Модель Воттса — Строгаца — Вікіпедія
Модель Воттса-Строгаца — це модель генерації випадкових графів, яка створює графи з властивостями тісного світу, зокрема з короткою середньою довжиною шляху та високою кластеризацією. Модель була запропонована Данканом Дж. Воттсом[en] та Стівеном Строгацом у їх спільній статті в журналі Nature 1998 року.[1] Модель також відома як (Watts) бета модель після того, як Воттс використовував для опису моделі в своїй популярній науковій книзі Six Degrees[en].
Формальне вивчення випадкових графів датується роботою Пала Ердеша та Альфреда Реньї[2]. Графи, які вони розглядали, тепер відомі як класичні графи або модель Ердеша — Реньї, пропонують просту та потужну модель з багатьма додатками.
Проте модель Ердеша — Реньї не має двох важливих властивостей, що спостерігаються в багатьох реальних мережах:
- Вони не генерують місцеві кластери та тріадичні замикання[en]. Натомість, оскільки вони мають постійну, випадкову та незалежну ймовірність підключення двох вузлів, модель Ердеша — Реньї має низький коефіцієнт кластеризації.
- Вони не враховують утворення вузлів. Формально ступінь вершини розподілу графа Ердеша-Реньї сходиться до розподілу Пуассона, а не до закону потужності, що спостерігається в багатьох реальних безмасштабних мережах.[3]
Модель Ердеша — Реньї була спроектована як найпростіша модель, яка стосується першого з двох обмежень. Це припускає кластеризацію, зберігаючи короткі довжини шляху моделі Ердеша-Реньї. Це відбувається шляхом інтерполяції між ЕР-графіком і регулярною кільцевою решіткою. Отже, модель здатна принаймні частково пояснити «малі світові» явища в різних мережах, таких як енергетична мережа, нейронна мережа C elegans та мережа кіноакторів. У 2015 році дослідники з Каліфорнійського технологічного інституту та Принстонського університету показали, що модель Воттса-Строгаца пояснює зв'язок жирового обміну в дріжджах[4], що починають жити.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Watts_strogatz.svg/220px-Watts_strogatz.svg.png)
Враховуючи бажану кількість вузлів , означає ступінь (вважається рівним цілим числом) і спеціальний параметр , що задовольняє ( i . Модель конструює неорієнтований граф з -вузлами та зв'язками за таким чином:
- Побудуйте правильну кільцеву решітку, графік з вузлами, кожен з яких з'єднаний з сусідніми, з кожного боку. Тобто, якщо вузли позначені , є ребро якщо і тільки якщо
- Для кожного вузла , з , перемотати його з ймовірністю бета-версія. Перемотування здійснюється шляхом заміни з , де вибирається з рівномірною ймовірністю з усіх можливих значень, які уникають самоплетіння () та дублювання посилань (немає краю з в цій точці алгоритму).
Основна решітка структури моделі створює локально кластеризовану мережу, а випадкові зв'язки різко зменшують середню довжину шляху. Алгоритм представляє решітчастих країв. Різні дозволяє інтерполювати між регулярною ґраткою () і випадковим графіком () наближаючись до випадкового графа Ердеша-Реньї з і .
Три цікаві властивості — це середня довжина шляху, високий коефіцієнт кластеризації та розподіл ступеня.
Для кільцевої решітки середня довжина шляху становить і масштабується лінійно з розміром системи. У граничному випадку граф сходиться до класичного випадкового графа з . Проте в проміжній області середня довжина шляху падає дуже швидко з збільшенням , швидко наближаючись до його граничного значення.
Для кільцевої решітки коефіцієнт кластеризації[5] , і тому має тенденцію до , оскільки зростає незалежно від розміру системи.[6] У граничному випадку коефіцієнт кластеризації досягає значення для класичних випадкових графів і, таким чином, обернено пропорційний розміру системи. У проміжному регіоні коефіцієнт кластеризації залишається досить близьким до його значення для звичайної решітки і лише падає при відносно високому (\ displaystyle \ beta) \ beta. Це призводить до регіону, де середня довжина шляху швидко падає, але коефіцієнт кластеризації не пояснюється явищем «малого світу».
- Якщо ми використовуємо міру Barrat і Weigt[6] для кластеризації , визначеної як частка між середньою кількістю ребер між сусідами вузла та середньою кількістю можливі краї між цими сусідами або, альтернативно,
- то ми отримаємо
Розподіл ступенів у випадку кільцевої решітки є просто дельта-функцією Дірака, центрованою в . У граничному випадку це розподіл Пуассона, як з класичними графіками. Розподіл ступенів для можна записати як,[6]
де — це кількість ребер, які мають вузол або її ступінь. Тут та . Форма розподілу ступенів аналогічна розподілу ступеня і має яскраво виражений пік при і розпадається експоненціально для великих . Топологія мережі є відносно однорідною, і всі вузли більш-менш однакові.
Основним обмеженням моделі є те, що він виробляє нереальний ступінь вершини. На відміну від цього, реальні мережі часто безмаштабні мережі, неоднорідні в ступені, мають концентратори та безмаштабний розподіл ступенів. Такі мережі краще описуються в цьому відношенні переважним сімейством моделей приєднання, такими як модель Барабаші-Альберта (БА). (З іншого боку, модель Барабаші-Альберт не здатна забезпечити високий рівень кластеризації в реальних мережах, це недолік, який не використовується моделями Воттса-Строгаца. Таким чином, ні модель Воттса-Строгаца, ні модель Барабаші-Альберт не можна вважати цілком реалістичними.)
Модель Воттса-Строгаца також передбачає фіксовану кількість вузлів і, таким чином, не може бути використана для моделювання зростання мережі.
- ↑ Watts, D. J.; Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks (PDF). Nature. 393 (6684): 440—442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998. Архів оригіналу (PDF) за 11 квітня 2020. Процитовано 28 листопада 2017.
- ↑ Erdos, P. (1960). Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi. Publ. Math. Inst. Hung. Acad. Sci. 5: 17.
- ↑ Ravasz, E. (30 серпня 2002). Hierarchical Organization of Modularity in Metabolic Networks. Science. 297 (5586): 1551—1555. Bibcode:2002Sci...297.1551R. doi:10.1126/science.1073374.
- ↑ Al-Anzi, Bader; Arpp, Patrick; Gerges, Sherif; Ormerod, Christopher; Olsman, Noah; Zinn, Kai (2015). Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network. PLOS Computational Biology. 11 (5): e1004264. Bibcode:2015PLSCB..11E4264A. doi:10.1371/journal.pcbi.1004264. PMID 26020510.
{{cite journal}}
: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом (посилання) - ↑ Albert, R., Barabási, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics. 74 (1): 47—97. arXiv:cond-mat/0106096. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47.
- ↑ а б в Barrat, A.; Weigt, M. (2000). On the properties of small-world network models (PDF). European Physical Journal B. 13 (3): 547—560. doi:10.1007/s100510050067. Процитовано 26 лютого 2008.[недоступне посилання]