🔗 Шість рукостискань — Мережі малого світу

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

В алгоритмі Уоттса-Строгаца p — це ймовірність того, що кожне ребро початкової кільцевої решітки від'єднується від одного кінця й приєднується до випадково обраного вузла натомість. При p = 0 мережа є чистою регулярною решіткою з довгими шляхами й високою кластеризацією. При p = 1 вона стає, по суті, випадковим графом із короткими шляхами, але низькою кластеризацією. Поведінка малого світу — короткі шляхи й висока кластеризація разом — виникає у вузькому проміжному діапазоні, часто вже при p від 0.01 до 0.1.

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

Середня довжина шляху — це середня кількість ребер на найкоротшому маршруті між усіма парами вузлів мережі. Це важливо, бо визначає, як швидко інформація, хвороба чи вплив можуть поширюватися системою. У чистій кільцевій решітці з кількох сотень вузлів середня довжина шляху зростає приблизно лінійно з розміром мережі, роблячи мережу функціонально «великою». Додавання лише кількох випадкових скорочень змушує середню довжину шляху зростати лише логарифмічно з розміром, тому величезні соціальні мережі все ж можна пройти за кілька кроків.

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

Дункан Уоттс, тоді аспірант, та його науковий керівник Стівен Строгац, прикладний математик у Корнельському університеті, опублікували «Collective dynamics of 'small-world' networks» у Nature 1998 року. Вони представили просту алгоритмічну модель — почати з регулярної кільцевої решітки й перез'єднати кожне ребро з ймовірністю p — і показали обчислювально, що вузький діапазон p дає мережі з короткою середньою довжиною шляху та високою кластеризацією одночасно, що відповідає властивостям, які спостерігаються в реальних мережах, як-от електромережа західної частини США та нейронна мережа нематоди C. elegans.

Структура малого світу задокументована в надзвичайно широкому спектрі систем: соціальних і дружніх мережах, графах наукової співпраці й цитування, нейронних з'єднаннях мозку, включно з C. elegans, великих енергетичних мережах, топології інтернету на рівні маршрутизаторів та мережах співпраці кіноакторів — основі популярної гри «Шість рукостискань Кевіна Бейкона», де майже будь-якого актора можна пов'язати з Кевіном Бейконом коротким ланцюжком спільних фільмів.

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

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

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