Малі світлові мережі: від упорядкованої решітки до випадкового шляху

Два екстреми, і дивовижне між ними

Візьміть n точок, розташованих на кільці, та з’єднайте кожну точку зі своїми k найближчими сусідами. Це регулярна решітка дуже кластерна — ваші сусіди також є сусідами один одного — але вона повільна у перетині: досягнення точки приблизно на половині кільця займає приблизно n/2k кроків. Тепер переналаштуйте кожен край до випадкового кінцевого пункту, рівномірно розподіленого. Це випадковий граф (Ердеш-Ренеґі) є протилежністю: майже немає кластеризації, але середній найкоротший шлях між будь-якими двома вузлами скорочується до приблизно log(n)/log(k), оскільки випадкові довгі відстані майже миттєво з’являються.

У 1998 році Донан Уоттс і Стівен Строґац запитали, що відбувається між ними, і відповідь пояснила те, що заплутувало соціологів з часів експерименту «шість ступенів» листа Стэнлі Мілграма 1967 року: реальні соціальні мережі одночасно дуже кластерні та мають короткі шляхи, які не могли разом пояснити два підручних екстреми.

Процедура перепідключення

Конструкція Watts-Strogatz починається з кільцевої решітки, а потім для кожного краю виконується перепідключення до випадкового нового кінцевого вузла з ймовірністю p, зберігаючи зв’язність графа:

для кожного вузла i в кільці: для кожного з його k/2 годинникових напрямків від краю (i, j): з ймовірністю p: вибрати випадковий вузол j', який не є вже суміжним з i замінити край (i, j) краєм (i, j')

При p = 0 нічого не перепідключається: чиста решітка, високий коефіцієнт зв’язності C, довга довжина шляху L. При p = 1 кожен край випадковим чином змінюється: чистий випадковий граф, низький C, коротка L. Інтересний режим – вузьке вікно малого p — часто лише кілька відсотків країв, де L майже зникає до значення випадкового графа, а C майже не падає від значення решітки. Невелика кількість перепідключених довгих відстаней достатньо, щоб пробити короткі шляхи по всьому кільцю, тоді як більшість локальної зв’язності, яку ці кілька країв не торкнулися, залишається без змін.

for each node i in the ring:
  for each of its k/2 clockwise edges (i, j):
    with probability p:
      pick a random node j' not already adjacent to i
      replace edge (i, j) with edge (i, j')

Вимірювання: C та L

Коефіцієнт кластеризації вузла – це частка його сусідніх пар, які самі з’єднані — скільки ваших друзів знають один одного. Середня довжина шляху L – це середнє число стрибків найкоротшим шляхом між усіма парами вузлів. Watts та Strogatz показали, що коли p збільшується від 0, L різко падає майже одразу (кілька довгобічнихshortcutів впливають на величезну кількість найкоротших шляхів), а C зменшується лише поступово, приблизно лінійно з p, оскільки більшість трикутників не торкаються рідкісних перемикань.

C(p) / C(0)  and  L(p) / L(0)   plotted against p (log scale)
p=0.0001 : C/C(0) ≈ 1.00   L/L(0) ≈ 1.00   (still a lattice)
p=0.01   : C/C(0) ≈ 0.95   L/L(0) ≈ 0.20   (small-world regime)
p=1.0    : C/C(0) ≈ 0.02   L/L(0) ≈ 0.04   (random graph)

Значення, що виходить за рамки соціальних граф

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

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Small-World Networks і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.