🕸️ Мережі малого світу — Воттс-Строгатц

Мережа малого світу — це граф, що поєднує високу локальну кластеризацію, як у регулярній решітці, з короткими середніми довжинами шляхів між будь-якими двома вузлами, як у випадковому графі. Воттс і Строгатц представили її у 1998 році, щоб пояснити, чому реальні мережі, як-от дружні зв'язки чи електромережі, одночасно локально «кланові» та глобально добре з'єднані.

Модель починається з кільцевої решітки, де кожен вузол з'єднаний зі своїми k найближчими сусідами. Потім вона проходить кожне ребро і з імовірністю p переприв'язує один його кінець до випадкового вузла в іншому місці кільця, уникаючи петель і дублікатів. При p = 0 нічого не змінюється; при p = 1 майже всі ребра стають випадковими скороченнями.

N встановлює кількість вузлів (від 10 до 80), k встановлює, скількома найближчими сусідами кожен вузол з'єднаний спочатку (від 2 до 10, завжди парне число), а p встановлює ймовірність переприв'язки від 0 до 1. Зміна N або k перебудовує решітку, тоді як зміна p повторно виконує переприв'язку і перераховує статистику в реальному часі.

Коефіцієнт кластеризації вузла — це частка пар його сусідів, які також безпосередньо з'єднані, обчислена як 2, помножене на кількість зв'язків між сусідами, поділене на k, помножене на (k мінус один). C — це середнє значення цього показника по всіх вузлах, у діапазоні від 0 до 1. Високий C означає, що ваші друзі, як правило, знають одне одного.

L — це середня кількість ребер на найкоротшому маршруті між парами вузлів, знайдена запуском пошуку в ширину з кожного вихідного вузла. Для швидкості симуляція вибирає до 20 вихідних вузлів замість усіх, що дає точну оцінку L без обчислення кожної пари на великих графах.

При малому, але ненульовому p, лише кілька далекосяжних скорочень різко зменшують середню довжину шляху L, тоді як локальна кластеризація C майже не падає. Мережа зберігає свої тісно пов'язані околиці, але стає глобально навігованою за дуже небагато кроків. Значок позначає цей режим, коли p приблизно між 0.01 і 0.3.

Це кластеризація та довжина шляху, поділені на їхні значення для початкової непереприв'язаної решітки (p = 0). Побудова цих нормалізованих співвідношень виявляє характерний провал малого світу: L/L0 різко падає зі зростанням p, тоді як C/C0 залишається близько одиниці до значно вищого p, залишаючи широкий розрив між двома кривими.

Так, вона слідує стандартній процедурі Воттса-Строгатца: k-регулярна кільцева решітка, переприв'язана ребро за ребром з імовірністю p. Формули кластеризації та довжини шляху BFS точні, хоча довжина шляху використовує випадкову вибірку джерел для продуктивності, тож значення трохи коливаються між запусками з однаковими налаштуваннями.

Це поширена ідея про те, що будь-які дві людини пов'язані ланцюжком приблизно з шести знайомих. Структура малого світу робить це правдоподібним: розріджена соціальна мережа лише з помірною кількістю випадкових далекосяжних зв'язків має середню довжину шляху, яка зростає дуже повільно, приблизно логарифмічно, з розміром популяції.

Вони зустрічаються в багатьох системах, включно з нейронними з'єднаннями мозку, електромережею, графом співпраці акторів, всесвітньою павутиною та мережами білок-білкових взаємодій. Ця структура підтримує швидке поширення інформації чи сигналу, зберігаючи водночас стійкі локальні спільноти, тому вона так широко повторюється в природі й технологіях.