Часть 3.1 Введение

Представьте, что вы устраиваете вечеринку на сто человек, которые изначально не знакомы друг с другом [1]. Вы угощаете их вином и сыром и вскоре они начинают общаться в группах по два-три человека. Теперь скажите Мэри, одной из ваших гостей, что красное вино в темно-зеленых бутылках без этикетки — это редкое старинное вино, которое гораздо лучше, чем то, что в бутылках с модной красной этикеткой. Если она расскажет об этом только своим знакомым, то ваше дорогое вино, по-видимому, останется нетронутым, поскольку у нее пока было время на то, чтобы встретить лишь несколько человек.

Однако, гости продолжат общаться друг с другом, образуя косвенную связь между людьми, которые все еще не знакомы лично. Например, в то время как Джон еще не встретил Мэри, оба они уже встретились с Майком, и таким образом, между Джоном и Мэри существует невидимая связь посредством Майка. Со временем гости будут все более и более переплетены такими неявными связями. В результате чего секрет бутылки без этикетки перейдет от Мэри к Майку, а от Майка к Джону, проникая в быстро растущую группу людей.

Несомненно, когда все гости перезнакомятся, каждый будет разливать это более качественное вино. Но если бы каждая новая встреча происходила раз в десять минут, на знакомство каждого гостя с остальными 99 людьми потребовалось бы около 16 часов. Таким образом, у вас есть все основания надеяться, что при подобном сценарии после ухода гостей вам останется несколько капелек этого первоклассного вина.

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

Часть 3.2 Модель случайной сети.

Цель науки о сетях – создать модели, которые обладают свойствами реальных сетей. Узлы большинства сетей, с которыми мы сталкиваемся, не упорядочены регулярно, подобно узлам кристаллической решетки. Напротив, на первый взгляд кажется, что они расположены произвольно (Рисунок 2.4.). Теория случайных сетей описывает эту видимую случайность посредством моделирования и анализа сетей, которые по-настоящему случайны.

С точки зрения построения моделей, сети просты, так как состоят лишь из узлов и связей между ними. Вопрос здесь в том, как и какие узлы связать между собой, чтобы воспроизвести всю сложность реальных систем. В этом плане философия, лежащая в основе случайных сетей проста – мы уславливаемся, что лучшим способом решить эту задачу является полностью случайное соединение узлов сети. А это, в свою очередь, приводит нас к определению случайной сети (Памятка 3.1):

Случайная сеть состоит из N узлов, соединенных между собой попарно с вероятностью p.

Для создания случайной сети необходимо исполнить следующие шаги:

• Создадим N изолированных узлов.
• Выберем случайную пару узлов и сгенерируйте случайное число между 0 и 1. Если число больше чем p, проведем ребро между узлами.
• Повторим пункт (2) для каждой из N(N-1)/2 пары узлов.

Полученная таким путем сеть называется случайным графом или случайной сетью. Два математика, Пол Эрдёш и Альфред Реньи, сыграли важную роль в понимании свойств случайных сетей. В их честь, случайные сети называются сетями Эрдёш-Реньи ( Памятка 3.2).

Часть 3.3 Количество связей

Случайные сети, образованные с одинаковыми параметрами N и p, несколько отличаются друг от друга (Изображение 3.3). Отличия заключаются не только в том, какие узлы связаны, а какие – нет, но и в общем количестве связей L. Таким образом, полезно определить, сколько связей образуется в каждой конкретной случайной сети с заданными параметрами N и p.

Вероятность, что случайная сеть содержит ровно L связей равна произведению трех величин:

1. Вероятность, что из N(N-1)/2 пар узлов сети L пар будут связаны, равная p^L.
2. Вероятность, что оставшиеся N(N-1)/2-L узлов не будут связаны, равная (1-p)N(N-1)/2-L.
3. Комбинаторный коэффициент $\left( {\begin{array}{*{20}c} {\frac{{N(N - 1)}}{2}} \\ L \\ \end{array}} \right) \hspace{20 mm} (3 . 0)$который равен количеству способов разместить L связей между N(N-1)/2 парами узлов.

Таким образом, вероятность, что каждая конкретная случайная сеть содержит ровно L связей, равна

Поскольку формула 3.1 описывает биномиальное распределение (памятка 3.3), математическое ожидание количества связей в случайном графе равно

Таким образом, 〈L〉 равно произведению вероятности p, что два узла связаны и общего количества пар узлов сети, которые мы можем соединить, равное L_max= (N(N-1))/2 (Глава 2).

Из формулы (3.2) мы можем вывести формулу для средней степени случайной сети

Следовательно 〈k〉 равно произведению вероятности p того, что два узла связаны и (N-1) – максимального количества связей любого из N узлов сети.

Резюмируя, количество связей различных случайных сетей с одинаковыми параметрами может отличаться. Его математическое ожидание определяется посредством N и p. Если мы увеличим p, случайная сеть становится более плотной. Среднее количество связей растет линейно от 〈L〉=0 до 〈L〉=L_max, а средняя степень узла увеличивается от 〈k〉= 0 до 〈k〉=N-1.

Часть 3.4 Распределение степеней

В каждой конкретной случайной сети меньшее количество узлов обладает множеством связей, в то время как на большинство приходится значительно меньше связей, или же совсем ничего (Изображение 3.3). Эти отличия хорошо показывает распределением степеней p_k, которое обозначает вероятность, что случайно выбранный узел сети имеет степень k. В этом разделе мы выводим форму p_k для случайной сети и обсуждаем ее свойства.

Биномиальное распределение

В случайной сети вероятность, что узел i обладает ровно k связями равна произведению трех величин [15]:

• Вероятность, что узел имеет k связей, p_k
• Вероятность, что связей кроме k (в количестве N-1-k) не существует, (1-p)^N-1-k.
• Количество способов, которыми можно связать данный узел с k другими узлами из N-1 возможных связей, равное $\left( {\begin{array}{*{20}c} {N - 1} \\ k \\ \end{array}} \right)$.

Следовательно, степени случайной сети распределены биноминально:

Форма такого распределения зависит от размера сети N и вероятности p (Изображение 3.4). Биномиальное распределение (памятка 3.3) позволяет нам вычислить среднюю степень сети 〈 k 〉 , используя (3.3), а также ее второй момент 〈𝑘²〉 и дисперсию 𝜎_𝑘 (Изображение 3.4).

Распределение Пуассона

Большинство реальных сетей имеют низкую плотность связей, т.е. их

‹k› ‹‹ N (Таблица 2.1). В таком предельном случае распределение степеней (3.7) хорошо аппроксимируется распределением Пуассона (Дополнительный материал 3.А)

которое часто называют (совместно с (3.7)) распределением степеней случайной сети.

Биномиальное и Пуассоновское распределения описывают одинаковую величину, т.е. у них одинаковые свойства (Изображение 3.4):

• Оба распределения имеют максимум возле 〈 k 〉. Если мы увеличим вероятность p, то сеть станет плотнее, увеличивая 〈 k 〉 и сдвигая максимум вправо.
• «Ширина» распределения, или дисперсия также зависит от p или 〈 k 〉. Чем плотнее сеть, тем «шире» распределение, и тем больше различия в степенях различных узлов.

Применяя распределение Пуассона (3.8), необходимо помнить, что

• Наиболее точно распределение степеней описывается биномиальным распределением (3.7), а (3.8) – это аппроксимация, действительная лишь в случаях, когда 〈k〉 значительно меньше N. Поскольку большинство случайных сетей, обладающих практической ценностью, имеют низкую плотность связей, это условие обычно соблюдается.
• Преимущество распределения Пуассона состоит в том, что ключевые характеристики сети, такие как 〈k〉, 〈k^2〉, σk вычисляются значительно проще (картинка 3.4) и зависят только от одного параметра 〈k〉.
• Распределение Пуассона (3.8) не имеет прямой зависимости от количества узлов N. Таким образом, (3.8) предопределяет, что распределения степеней сетей разных размеров, но с одинаковой средней степенью 〈k〉 будут неотличимы друг от друга (Изображение 3.5).

В заключение отметим, что распределение Пуассона - это лишь аппроксимация настоящего распределения степеней случайной сети, однако благодаря его аналитической простоте ему отдается предпочтение для вычисления pk. Таким образом, в продолжение настоящей книги, если не оговорено иначе, мы будем считать, что степени случайной сети имеют распределение Пуассона (3.8). Его ключевая особенность состоит в том, что его свойства зависят не от размера сети, а только от одного параметра – средней степени 〈k〉.

Часть 3.5 Реальные сети не следуют распределению Пуассона

Учитывая, что степень узла в случайной сети может принимать значения от 0 до N-1, как сильно могут отличаться степени узлов в какой-либо конкретной случайной сети? А именно, могут ли узлы с большими степенями сосуществовать с узлами с малыми степенями? Мы ответим на эти вопросы, оценивая размер самых больших и самых малых узлов случайной сети.

Давайте предположим, что всемирная социальная сеть укладывается в рамки модели случайной сети. Формирование общества случайным образом на самом деле не притянуто за уши, как это может показаться на первый взгляд. Мы встречаем новых людей и вступаем с ними в отношения совершенно случайно.

Социологи считают, что в среднем каждый из нас имеет порядка 1000 знакомых, что позволяет нам предположить, что ≈ 1000. Используя уже известные нам соотношения для случайных сетей, мы можем прийти к ряду занимательных выводов и умозаключений о случайном обществе, состоящем из N≈7×10⁹ человек (Дополнительный материал 3.Б):

• Человек, имеющий наибольшее количество знакомых (узел с наибольшей степенью) в случайном обществе будет иметь порядка 1185 знакомых, k_max=1185.
• Степень человека с наименьшим количеством связей будет равной 816, что не сильно отличается от k_max или 〈k〉.
• Дисперсия случайной сети σ_k=〈k〉^(1/2). Для 〈k〉=1000 σ_k составляет 31,62, откуда следует, что среднее количество знакомых случайного человека лежит в пределах 〈k〉±σ_{k, или между 968 и 1032, т.е. в достаточно узком диапазоне.}

Мы ожидаем, что у всех членов этого случайного сообщества будет сравнимое количество знакомых. Следовательно, если люди связаны друг с другом случайным образом, среди них нет как чрезвычайно популярных людей, количество знакомых которых значительно превышает среднее, как нет и изгоев, практически не имеющих знакомых. Это удивительное заключение является следствием одного важного свойства случайных сетей: в большой случайной сети степень большинства узлов не сильно отличается от 〈k〉.

Это предсказание вопиюще противоречит реальности. Действительно, существует множество примеров, когда кто-либо знает гораздо больше, чем 1185 людей. Например, в книге деловых встреч президента США Франклина Делано Рузвельта отмечено более 22000 имен людей, с которыми он встречался лично [16, 17]. Аналогичным образом, исследование социальной сети Facebook обнаружило множество людей, имеющих более 5000 друзей, что является максимально возможным количеством друзей на платформе Facebook [18]. Чтобы понять истоки этих расхождений, нам потребуется сравнить распределения степеней реальной и случайной сетей.

Часть 3.6 Эволюция случайных сетей

Коктейльная вечеринка, с которой мы столкнулись вначале этой главы описывает динамический процесс: начиная с N изолированных узлов, связи между случайными гостями постепенно устанавливаются с течением времени. Это соответствует постепенному увеличению p, что приводит к поразительным последствиям для топологии данной сети (Видео 3.2). Чтобы дать количественную оценку данному процессу, мы в первую очередь оцениваем как меняется размер самого большого связного кластера сети, N_G с изменением 〈k〉. Два предельных случая просты:

Для p=0 〈k〉=0 и следовательно все узлы изолированы. Следовательно самая большая компонента сети имеет размер 1, N^G=1, и N^G/N→0 для больших N.

Для p=1 〈k〉=N-1 и следовательно сеть является полным графом и все узлы принадлежат одной компоненте. Следовательно NG=N и Ng/N=1.

Можно было бы ожидать, что самый большой компонент увеличивается постепенно с NG=1 до NG=N если 〈k〉 увеличивается с 0 до N-1. Но, как показывает Картинка 3.7а, этого не происходит: отношение NG/N остается близким к нулю для малых 〈k〉, указывая на отсутствие большого кластера. Как только 〈k〉 превысит критическое значение, NG/N увеличится, сигнализируя о быстром возникновении большого кластера, который мы называем гигантской компонентой. Эрдёш и Реньи в их классической статье 1959-го года предсказали, что необходимым условием для возникновения гигантской компоненты является [2]

Другими словами, гигантская компонента присутствует тогда и только тогда, когда каждый узел в среднем имеет более одной связи (Дополнительный материал 3.В).

Факт, что для наличия гигантской компоненты требуется как минимум одна связь на каждый узел не является неожиданным. Действительно, для существования гигантской компоненты нужно, чтобы каждый узел, который является ее частью, имел хотя бы одну связь с соседним узлом. С другой стороны, это условие противоречит здравому смыслу.

Мы можем выразить (3.10) через p, используя формулу (3.3),

Таким образом, чем больше сеть, тем меньшего значения p достаточно для возникновения гигантской компоненты.

Возникновение гигантской компоненты - это лишь одно из многих преобразований, которыми можно охарактеризовать случайную сеть по мере изменения . Можно выделить 4 топологически различных режима случайной сети (Изображение 3.7.а), каждый из которых обладает уникальными характеристиками.

Подкритический режим: 0

При 〈k〉=0 сеть состоит из N изолированных узлов. Увеличение 〈k〉 приводит к созданию N〈k〉=pN(N-1)/2 связей между узлами сети. И все же, при 〈k〉<1 в сети имеется лишь малое количество связей, и следовательно большинство кластеров имеет малый размер (Изображение 3.7б).

В любой момент мы можем обозначить самый большой кластер как гигантскую компоненту. И все же в таком режиме относительный размер самого большого кластера NG/N остается близким нулю. Это происходит потому, что при 〈k〉<1 самый большой кластер – это дерево размера NGlnN, размер которого увеличивается гораздо медленнее, чем размер сети. Поэтому в пределе NG/N≅lnN/N→0 при N→∞.

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

Критическая точка: 〈k〉=1(p=1/N, Изображение 3.7 в)

Критическая точка отделяет режим сети, в котором еще нет гигантской компоненты (〈k〉<1) от режима сети, в котором она уже есть (〈k〉>1). В этом режиме относительный размер самой большой компоненты все еще близок к нулю (Изображение 3.7 в). Действительно, размер самой большой компоненты все еще NG~N^(2/3). Следовательно размер NG растет гораздо медленнее, чем размер сети и его относительный размер уменьшается по формуле NG~ N^(-1/3) при N → ∞.

Заметим, однако, что в абсолютных величинах размер самой большой компоненты совершает сильный скачок при = 1. Например, для случайной сети, состоящей из N=7×10⁹ узлов, и сравнимой по размерам с мировой социальной сетью всех людей, при < 1 самый большой кластер имеет размер порядка NG≅lnN=ln⁡(7×10⁹)≅22.7. Для сравнения, при = 1, для которого мы ожидаем NG~N^(2/3)=(7×10⁹)^(2/3 )≅3×10^6, мы имеем скачок на 5 порядков. И все же, в обоих случаях — в подкритическом режиме и критической точке — отношение количества узлов, которые содержит наибольшая компонента, к общему количеству узлов сети стремится к 0.

В итоге, в критической точке большинство узлов расположено во множестве малых компонент, размеры которых имеют распределение (3.36). Степенной закон указывает на то, что в сети присутствуют компоненты разных размеров. Множественные малые компоненты в основном представляют из себя деревья, в то время как большие компоненты могут содержать петли. Отметим, что многие свойства сети в критической точке похожи на свойства физической системы осуществляющей фазовый переход (Дополнительный материал 3.Е).

Сверхкритический режим: 〈k〉>1(p>1/N, Изображение 3.7г).

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

или

где величина pc задана по (3.11). Другими словами, гигантская компонента содержит существенную часть узлов случайной сети. Чем дальше мы продвигаемся за критическую точку, тем больше узлов входит в гигантскую компоненту. Отметим, что (3.12) имеет смысл только в окрестностях 〈k〉=1. Для больших 〈k〉 зависимость NG от 〈k〉 нелинейна (Изображение 3.7a).

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

Связный режим: 〈k〉>lnN(p>lnN/N, Изображение 3.7д)

Для достаточно больших p гигантская компонента поглощает все узлы и компоненты, а следовательно NG≅N. С отсутствием изолированных узлов сеть становится связной. Средняя степень при этом начинает зависеть от N как (Дополнительный материал 3.Д)

Отметим, что когда сеть переходит в связный режим, она все еще имеет низкую плотность связей, т.к. lnN/N→0 для больших N. Сеть становится полным графом только по достижении 〈k〉=N-1.

Таким образом, модель случайной сети предсказывает, что возникновение сети – это не плавный постепенный процесс: изолированные узлы и малые компоненты, наблюдаемые при малых 〈k〉 объединяются в гигантскую компоненту путем фазового перехода (Дополнительный материал 3.Е). Меняя значения 〈k〉 можно отметить 4 топологически различных режима сети (Изображение 3.7).

Приведенное выше обсуждение проводилось с практической точки зрения, удобной при сравнении случайных сетей с реальными системами. Взгляд на случайные сети с другой стороны, со всем её богатством и разнообразием приводится в математической литературе (Памятка 3.5).

Часть 3.7 Реальные сети - сверхкритические

Два предсказания теории случайных сетей имеют непосредственную важность для реальных сетей:

Как только средняя степень превысит значение 〈k〉= 1, должна появиться гигантская компонента, которая содержит существенную часть всех узлов. Т.е. только для 〈k〉> 1 узлы организуются в узнаваемую сеть.

Для 〈k〉> lnN все компоненты поглощаются гигантской компонентой, образуя единую полностью связную сеть.

Соответствуют ли реальные сети минимальному критерию существования гигантской компоненты, т.е. 〈k〉> 1? Будет ли эта гигантская компонента содержать все узлы при 〈k〉> lnN, или мы будем и дальше наблюдать изолированные узлы и компоненты? Чтобы ответить на эти вопросы, мы сравним структуру реальной сети при заданном 〈k〉 с теоретическими результатами, описанными ранее.

Эксперименты показывают, что реальные сети странным образом превышают порог в 〈k〉= 1. Действительно, социологи дают оценку, что в среднем человек имеет около 1000 знакомых; средний нейрон в человеческом мозге содержит порядка 7000 синапсов; в наших клетках каждая молекула участвует в нескольких химических реакциях.

Это заключение подтверждается в Таблице 3.1, которая отображает средние степени нескольких неориентированных сетей, каждая из которых имеет 〈k〉> 1. Таким образом, средняя степень реальных сетей значительно больше порогового значения 〈k〉= 1, что означает что каждая из них обладает гигантской компонентой. Что также верно для сетей, приведенных в Таблице 3.1.

Часть 3.8 Тесный Мир

Феномен «тесного Мира», также известный как шесть степеней отчуждения давно восхищает широкую публику. Он гласит, что если вы случайно выберете двух человек где угодно на Земле, вы обнаружите, что они связаны между собой не более чем через шесть знакомых (Рисунок 3.10). Тот факт, что люди, которые живут в одном и том же городе разделены лишь несколькими рукопожатиями друг от друга не является ни в коей мере неожиданным. Однако, концепция «тесного Мира» утверждает, что даже люди, которые находятся на другой стороне Земного шара могут быть связаны с нами через всего лишь нескольких знакомых.

На языке науки о сетях феномен тесного Мира подразумевает, что расстояние между двумя случайными узлами сети мало. Это утверждение поднимает два вопроса: Что значит малое расстояние, т.е малое в сравнении с чем? Как мы можем объяснить существование этих малых расстояний?

На оба вопроса можно ответить простым вычислением. Возьмем случайную сеть со средней степенью 〈k〉. Узел такой сети имеет в среднем:

〈k〉 узлов на расстоянии единица (d=1).

〖〈k〉〗^2 узлов на расстоянии двойка (d=2).

〖〈k〉〗^3 узлов на расстоянии три (d=3).

…

〖〈k〉〗^d узлов на расстоянии d.

Например, если 〈k〉≈1000, что равно, как считается, среднему количеству знакомых случайного индивидуума, то мы ожидаем 〖10〗^6 человек на расстоянии два или около миллиарда, т.е. практически все население Земли, на расстоянии три от нас.

Если быть точнее, математическое ожидание количества узлов на расстоянии d от изначального узла равно:

N(d) не должно превысить полное количество узлов N сети. Таким образом, расстояния не могут принимать случайные значения. Мы можем определить максимальное расстояние dmax, или диаметр сети как

Полагая, что 〈k〉≫1, мы можем проигнорировать слагаемое «-1» в числителе и знаменателе (3.15) и получить

Следовательно, диаметр случайной сети удовлетворяет

что и является математической записью феномена тесного Мира. Однако, вся суть в его интерпретации:

• В изначальной форме (3.18) предсказывает масштабирование диаметра сети dmax вместе с размером системы, N. И все же для большинства сетей (3.18) предлагает лучшее приближение среднего расстояния между двумя случайно выбранными узлами, 〈d〉, чем приближение значения dmax (Таблица 3.2). Потому что несколько длины экстремальных путей часто доминируют над значением dmax, в то время как 〈d〉 является средним для всех пар узлов, что нивелирует все сильно отклоняющиеся значения. Таким образом, свойство тесного Мира определяется формулой $\left\langle d \right\rangle \approx \frac{{\ln N}}{{\ln \left\langle k \right\rangle }} \hspace{20 mm} (3 . 19)$, которая описывает зависимость среднего расстояния в сети от N и 〈k〉.
• В общем случае lnN≪N, поэтому зависимость 〈d〉 от lnN подразумевает, что расстояния в случайной сети на порядки меньше, чем размер сети. Поэтому под теснотой в «феномене тесного Мира» мы имеем в виду, что средняя длина пути, или диаметр сети зависят от размера сети логарифмически. Отсюда «малый» означает, что 〈d〉 пропорционально lnN, а не N или N в какой-либо степени (Картинка 3.11).
• Множитель 1/ln〈k〉 подразумевает, что чем больше плотность сети, тем меньше расстояние между ее узлами.
• Реальные сети систематически отклоняются от (3.19), что происходит из-за того, что количество узлов на расстоянии d>〈d〉 резко уменьшается (Дополнительный материал 3.Е).

Давайте проиллюстрируем следствия формулы (3.19) для социальных сетей. Подставляя N≈(7×〖10〗^9) и 〈k〉≈〖10〗^3, мы получаем

Следовательно, все люди на Земле должны быть на расстоянии от трех до четырех рукопожатий друг от друга [20]. Оценка (3.20) вероятно ближе к настоящему значению, чем часто упоминаемые шесть степеней отчуждения (Памятка 3.7).

Мы знаем, что случайные сети обладают свойством «тесного Мира», включая результат (3.19), благодаря малоизвестной статье Манфреда Кохена и Итиэль де Сола Пула [20], в которой они сформулировали эту проблему математически и обсудили ее социологические следствия в деталях. Эта статья вдохновила хорошо известный эксперимент Милгрэма (Памятка 3.6), который в свою очередь вдохновил назвать этот феномен «шесть рукопожатий» или «шесть степеней отчуждения».

Несмотря на то, что свойство тесного Мира было обнаружено в социальных системах, оно находит свое применение за пределами социальных сетей. (Памятка 3.6). Для демонстрации этого факта в Таблице 3.2 мы сравниваем предсказания 3.19 со средней длиной пути 〈d〉 для различных реальных сетей и обнаруживаем, что несмотря на разнообразие сравниваемых систем и их существенные различия в терминах N и 〈k〉, (3.19) является хорошим приближением 〈d〉, наблюдаемого в экспериментах.

Таким образом, «тесный Мир» не только подогревает общественный интерес (Памятка 3.8), но и играет важную роль в науке о сетях. Феномен «тесного Мира» может быть достаточно хорошо понят в рамках модели случайной сети: он уходит корнями в тот факт, что число узлов на расстоянии d от данного узла возрастает экспоненциально с ростом d. В последующих главах мы увидим, что в реальных сетях встречаются систематические отклонения от (3.19), заставляя нас использовать другие более аккуратные формулы. И все же интуитивное объяснение феномена «тесного Мира», которое дает модель случайной сети остается верным.

Часть 3.10 Заключение: Реальные сети не случайны

С момента появления в 1959 году, модель случайных сетей доминировала среди математических методов по работе со сложными сетями. Модель предполагает, что сети, которые похожи на случайные и наблюдаются в сложных системах, следует рассматривать как исключительно случайные сети. Таким образом, сложность приравнивалась к случайности. Отсюда вытекает вопрос:

Действительно ли мы считаем, что все реальные сети случайны?

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

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

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

Распределение степеней

Случайная сеть обладает биномиальным распределением, которое хорошо аппроксимируется распределением Пуассона в пределах для k≪N. Все же, как показано на Картинке 3.5, распределение Пуассона не способно описать распределение степеней реальных сетей. В реальных системах присутствуют узлы, обладающие значительно большей связностью, чем можно учесть с помощью модели случайных сетей.

Связность

Теория случайных сетей предсказывает, что для 〈k〉>1 мы должны наблюдать гигантскую компоненту, условие, соблюдаемое всеми сетями, которые мы исследовали. Тем не менее, большинство сетей не удовлетворяют условию 〈k〉≫ ln N , подразумевая, что они должны распадаться на изолированные кластеры (Таблица 3.1). Некоторые сети действительно фрагментированны, но большинство – нет.

Средняя длина пути

Теория случайных сетей предсказывает, что средняя длина пути подчиняется (3.19), что дает достаточно точное приближение наблюдаемых длин путей. Таким образом, случайная сеть учитывает появление феномена «тесного Мира».

Коэффициент кластеризации

В случайной сети локальный коэффициент кластеризации не зависит от степени узла и 〈C〉 зависит от размера системы пропорционально 1/N. В противоположность этому измерения показывают, что для реальных сетей C(k) уменьшается вместе с уменьшением степени узла и не зависит значительно от размера системы (Картинка 3.13).

Все вышеперечисленное вместе означает, что феномен «тесного Мира» является единственным свойством, которое приемлемо объясняется моделью случайной сети. Все остальные характеристики сетей, начиная с распределения степеней и заканчивая коэффициентом кластеризации, значительно отличаются от реальных сетей. Расширение модели Эрдёша-Реньи, предложенное Ваттсом и Строгацом, успешно предсказывает сосуществование больших C и малых 〈d〉, но не способно объяснить распределение степеней и C(k). По сути, чем больше мы узнаем о реальных сетях, тем ближе мы подходим к потрясающему заключению, что нам не известна ни одна реальная сеть, которая бы точно описывалась моделью случайных сетей.

Такое заключение вызывает закономерный вопрос – если реальные сети не случайны, почему мы посвятили целую главу модели случайных сетей? Ответ прост: эта модель послужит важным эталоном по мере нашего продвижения в изучении свойств реальных сетей. Каждый раз, наблюдая какое-либо свойство какой-нибудь сети, мы будем задаваться вопросом – могло ли оно возникнуть случайно. Для этого мы превратим модель случайных сетей в руководство: если реальная сеть обладает свойством случайной сети, значит оно могло возникнуть случайно. Если случайная сеть не обладает каким-либо свойством, значит, что оно является признаком порядка и требует более глубокого объяснения. Итак, модель случайных сетей может быть плохой моделью для описания большинства реальных сетей, но она остается очень актуальной для науки о сетях (Памятка 3.10).

Домашнее Задание

• Сети Эрдёша-Реньи

Имеется сеть Эрдёша-Реньи с N=3000 узлов, связанных между собой с вероятностью p=10^-3.

• Каково математическое ожидание количества связей, 〈L〉?
• В каком режиме находится случайная сеть?
• Вычислите вероятность pc при которой сеть находится в критической точке
• Для заданной вероятности p=〖10〗^(-3) вычислите количество узлов N^cr, для которого сеть обладает лишь одной компонентой.
• Для сети (г) вычислите среднюю степень 〈k^cr〉 и среднее расстояние между двумя случайно выбранными узлами 〈d〉
• Вычислите параметры распределения p^k для этой сети ( аппроксимируйте распределением степеней Пуассона)
• Построение сетей Эрдёша-Реньи

Опираясь на модель G(N,p), сгенерируйте на компьютере 3 сети с количеством узлов N=500 и средней степенью (а) 〈k〉=0.8, (б) 〈k〉=1 и (в) 〈k〉=8. Визуализируйте эти сети.

• Кольцевая сеть

Дана сеть с N узлами, расположенными на окружности так, что каждый узел соединяется с m соседними узлами с каждой стороны (следовательно каждый узел имеет степень 2m). Картинка 3.14 (а) показывает пример такой сети с m=2 и N=20. Вычислите средний коэффициент кластеризации 〈C〉 и средний кратчайший путь 〈d〉 этой сети. Для простоты считайте, что N и m выбраны так, что (N-1)/2m делится нацело. Что происходит с 〈C〉, когда N≫1? Что происходит с 〈d〉?

• Дерево Кейли

Дерево Кейли – симметричное дерево, которое строится с корнями в центральном узле степени k. Каждый узел на расстоянии d от центрального узла имеет степень k, а крайние узлы на расстоянии P обладают степенью 1 и зовутся листьями (См. Изображение 3.16, на котором показано дерево Кейли с k=3, P=5).

• Вычислите количество узлов, в которые можно попасть за t шагов от центрального узла.
• Вычислите распределение степеней такой сети.
• Вычислите диаметр d _max.
• Найдите выражение для вычисления диаметра d_max по количеству узлов N.
• Обладает ли такая сеть свойством «тесного Мира»?
• Снобистская сеть

Дана сеть из N красных и N синих узлов. Вероятность связи между узлами одного цвета – p, а между узлами разного цвета – q. Сеть является снобистской, если p>q, что отражает тенденцию узлов устанавливать больше связей одного цвета. Для q=0 в сети есть не менее двух компонент, содержащих узлы одинакового цвета.

• Вычислите среднюю степень «синей» подсети, состоящей только из синих узлов, а также среднюю степень всей сети.
• Определите минимальные p и q, необходимые для наличия с высокой вероятностью лишь одной компоненты.
• Покажите, что для больших N даже очень снобистские сети (p≫q) обладают свойством «тесного Мира».
• Снобистские социальные сети

Рассмотрите следующую вариацию модели, описанной выше: мы имеем сеть из 2N узлов, состоящую из равного числа красных и синих узлов, при этом порция f из 2N узлов – фиолетовая. Синие и красные узлы не образуют связей (q=0), в то время как между собой они образуют связи с вероятностью p. Фиолетовые узлы связывается с той же вероятностью p как с красными, так и с синими узлами.

• Мы называем красные и синие сообщества интерактивными, если обычный красный узел находится на расстоянии двух шагов от синего узла и наоборот. Оцените, какая часть узлов должна быть фиолетовой, чтобы красные и синие сообщества были интерактивными.
• Опишите размер фиолетового сообщества, если средняя степень синих или красных узлов составляет 〈k〉≫1.
• Каковы следствия из этой модели вытекают для структуры социальной (или других) сетей?

Дополнение Б. Максимальные и минимальные степени

Для определения степени для наибольшей степени узла в случайной сети, так же называемой верхним натуральным пределом сети, мы обозначим степень k_max, такую что для сети из N узлов будет существовать не более одного узла со степенью, большей чем k_max. Математически это означает что площадь под кривой Пуассоновского распределения p_k для k ≥ k_max должно равняться примерно 1 (Изображение 3.17). Так как площадь определяется как 1-P(k_max), где P(k) - кумулятивное распределение степеней p _k, наиболее связанному узлу сети соответствует:

$N\left[ {1 - P\left( {k_{\max } } \right)} \right] \approx 1 \hspace{20 mm} (3 . 26)$

Здесь мы используем ≈ вместо =, так как k_max - целое число, так что выражение не имеет решения в общем виде. Для Пуассоновского распределения

$1 - P(k_{\max } ) = 1 - e^{ - \left\langle k \right\rangle } \sum\limits_{k = 0}^{k_{\max } } {\frac{{\left\langle k \right\rangle ^k }}{{k!}}} = e^{ - \left\langle k \right\rangle } \sum\limits_{k = k_{\max } + 1}^\infty {\frac{{\left\langle k \right\rangle ^k }}{{k!}}} \approx e^{ - \left\langle k \right\rangle } \frac{{\left\langle k \right\rangle ^{k_{\max } + 1} }}{{(k_{\max } + 1)!}} \hspace{20 mm} (3 . 27)$

Где последний элемент выражения аппроксимируется к сумме его наибольшего значения.

For N = 109 and 〈k〉 = 1,000, roughly the size and the average degree of the globe’s social network, (3.26) and (3.27) predict kmax = 1,185, indicating that a random network lacks extremely popular individuals, or hubs.

We can use a similar argument to calculate the expected degree of the smallest node, kmin. By requiring that there should be at most one node with degree smaller than kmin we can write

NP(kmin−1)≃1(3.28)

For the Erdős-Rényi network we have

P(kmin−1)=e−⟨k⟩∑k=0kmin−1⟨k⟩kk!(3.29)

Solving (3.28) with N = 109 and 〈k〉 = 1,000 we obtain k_min = 816.

Дополнение В. Гигантская компонента

В этом разделе мы введем новую переменную, предложенную независимо друг от друга Соломонофф и Раппопортом [11], и Эрдёшем и Реньи [2], - возникновение при〈k〉= 1 [33] гигантской компоненты.

Давайте определим u = 1 - N_G /N как часть узлов, не состоящей в гигантской компоненте (GC), размер которой вы определим как NG. Если узел i входит в GC, он должен быть связан с другим узлом j, который так-же принадлежит GC по определению. Таким образом, если i не принадлежит GC, из этого следует:

• Связи между i и j нет (с вероятностью 1-p)
• Либо связь между i и j есть, но j тоже не входит в GC (с вероятностью pu).

Таким образом, общая вероятность того, что i не входит в GC через j равна 1 - p + pu. Следовательно, вероятность того, что она не соединена с GC через любую другую компоненту равна (1 - p + pu)^{N - 1} , при N-1 узлах, которые могут связать i с GC.

Так как u - часть узлов вне GC, для каждого p и N решение формулы

$u = (1 - p + pu)^{N - 1} \hspace{20 mm} (3 . 30)$

Определяет размер гигантской компоненты через N_G = N(1-u). Учитывая что p=/(N-1) и взяв с каждой стороны логарифм, для << N мы получаем

$\ln u = (N - 1)\ln \left[ {1 - \frac{{\left\langle k \right\rangle }}{{N - 1}}(1 - u)} \right] \approx (N - 1)\left[ { - \frac{{\left\langle k \right\rangle }}{{N - 1}}(1 - u)} \right] = - \left\langle k \right\rangle (1 - u) \hspace{20 mm} (3 . 31)$

где для ln(1+x) мы использовали расширение серии.

При получении экспоненты по обе стороны мы получаем u = exp[- 〈k〉(1 - u)]. Если определим часть узлов входящих в GC как S, S = NG / N, тогда S = 1 - u и (3.31) соответствует

$S = 1 - e^{ - \left\langle k \right\rangle S} \hspace{20 mm} (3 . 32)$

Эта формула позволяет получить размер гигантской компоненты S как функцию от (Изображение 3.18). Хотя (3.32) выглядит аналогично, у него нет закрытого решения. Мы можем решить его визуально с помощью графика правой части (3.32) как функции S от различных значений . Для ненулевого решения, полученная кривая должна пересечь пунктирную диагональ, соответствующую левой части (3.32). Для небольших , две кривые пересекаются только для S=0, что означает что для небольших размер гигантской компоненты равен нулю. Не-нулевое решение появляется только когда превышает граничное значение.

Для того, чтобы определить значение , для которого мы получим не-нулевое значение, возьмем производное (3.32), — точка смены фазы окажется там, где правая сторона формулы (3.32) будет иметь ту же производную, что и левая, т.е. когда

$\frac{d}{{dS}}\left( {1 - e^{ - \left\langle k \right\rangle S} } \right) = 1$

При S=0, мы можем вычислить, что таковая точка смены фазы находится на =1 (см. Так-же ДОПОЛНЕНИЕ Д).

Дополнение Г. Размер Компоненты

На изображении 3.7 мы исследовали размер гигантской компоненты, игнорируя другой важный вопрос: Сколько компонент мы расчитываем иметь для ‹k›? Каково их распределение размеров? В этом разделе мы отвечаем на эти вопросы.

Распределение размеров компонент

Для случайной сети вероятность случайного узла принадлежать компоненте размером s (не соответствующей гигантской компоненте G) равна [33]

$p_s \sim \frac{{\left( {s\left\langle k \right\rangle } \right)^{s - 1} }}{{s!}}e^{ - \left\langle k \right\rangle s} \hspace{20 mm} (3 . 34)$

Заменив ‹k›^s-1 выражением exp[(s-1) ln‹k›] и используя формула Стирлинга

$s! = \sqrt {2\pi s} \left( {\frac{s}{e}} \right)^s$

Для больших S мы получаем

$p_s \sim s^{ - 3/2} e^{ - (\left\langle k \right\rangle - 1)s + (s - 1)\ln \left\langle k \right\rangle } \hspace{20 mm} (3 . 35)$

Следовательно распределение размеров определяется двумя факторами: медленно уменьшающимся параметром степенным параметром s^-3/2 и быстро уменьшающимся экспоненциальным фактором e ^{-(‹k›-1)s+(s-1)ln‹k›} . Учитывая доминантность экспоненциального параметра для больших s, (3.35) предсказывает отсутствие больших компонент. В критической точке, ‹k› = 1, все экспоненциальные факторы отменяются, и распределение соответствует степенному фактору

$p_s \sim s^{ - 3/2} \hspace{20 mm} (3 . 36)$

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

Средний размер компонент

Наш рассвет так-же показывает что средний размер компоненты (опять же, за исключением гигантской компоненты) соответствует [33]

$\left\langle s \right\rangle = \frac{1}{{1 - \left\langle k \right\rangle + \left\langle k \right\rangle N_G /N}} \hspace{20 mm} (3 . 37)$

Для ‹k› ‹ 1 гигантской компоненты не существует (NG = 0), следовательно (3.37) сводится к

$\left\langle s \right\rangle = \frac{1}{{1 - \left\langle k \right\rangle }} \hspace{20 mm} (3 . 38)$

Это выражение расходится при приближении средней степени к критической точке =1. Таким образом, при приближении к критической точке размер кластеров увеличивается, обозначение возникновение гигантской компоненты при ‹k› = 1. Эти предсказания подтверждаются симуляциями при больших N (Изображение 3.20).

Для определения среднего размера компонент при

‹k› › 1 используя (3.37), начнем с расчета размера гигантской компоненты. Этот шаг может быть исполнен независимо, указывая на уменьшение среднего размера кластера при ‹k› › 1, так как большинство кластеров поглотила гигантская компонента.

Заметьте что (3.37) предсказывает размер компонента соответствующего случайно выбранному узлу. Эта метрика неравноправна, так как шанс принадлежать большому кластеру выше, нежели маленькому. “Предвзятость” метрики линейно зависима от размера кластера s. При поправке на предвзятость, получим средний размер малых компонент, такой как если бы мы проверяли кластеры вручную, один за одним [33]

$\left\langle {s'} \right\rangle = \frac{2}{{2 - \left\langle k \right\rangle + \left\langle k \right\rangle N_G /N}} \hspace{20 mm} (3 . 39)$

Изображение 3.20 представляет подтверждение (3.39) через симуляции.

Дополнение Е. Фазовый переход

Возникновение гигантской компоненты при ‹k›=1 в случайной сети - пример фазового перехода, феномена хорошо изученного в физике и химии [35]. Посмотрим на примеры:

• Переход Вода-Лед (Изображение 3.21a): При высоких температурах молекулы H²O активно перемещаются, формируя небольшие группы и отделяясь, для того чтобы соединиться с в группу с другими молекулами. С охлаждением, при температуре 0˚C молекулы внезапно останавливают этот танец переходов, формируя упорядоченные и жесткие кристаллы льда.
• Магнетизм (Изображение 3.21b): В ферромагнетиках, таких как железо, при высоких температурах спины направленны в случайных направлениях. При определенной критическое температуре T_c все атомы разворачиваются спинами в одном направлении, и металл превращается в магнит.

Замерзание жидкости и возникновение магнетизма - примеры фазового перехода, соответствующего переходу от хаоса к порядку. Действительно, по сравнению с упорядоченной структурой кристаллов льда, жидкая вода представляется достаточно хаотичной. Аналогично, случайно направленные магнитные оси атомов в ферромагнитных принимают упорядоченное состояние при T_c.

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

Феномен, наблюдаемый около критической точки ‹k› = 1 в случайной сети во многом соответствует фазовому переходу:

• Схожесть между Изображением 3.7а и диаграммой магнетизации на Изображении 3.21b неслучайна - обе показывают переход от хаоса к порядку. В случайной сети этот переход соответствует появлению гигантской компоненте при переходе через точку =1.
• При достижении точки замерзания, мы наблюдаем кристаллы льда разнообразных размеров, как и в случае с группами атомов в ферромагнитах, ориентированных вместе. Распределение размеров кристаллов и атомов соответствуют степенному закону. Аналогично, хотя для ‹k› ‹ 1 и ‹k› › 1 размер кластеров соответствует экспоненциальному распределению, прямо в точке перехода p_s соответствует степенному распределения (3.36), означая существование компонент разнообразных размеров.
• В критической точке средний размер кристаллов the ice crystals or of the magnetic domains diverges, assuring that the whole system turns into a single frozen ice crystal or that all spins point in the same direction. Similarly in a random network the average cluster size ‹s› diverges as we approach ‹k› = 1 (Image 3.20).