Модель Уоттса – Строгаца

Модель маленького мира Уоттса-Строгаца, созданная с помощью igraph и визуализированная с помощью Cytoscape 2.5. 100 узлов.

Модель Уоттса-Строгаца — это модель генерации случайных графов , которая создает графы со свойствами маленького мира , включая короткие средние длины путей и высокую кластеризацию . Его предложили Дункан Дж. Уоттс и Стивен Строгац в своей статье, опубликованной в 1998 году в научном журнале Nature . Модель также стала известна как бета- модель (Уоттса) после того, как Уоттс использовал $\beta$ сформулировать его в своей научно-популярной книге «Шесть градусов» .

Обоснование модели

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

Однако ER -графы не обладают двумя важными свойствами, наблюдаемыми во многих реальных сетях:

1. Они не создают локальную кластеризацию и триадные замыкания . Вместо этого, поскольку они имеют постоянную, случайную и независимую вероятность соединения двух узлов, ER-графы имеют низкий коэффициент кластеризации .
2. Они не учитывают образование хабов. Формально распределение степеней ER-графов сходится к распределению Пуассона , а не к степенному закону, наблюдаемому во многих реальных безмасштабных сетях .

Модель Уоттса и Строгаца была разработана как простейшая модель, устраняющая первое из двух ограничений. Он учитывает кластеризацию, сохраняя при этом короткие средние длины пути модели ER. Это достигается путем интерполяции между рандомизированной структурой, близкой к ER-графам, и регулярной кольцевой решеткой . Следовательно, модель способна, по крайней мере частично, объяснить явления «тесного мира» в различных сетях, таких как энергосистема, нейронная сеть C. elegans , сети киноактеров или коммуникация метаболизма жиров у почкующихся дрожжей. .

Алгоритм

График Уоттса – Строгаца

Учитывая желаемое количество узлов $N$, средняя степень $K$ (предполагается, что это четное целое число) и параметр $\beta$, все устраивает $0\leq \beta \leq 1$ и $N\gg K\gg \ln N\gg 1$, модель строит неориентированный граф с $N$ узлы и ${\frac {NK}{2}}$ края следующим образом:

1. Постройте регулярную кольцевую решетку — граф с $N$ узлы, каждый из которых подключен к $K$ соседи, $K/2$ с каждой стороны. То есть, если узлы помечены $0\ldots {N-1}$, есть грань $(i,j)$ тогда и только тогда, когда $0<|i-j|\ \mathrm {mod} \ \left(N-1-{\frac {K}{2}}\right)\leq {\frac {K}{2}}.$
2. Для каждого узла $i=0,\dots ,{N-1}$ возьмите каждое ребро, соединяющее $i$ своему $K/2$ крайние правые соседи, то есть каждое ребро $(i,j)$ такой, что $0<(j-i)\ \mathrm {mod} \ N\leq K/2$, и перемонтировать его с вероятностью $\beta$. Перепрошивка производится заменой $(i,j)$ с $(i,k)$ где $k$ выбирается равномерно случайным образом из всех возможных узлов, избегая при этом циклов ( $k\neq i$) и дублирование ссылок (нет края $(i,{k'})$ с $k'=k$ на этом этапе алгоритма).

Характеристики

Базовая решетчатая структура модели создает локально кластеризованную сеть, в то время как случайно перемонтированные каналы значительно сокращают среднюю длину пути . Алгоритм знакомит с $\beta {\frac {NK}{2}}$ таких нерешетчатых ребер. Варьируясь $\beta$ позволяет интерполировать между регулярной решеткой ( $\beta =0$) и структуру, близкую к случайному графу Эрдеша–Реньи $G(N,p)$ с $p={\frac {K}{N-1}}$ в $\beta =1$. Она не соответствует реальной модели ER, поскольку каждый узел будет подключен как минимум к $K/2$ другие узлы.

Три свойства, представляющие интерес, — это средняя длина пути , коэффициент кластеризации и распределение степеней .

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

Для кольцевой решетки средняя длина пути является $\ell (0)\approx N/2K\gg 1$ и масштабируется линейно с размером системы. В предельном случае $\beta \rightarrow 1$, граф приближается к случайному графу с $\ell (1)\approx {\frac {\ln N}{\ln K}}$, но фактически к нему не сходится. В промежуточном регионе $0<\beta <1$, средняя длина пути очень быстро падает с увеличением $\beta$, быстро приближаясь к своему предельному значению.

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

Для кольцевой решетки коэффициент кластеризации $C(0)={\frac {3(K-2)}{4(K-1)}}$и поэтому имеет тенденцию $3/4$ как $K$ растет независимо от размера системы. В предельном случае $\beta \rightarrow 1$ коэффициент кластеризации того же порядка, что и коэффициент кластеризации классических случайных графов, $C=K/(N-1)$ и, таким образом, обратно пропорциональна размеру системы. В промежуточной области коэффициент кластеризации остается достаточно близким к своему значению для регулярной решетки и падает лишь при относительно высоких $\beta$. Это приводит к появлению области, в которой средняя длина пути быстро падает, а коэффициент кластеризации - нет, что объясняет феномен «тесного мира».

Если мы воспользуемся Барратом и Вейгтом мера кластеризации $C'(\beta )$ определяется как доля между средним количеством ребер между соседями узла и средним количеством возможных ребер между этими соседями, или, альтернативно,

$C'(\beta )\equiv {\frac {3\times {\text{number of triangles}}}{\text{number of connected triples}}}$

тогда мы получим $C'(\beta )\sim C(0)(1-\beta )^{3}.$

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

Распределение степеней в случае кольцевой решетки представляет собой просто дельта-функцию Дирака с центром в точке $K$. Распределение степеней для большого числа узлов и $0<\beta <1$ можно записать как,

$P(k)\approx \sum _{n=0}^{f(k,K)}{{K/2} \choose {n}}(1-\beta )^{n}\beta ^{K/2-n}{\frac {(\beta K/2)^{k-K/2-n}}{(k-K/2-n)!}}e^{-\beta K/2},$

где $k_{i}$ - это количество ребер, которые $i^{\text{th}}$ узел имеет или свою степень. Здесь $k\geq K/2$, и $f(k,K)=\min(k-K/2,K/2)$. Форма распределения степеней аналогична форме случайного графика и имеет ярко выраженный пик при $k=K$ и экспоненциально затухает при больших $|k-K|$. Топология сети относительно однородна, что означает, что все узлы имеют одинаковую степень.

Ограничения

Основным ограничением модели является то, что она дает нереалистичное распределение степеней . Напротив, реальные сети часто представляют собой безмасштабные сети, неоднородные по степени, имеющие концентраторы и безмасштабное распределение степеней. В этом отношении такие сети лучше описываются семейством моделей предпочтительного прикрепления , такими как модель Барабаши-Альберта (BA) . (С другой стороны, модель Барабаши-Альберта не может обеспечить высокий уровень кластеризации, наблюдаемый в реальных сетях, и этот недостаток не свойственен модели Уоттса и Строгаца. Таким образом, ни модель Уоттса-Строгаца, ни модель Барабаши-Альберта не должны считать вполне реалистичным.)

Модель Уоттса и Строгаца также предполагает фиксированное количество узлов и поэтому не может использоваться для моделирования роста сети.

См. также

• Сети маленького мира
• Модель Эрдеша – Реньи (ER)
• Модель Барабаши – Альберта
• Социальные сети