Читать «Критическая масса, как одни явления порождают другие» онлайн - страница 313

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

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

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

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

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

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