< Попер   ЗМІСТ   Наст >

Сети малого мира Ваттса - Строгатца

В 70-е года прошлого века американский психолог Милграм (Milgram) провел интересное исследование. Он задался вопросом, каково "расстояние" между двумя случайно выбранными людьми. Под расстоянием понимается количество знакомств, необходимое для установления связи между данными людьми. Милграм поступил следующим образом - поскольку он жил в Бостоне, то был выбран далекий от Бостона город - Небраска, и случайно выбранным людям были розданы конверты, которые нужно было передать в Бостон. Конверты можно было передавать только через своих знакомых и родственников. Милграм получил весьма неожиданный результат: в среднем каждый конверт прошел через шесть человек. Так и родилась теория "шести рукопожатий". Т.е. каждый человек связан с любым другим цепью не больше шести личных знакомств. В этом смысле о нашем мире говорят как о малом мире - "small world".

Модель перехода от большого (регулярного) мира к малому предложили Ваттс (Watts) и Строгац (Strogatz). Эта модель представляет собой одномерную регулярную решетку, состоящую из N узлов, где каждый узел соединен только со своими k ближайшими соседями и наложены периодические граничные условия, т.е. решетку свернули в кольцо, см. рис. 1.2.3. После чего каждую связь с вероятностью f <<С 1 перебрасывали на другой случайно выбранный узел. Правда при такой процедуре есть вероятность появления изолированных узлов.

Пример малого мира с тремя перебросами ( N = 16): а - каждый узел соединен со своими ближайшими соседями (к = 2), б - каждый узел соединен с четырьмя соседями (к = 4)

Рис. 1.2.3 - Пример малого мира с тремя перебросами ( N = 16): а - каждый узел соединен со своими ближайшими соседями (к = 2), б - каждый узел соединен с четырьмя соседями (к = 4)

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

связей есть:

Для удобства опустим двойку в знаменателе и определим д как:

Для k > 2 естественное обобщение дает:

Так как существует только один характерный размер системы X, то и безразмерное отношение среднего расстояния между узлами графа к числу всех узлов графа 1N может зависеть только от безразмерной величины Ы/X-Т.е. можно написать:

где f (x) - скейлинговая функция со следующими асимптотиками:

Как уже упоминалось выше, существует много способов определения корреляционного радиуса. Предположим что

Покажем с помощью ренорм-группового преобразования (для к = 2) что Т = 1. Итак пусть имеем:

Выполним ренорм-групповое преобразование, показанное на рис. 1.2.4, а именно: объединим в пары соседние узлы в графе, при этом в новом графе узлы соединены добавленной связью, если в исходном графе такая связь была хотя бы у одной из пар.

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

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

При таком преобразовании с очевидностью можно

записать, что:

где штрихованные величины относятся к правому графу на рис. 1.2.4.

Также понятно, что и среднее минимальное расстояние в новом графе / будет отличаться в два раза.

Подставляя (1.2.33) и (1.2.34) в (1.2.32) получаем:

Для к > 2 можно провести аналогичное преобразование, только теперь необходимо группировать не по два узла, а по к/ 2 узлов. Результат естественно остается тем же - Т = 1.

Выше описанную модель малого мира можно обобщить на большие размерности. Так, например, в двумерном случае это может быть регулярная квадратная решетка с дополнительными связями, как показано на рис. 1.2.5. Здесь далее под к понимается степень узла, т.е. число ближайших соседей. Но нужно иметь в виду, что в литературе при описании малого мира под к часто понимают количество соседей в одном направлении.

Пример двумерного ( d = 2) малого мира, к = 4 .

Рис. 1.2.5 - Пример двумерного ( d = 2) малого мира, к = 4 .

Тогда вместо (1.2.29) будем иметь:

где - d размерность малого мира. И выражение (1.2.30) примет вид:

Для одномерного малого мира можно найти в явном виде кластерность С и средне минимальное расстояние 1 для малого мира, приведем конечные выражения:

и

Как и должно быть при записи выражения (1.2.39) в форме (1 .2.38), функция / (х) имеет следующие асимптотики:

На рис. 1.2.6. приведены графики нормированных зависимостей кластерности С и среднего расстояния 1 от концентрации перебросов р.

Подробнее о скейлинге в малом мире можно прочитать здесь:

M. E. J. Newman and D. J. Watts. Scaling and percolation in the small-world network model. Phys. Rev. E 60, 7332-7342 (1999) (arXiv: 9904419v2).

О ренорм-групповом преобразовании можно прочитать здесь: Newman M. E. J., Watts D. J. Renormalization group analysis of the small-world network mode. Phys. Lett. A 263, 341-346 (1999).

Пунктирная линия - нормированная кластерность. Сплошная линия - нормированное средне минимальное расстояние.

Рис. 1.2.6 - Пунктирная линия - нормированная кластерность. Сплошная линия - нормированное средне минимальное расстояние.

Нормировка происходит на регулярный граф (без перебросов) -

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

Подробный вывод формулы (1.2.41) основанный на приближении теории среднего поля описан здесь: "Mean-field solution of the small-world network model" - M. E. J. Newman, C. Moore and D. J. Watts, Phys. Rev. Lett. 84, 3201-3204 (2000) (arXiv: 9909165v2).

 
< Попер   ЗМІСТ   Наст >