Модель Воттса — Строгаца

Модель Воттса-Строгаца — це модель генерації випадкових графів, яка створює графи з властивостями тісного світу, зокрема з короткою середньою довжиною шляху та високою кластеризацією. Модель була запропонована Данканом Дж. Воттсом та Стівеном Строгацом у їх спільній статті в журналі Nature 1998 року. Модель також відома як (Watts) бета модель після того, як Воттс використовував $\beta$ для опису моделі в своїй популярній науковій книзі Six Degrees.

Обґрунтування для моделі

Формальне вивчення випадкових графів датується роботою Пала Ердеша та Альфреда Реньї. Графи, які вони розглядали, тепер відомі як класичні графи або модель Ердеша — Реньї, пропонують просту та потужну модель з багатьма додатками.

Проте модель Ердеша — Реньї не має двох важливих властивостей, що спостерігаються в багатьох реальних мережах:

1. Вони не генерують місцеві кластери та тріадичні замикання. Натомість, оскільки вони мають постійну, випадкову та незалежну ймовірність підключення двох вузлів, модель Ердеша — Реньї має низький коефіцієнт кластеризації.
2. Вони не враховують утворення вузлів. Формально ступінь вершини розподілу графа Ердеша-Реньї сходиться до розподілу Пуассона, а не до закону потужності, що спостерігається в багатьох реальних безмасштабних мережах.

Модель Ердеша — Реньї була спроектована як найпростіша модель, яка стосується першого з двох обмежень. Це припускає кластеризацію, зберігаючи короткі довжини шляху моделі Ердеша-Реньї. Це відбувається шляхом інтерполяції між ЕР-графіком і регулярною кільцевою решіткою. Отже, модель здатна принаймні частково пояснити «малі світові» явища в різних мережах, таких як енергетична мережа, нейронна мережа C elegans та мережа кіноакторів. У 2015 році дослідники з Каліфорнійського технологічного інституту та Принстонського університету показали, що модель Воттса-Строгаца пояснює зв'язок жирового обміну в дріжджах, що починають жити.

Алгоритм

Watts–Strogatz graph

Враховуючи бажану кількість вузлів $N$, означає ступінь $K$ (вважається рівним цілим числом) і спеціальний параметр $\beta$, що задовольняє ($0\leq \beta \leq 1$ i $N\gg K\gg \ln N\gg 1$. Модель конструює неорієнтований граф з $N$-вузлами та ${\frac {NK}{2}}$ зв'язками за таким чином:

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

Властивості

Основна решітка структури моделі створює локально кластеризовану мережу, а випадкові зв'язки різко зменшують середню довжину шляху. Алгоритм представляє $\beta {\frac {NK}{2}}$ решітчастих країв. Різні $\beta$ дозволяє інтерполювати між регулярною ґраткою ($\beta =0$) і випадковим графіком ($\beta =1$) наближаючись до випадкового графа Ердеша-Реньї $G(n,p)$ з $n=N$ і $p={\frac {NK}{2{N \choose 2}}}$.

Три цікаві властивості — це середня довжина шляху, високий коефіцієнт кластеризації та розподіл ступеня.

Середня довжина шляху

Для кільцевої решітки середня довжина шляху становить $\ell (0)=N/2K\gg 1$ і масштабується лінійно з розміром системи. У граничному випадку $\beta \rightarrow 1$ граф сходиться до класичного випадкового графа з $\ell (1)={\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(1)=K/N$ і, таким чином, обернено пропорційний розміру системи. У проміжному регіоні коефіцієнт кластеризації залишається досить близьким до його значення для звичайної решітки і лише падає при відносно високому (\ displaystyle \ beta) \ beta. Це призводить до регіону, де середня довжина шляху швидко падає, але коефіцієнт кластеризації не пояснюється явищем «малого світу».

Якщо ми використовуємо міру Barrat і Weigt для кластеризації $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$. У граничному випадку $\beta \rightarrow 1$ це розподіл Пуассона, як з класичними графіками. Розподіл ступенів для $0<\beta <1$ можна записати як,

$P(k)=\sum _{n=0}^{f(k,K)}C_{K/2}^{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|$. Топологія мережі є відносно однорідною, і всі вузли більш-менш однакові.

Обмеження

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

Модель Воттса-Строгаца також передбачає фіксовану кількість вузлів і, таким чином, не може бути використана для моделювання зростання мережі.

Див. також

• Світ тісний (граф)
• Граф Радо
• Модель Ердеша — Реньї
• Модель Барабаші — Альберт
• Соціальна мережа