Занимаясь переводами Кнута, я наткнулся на упоминание очень интересного свойства нашей вселенной. Рождение гигантской компоненты. Каждый встречался с этим феноменом. Я, например, помню коробочки с рыболовными крючками. Когда крючков было 5-15 все нормально, но есть определенная критическая масса, после которой получался единый комок. Интуитивно я чувствую, что это очень важный феномен, который проявляется во многих дисциплинах — от теории информации, до молекулярной химии и биотехнологии. Предлагаю вашему вниманию перевод легкой и наглядной статьи на эту тему. Слово Brian Hayes.



Ненужным продуктом моего проекта, сканирующего документы, является куча извлеченных скоб.

На днях я сделал открытие: если вы захватите одну из выброшенных скоб и поднимите ее, целый клубок спутанного искореженного металла поднимется вслед за ней, оставляя лишь пару скоб на дне чаши. Когда я заметил это, я сначала подумал «Хм, это забавно». Потом «О, конечно: Erdos-Renyi». А третей мыслью… ну я все еще работаю над ней, а еще над четвертой, пятой и шестой.



Erdos и Renyi это Paul Erdos и Alfred Renyi, которые написали большую работу по «Эволюции Случайных Графов» 50 лет назад (Публикации Математического Института венгерской Академии наук, 1960, 5:17–61). Их статья не была вполне дебютным появлением случайных графов в математической литературе, но считается оригиналом происхождения теории.

В одной версии процесса Erdos-Renyi вы начинаете с множества изолированных вершин n и затем добавляете случайные ребра по одному; в частности, на каждом этапе вы выбираете две любые вершины из числа всех пар, которые уже не соединены, и затем рисуете ребро между ними.

Оказывается, драматическая перемена в природе графов происходит, когда количество граней достигает n/2. Ниже этого порога граф состоит из множества мелких, изолированных компонентов; выше n/2 фрагменты сливаются в одну гигантскую компоненту, которая включает в себя почти все вершины.

«Рождение гигантской компоненты» было позже описано более подробно в еще большей статье — она охватила весь вопрос случайных структур и алгоритмов (1993, 4:233-358) и была написана Сванте Янсоном, Дональдом Кнутом, Томашем Луцакой и Борисом Питтелем.

Что заставило меня подумать о связи между графами Erdos-Renyi и клубком скоб? У меня на уме было что-то вроде длинная, прямая, средняя часть скобы соответствует ребру графа, а изогнутые части, которые могут сцепиться друг с другом, являются вершинами. Таким образом, одна скоба это граф, состоящий из двух вершин, соединенных по одному краю. Когда две скобы соединены, две их вершины сливаются, и остается связный граф из трех вершин и двух ребер. Так как каждая скоба дает одно ребро и самое большее две вершины графу, количество ребер должно быть равно, по крайней мере, половине количества вершин. Таким образом, граф всегда превышает порог, когда образуется гигантская компонента, по данным Erdos и Renyi.

С вычислительной частью этого анализа кажется все ясно, но я боюсь, что остальное не так просто понять. Независимо от того, что происходит в скобочном шаре, эволюция системы не очень хорошо смоделирована процессом Erdos-Renyi, добавляющим грани к фиксированному набору вершин. Вместо этого каждая скоба дает 2 грани и 2 вершины.

Переломный момент, который заставляет пучок скоб держаться вместе — это слияние вершин, когда скобы скрепляются; в процессе Erdos-Renyi нет подобного слияния. Основная проблема здесь состоит в том, что графы Erdos-Renyi чисто топологические — нет никакого понятия расстояния, и любые две вершины могут иметь ребро, соединяющее их. Но у графа скоб есть важные геометрические ограничения. Две вершины могут быть соединены ребром, только если расстояние между ними примерно равно длине скобы.

Геометрическая структура предполагает попытки построения различного рода моделей — возможно, то, что описывает молекулярное строение жидкостей и твердых веществ. Молекулы воды, например, связаны друг с другом сетью водородных связей; каждый атом водорода в одной молекуле может иметь связь с атомом кислорода другой молекулы. Но связи не могут распространяться на произвольные расстояния; они распространяются только между соседними молекулами. В результате была получена трехмерная структура, основной мотив которой представляет собой тетраэдр с атомом кислорода в центре и атомами водорода в четырех углах. (Существует также схема двумерной модели, известной как площадь льда). Мы можем представить, как что-то подобное происходит со скобами, где два отогнутых конца могут образовывать водородные связи как связь с другими близлежащими скобами.

Но с такими химическими элементами тоже есть проблема. У атомов есть фиксированная валентность (более или менее – давайте не придираться); у воды, например, каждый атом водорода может сформировать водородную связь только с одним атомом кислорода. Но у нас нет оснований полагать, что крючковатые концы скоб могут цеплять только один край другой скобы. На самом деле, если бы такое ограничение имело место быть, то скобы могли бы сформировать только цепи и кольца, не плотные скопления. При близком рассмотрении скопления скоб легко найти места, где три или более скобы сцеплены вместе в одной и той же точке. Аккуратно заглянув вглубь скопления скоб, я нашел скобу, к которой цеплялись, по меньшей мере, шесть других скрепок.

Еще один физический процесс, который мог бы предоставить модель для основного графа, является агрегацией ограниченного распространения. Это — механизм, ответственный за филигранный узор.



Это произведено липкими частицами, которые дрейфуют случайным образом пока не наткнутся на основание или пока не коснутся другой частицы, которая уже находится в контакте (прямо или косвенно) с основанием.

Другим фактором, который необходимо учитывать, является тот факт, что пространственные размеры, несомненно, важны здесь. С одной стороны это дает просто больше возможностей маневрировать в трех измерениях, больше возможностей для того, чтобы прицепиться к соседу. Но конкретно в случае со скобами другая причина: будучи прикованными к плоскости, им тяжело соединяться.



Разбросанные на плоской доске они отказываются сворачиваться, даже когда крутятся энергично. Причина, по-видимому, состоит в том, что безопасные соединения формируются только, когда скобы могут повернуться на 90 градусов и сцепиться. В этой связи представляется важным, что используются скобы, довольно разнообразные по форме, с крючковатыми концами, согнутыми примерно на 180 градусов в процессе переплета и которые в основном сохранили угол больше 90 градусов после того, как их выдернули из бумаги.

Мне стало интересно, как поведут себя блестящие новенькие скобы и я провел эксперимент (Materials and methods: 630 Stanley Bostitch chisel-point staples, model SBS191/4CP, freshly dispensed from an open-jaw Swingline stapler.)

Я был, мягко говоря, удивлен результатом. Хотя скопление скоб было несколько более свободным и более тонким, суть действительно не особо отличалась. Снова мы свидетельствуем рождение гигантской компоненты.

Комментарии

Barry Cipra: Возможно, стоило бы повторить эксперимент с новыми скобами, делая паузу каждый раз, когда вы добавляете скобы (скажем каждые 10 или 20 скоб), встряхивая то, что уже находится в чаше, и затем наблюдать как образуется большое скопление, когда вы берете одну из скоб. Возможно, было бы неплохо повторить встряску и паузы между добавлением скоб несколько раз и понаблюдать за статистикой. Я предполагаю, что (средний) процент скоб, которые поднимутся с клубком скоб, будет довольно маленьким, пока общее количество скоб в миске не будет равно приблизительно сотне, и затем начнет увеличиваться к чему-то достаточно близкому 100%. Из этого следует какая-то логическая кривая? И если да, то какая? В любом случае, это замечательное наблюдение!

Yonkou: Очень красивая работа. Интересно, играет ли роль форма миски.

Я действительно понимаю эксперимент плоской пластины …, но вы добавляли скобы к верхушкам предыдущих (что оказывает давление, когда вы делаете это в чаше)? Также интересно, что произошло бы, если бы мы добавляли их в более ограниченном контейнере, скажем, в пробирке.

Unekdoud: Я думаю, вы должны рассмотреть возможность сделать это с различным офисным оборудованием, скажем со скрепками. Кроме того играет ли роль размер степлера?

Смешивайте и сочетайте их различные виды, чтобы образовать «сплавы». Если вы рассматриваете их как примеси во льду, мог бы быть определенный значимый эффект на структуру. Есть ли аналог температуры замерзания льда? Каковы изменения в плотности?
Обязательно, размер миски имеет значение. Вероятно, существует возможность сделать гигантская компонента в невыпуклой форме. Что касается самой структуры, вы могли бы хотеть рассмотреть фактически её отображение в виде графа, чтобы изучить свойства подграфов и циклов, а также такие вещи, как плотность вершин. Можно добавить немного клея, чтобы сохранить структуру, и чтобы за ней было легче наблюдать. Изменятся ли свойства графа, если используется другой метод для создания гигантской компоненты типа использования магнита или намагниченных ножниц, чтобы расшевелить структуру? Как бы это изменилось, если бы скобы были погружены в масло? Что, если они нагреваются или охлаждаются в середине процесса? Что насчет вибрации на разных частотах? С точки зрения размера компонента, вы, возможно, захотите продолжать добавлять скобы, чтобы посмотреть до каких размеров он может дорасти. Возможно ли объединить два компонента? И где можно это применить помимо физики и химии? Так же можно будет воссоздать этот эксперимент в контексте социальной сети. Аналогичные эффекты тогда будут наблюдаться в разных масштабах, или, возможно, будут совершенно другими.

Brian: Спасибо Barry и Yonkou и Unekdoud за то, что подняли несколько интересных вопросов и предложили дальнейшие направления для исследований. Прежде чем что-либо еще сказать, я хотел бы отметить, что это один из тех редких случаев в экспериментальной науке, где любой может играть. Материалы легко доступны. Вам не нужен грант NSF, чтобы финансировать исследование (хотя я предполагаю, что мы могли бы искать финансирование в магазинах канцелярских принадлежностей). Любой ценой: Захватите степлер и присоединитесь. В духе научного сотрудничества и рьяном преследовании правды, я готов поделиться своим запасом используемых скоб. Барри спрашивает о появлении кластеров в маленьких совокупностях скоб. Я не знаю, как это бывает. С графами Erdos-Renyi известные результаты строго справедливы лишь в пределах бесконечного N, но на практике бесконечность встречается довольно редко в теории графов.

Unekdoud спрашивает о самых больших достижимых скоплениях. Опять же я не знаю, но, конечно, должен быть физический предел. В какой-то момент вес скопления превышает силу той скобы, на которой все держится.

Что касается открытых вопросов о форме чаши, манере помешивая, размере скоб и т. д.: помимо того, что эти факторы важны, у нас нет системы, которая бы привела к четкому анализу. Я бы предпочел выйти из этого беспорядочного мира металлических скоб и перейти в область моделирования, где мы можем вычислительно моделировать и математически решать.

Но, конечно, у меня нет такой модели.

Наконец насчет скрепок. Это территория американского ученого коллеги Генри Петроски. Он написал об этом книгу и пусть это останется его областью.

Кevembuangga: Я думаю, что подобного рода “исследования” глубоко идиотские, однако я искренне благодарен, что некоторые люди занимаются ими, так же, как я благодарен людям, зависимым от видео игр за успешное развитие высокой производительности процессора.

Ben: первое о чем я подумал, когда вы начали говорить о случайных графах, это что «плоская» часть скобы должна быть вершиной, а «концы» должны быть краями — в конце концов все края формируют “связи”, которые вы описывали, когда обсуждали молекулы воды. Связи между краями формируются беспорядочно, поскольку скобы размещены в миске или перемешаны вокруг чаши или еще что-то. Тогда изменение от 2 до 3 измерения, от поверхности до миски, изменяет вероятность, что случайная связь формируется между любыми двумя вершинами. Нужно подумать о том как точно, но по-видимому на поверхности, ожидаемое количество связей — меньше, чем n/2, в то время как в миске оно больше.

Jess: Моя мысль заключается в том, что степлер это в целом — вершина и край сформированные, когда две скобы зацепляются друг за друга. Это кажется проще, чем предложенный процесс “слияния”. Мы не ожидаем, что понятие края больше заключается в связи между двумя объектами, чем в грубом физическом аналоге?

Stephan Mertens говорит: Я предполагаю, что своего рода энтропийный храповой механизм (entropic ratchet mechanism) (по крайней мере, частично) ответственен за формирование гигантской компоненты: есть много способов того как две скобы могут зацепиться но это требует, чтобы скоординированное перемещение отделило пару соединенных скоб. И я думаю, что тот же самый аргумент относится к шнурам питания в вашем ящике, которые всегда формируют гигантский узел.

Еще материалы:

• Giant component
• The birth of the giant component (Knuth)
• Связность G(n,p), гигантская компонента, характеристические числа G(n,p)
• Lecture 9 — Теорема о появлении гигантской компоненты в случайном графе
• Системная биология – сети М.Гельфанд «Сравнительная геномика» БиБи 4 курс. — презентация
• From Cycles to Giant Components, a Socially-guided Tour
• NetLogo Models Library: Sample Models/Networks

---

Поддержка публикации — компания Edison, которая разрабатывает биллинговую систему для провайдеров, а так же разрабатывает ПО для сдачи налоговой отчетности через Интернет.