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

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

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

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

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

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

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

Алгоритм

Watts–Strogatz graph

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

1. Побудуйте правильну кільцеву решітку, графік з $N$ вузлами, кожен з яких з'єднаний з $K$ сусідніми, $K/2$ з кожного боку. Тобто, якщо вузли позначені $n_0\dots n_{N-1}$, є ребро $(n_i,n_j)$ якщо і тільки якщо $0<|i-j|mod(N-1-\frac{K}{2})\le \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\ne i$) та дублювання посилань (немає краю $(n_i,n_{k^{\prime }})$ з $k^{\prime }=k$ в цій точці алгоритму).

Властивості

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

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

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

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

Якщо ми використовуємо міру Barrat і Weigt для кластеризації $C^{\prime }(\beta )$, визначеної як частка між середньою кількістю ребер між сусідами вузла та середньою кількістю можливі краї між цими сусідами або, альтернативно,

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

то ми отримаємо $C^{\prime }(\beta )\sim C(0)(1-\beta {)}^3.$

Розподіл ступеня

Розподіл ступенів у випадку кільцевої решітки є просто дельта-функцією Дірака, центрованою в $K$. У граничному випадку $\beta \to 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\ge K/2$ та $f(k,K)=\min (k-K/2,K/2)$. Форма розподілу ступенів аналогічна розподілу ступеня і має яскраво виражений пік при $k=K$ і розпадається експоненціально для великих $|k-K|$. Топологія мережі є відносно однорідною, і всі вузли більш-менш однакові.

Обмеження

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

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

Див. також

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