Критическая масса. Как одни явления порождают другие

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

Частично связный граф Полностью связный граф

Рис. 15.4. Случайный граф считается полностью связным, если все его вершины связаны в единую сеть (б). В противном случае некоторые вершины (или даже кластеры вершин) остаются изолированными, как показано на рисунке а.

Еще в начале 1950-х годов некоторые социологи, занявшиеся приложениями теории графов (например, группа Анатоля Рапопорта в университете Чикаго), заподозрили, что графы социальных отношений и связей по своим топологическим особенностям относятся к классу случайных. Предположение оказалось не очень правильным, но очень плодотворным, поскольку случайные графы стали прекрасной моделью для понимания основополагающих структур в таких отношениях. Кроме того, Эрдеш и Реньи уже разработали очень удобный математический аппарат для исследования графов этого типа.

Свойства таких структур описываются, естественно, в терминах статистики, поскольку соединение вершин с самого начала осуществляется случайным образом. При большом числе вершин (достаточно ста) вероятность получения одинаковых графов за счет случайного совпадения соединения вершин становится пренебрежимо малой. Аналогично тому как в статистической физике нас интересовало не поведение конкретных молекул, а связанные с этим поведением усредненные характеристики газа в целом, при изучении случайных графов с большим числом вершин мы также можем ограничиться исследованием только среднего числа связей на вершинах. Естественно, что наиболее интересной и важной характеристикой является статистическое распределение вероятностей для этого числа по всей системе. Эрдеш и Реньи показали, что оно представляет собой привычную колоколообразную кривую Гаусса, пик которой соответствует среднему числу связей. Разумеется, среднее значение зависит от числа ребер графа, но для определенного случайного графа оно является вполне конкретным.

К иному (точнее сказать, противоположному) типу графов относятся регулярные решетки с одинаковыми вершинами, соединенными одинаковыми ребрами (рис. 15.5). Естественно, что математическое описание таких «упорядоченных» графов выглядит значительно проще, чем случайных. Кроме того, в этом случае не имеет смысла говорить о среднем числе ребер, так как каждая вершина, за исключением граничных или угловых, имеет одинаковое число связей (четыре для показанного на рисунке графа).

Упорядоченные и случайные графы обладают очень разными свойствами. В теории графов вообще чрезвычайно важен вопрос средней длины пути (маршрута), связывающего две случайно выбранные вершины. Эта величина называется характеристической длиной, а ее статистический смысл соответствует среднему числу пересылок пакета из Небраски в Бостон в описанном эксперименте Стэнли Мильграма. В упорядоченных графах характеристическая длина маршрута обычно довольно велика, потому что передвижение состоит из маленьких одинаковых шажков между ближайшими вершинами. В случайном графе всегда существует некоторая вероятность того, что исходная точка маршрута связана «длинной» прямой связью с вершиной, находящейся поблизости от точки назначения. Существует множество таких «коротких» путей, и соответственно характеристическая длина уменьшается по сравнению с упорядоченными графами. Более того, добавление дополнительных вершин не приводит к увеличению характеристической длины для случайных графов (в отличие от упорядоченных) и даже повышает вероятность нахождения еще более короткого маршрута.

На первый взгляд кажется очевидным, что социальные сети для небольших групп населения (типа нарисованной схемы связей между киноактерами) должны относиться к классу случайных. Идея выглядела вполне разумной, учитывая явно случайный характер многих социальных связей, и многие социологи стали рассматривать ее в качестве основы построения социальных сетей. Однако в 1998 году двое ученых из Корнельского университета (Стивен Строгац и его студент Дункан Ватте) показали, что социальные сети не относятся к случайным графам, а образуют собственный класс, промежуточный между упорядоченными и случайными графами. Такие структуры, лежащие где-то между полным беспорядком (в случайных графах) и полным порядком (в упорядоченных графах), были очень удачно названы авторами сетями малых миров.