Loading AI tools
З Вікіпедії, вільної енциклопедії
Модель Воттса-Строгаца — це модель генерації випадкових графів, яка створює графи з властивостями тісного світу, зокрема з короткою середньою довжиною шляху та високою кластеризацією. Модель була запропонована Данканом Дж. Воттсом[en] та Стівеном Строгацом у їх спільній статті в журналі Nature 1998 року.[1] Модель також відома як (Watts) бета модель після того, як Воттс використовував для опису моделі в своїй популярній науковій книзі Six Degrees[en].
Формальне вивчення випадкових графів датується роботою Пала Ердеша та Альфреда Реньї[2]. Графи, які вони розглядали, тепер відомі як класичні графи або модель Ердеша — Реньї, пропонують просту та потужну модель з багатьма додатками.
Проте модель Ердеша — Реньї не має двох важливих властивостей, що спостерігаються в багатьох реальних мережах:
Модель Ердеша — Реньї була спроектована як найпростіша модель, яка стосується першого з двох обмежень. Це припускає кластеризацію, зберігаючи короткі довжини шляху моделі Ердеша-Реньї. Це відбувається шляхом інтерполяції між ЕР-графіком і регулярною кільцевою решіткою. Отже, модель здатна принаймні частково пояснити «малі світові» явища в різних мережах, таких як енергетична мережа, нейронна мережа C elegans та мережа кіноакторів. У 2015 році дослідники з Каліфорнійського технологічного інституту та Принстонського університету показали, що модель Воттса-Строгаца пояснює зв'язок жирового обміну в дріжджах[4], що починають жити.
Враховуючи бажану кількість вузлів , означає ступінь (вважається рівним цілим числом) і спеціальний параметр , що задовольняє ( i . Модель конструює неорієнтований граф з -вузлами та зв'язками за таким чином:
Основна решітка структури моделі створює локально кластеризовану мережу, а випадкові зв'язки різко зменшують середню довжину шляху. Алгоритм представляє решітчастих країв. Різні дозволяє інтерполювати між регулярною ґраткою () і випадковим графіком () наближаючись до випадкового графа Ердеша-Реньї з і .
Три цікаві властивості — це середня довжина шляху, високий коефіцієнт кластеризації та розподіл ступеня.
Для кільцевої решітки середня довжина шляху становить і масштабується лінійно з розміром системи. У граничному випадку граф сходиться до класичного випадкового графа з . Проте в проміжній області середня довжина шляху падає дуже швидко з збільшенням , швидко наближаючись до його граничного значення.
Для кільцевої решітки коефіцієнт кластеризації[5] , і тому має тенденцію до , оскільки зростає незалежно від розміру системи.[6] У граничному випадку коефіцієнт кластеризації досягає значення для класичних випадкових графів і, таким чином, обернено пропорційний розміру системи. У проміжному регіоні коефіцієнт кластеризації залишається досить близьким до його значення для звичайної решітки і лише падає при відносно високому (\ displaystyle \ beta) \ beta. Це призводить до регіону, де середня довжина шляху швидко падає, але коефіцієнт кластеризації не пояснюється явищем «малого світу».
Розподіл ступенів у випадку кільцевої решітки є просто дельта-функцією Дірака, центрованою в . У граничному випадку це розподіл Пуассона, як з класичними графіками. Розподіл ступенів для можна записати як,[6]
де — це кількість ребер, які мають вузол або її ступінь. Тут та . Форма розподілу ступенів аналогічна розподілу ступеня і має яскраво виражений пік при і розпадається експоненціально для великих . Топологія мережі є відносно однорідною, і всі вузли більш-менш однакові.
Основним обмеженням моделі є те, що він виробляє нереальний ступінь вершини. На відміну від цього, реальні мережі часто безмаштабні мережі, неоднорідні в ступені, мають концентратори та безмаштабний розподіл ступенів. Такі мережі краще описуються в цьому відношенні переважним сімейством моделей приєднання, такими як модель Барабаші-Альберта (БА). (З іншого боку, модель Барабаші-Альберт не здатна забезпечити високий рівень кластеризації в реальних мережах, це недолік, який не використовується моделями Воттса-Строгаца. Таким чином, ні модель Воттса-Строгаца, ні модель Барабаші-Альберт не можна вважати цілком реалістичними.)
Модель Воттса-Строгаца також передбачає фіксовану кількість вузлів і, таким чином, не може бути використана для моделювання зростання мережі.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.