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

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

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

Рис. 15.5. Регулярная решетка, в которой все вершины (за исключением граничных) имеют одинаковое число связей.

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