Навчання #42: Наука про мережі — випадкові графи…

1959 року Пол Ердеш і Альфред Реньї поставили оманливо просте запитання: якщо розкидати n вузлів по аркушу й незалежно з'єднати кожну пару з імовірністю p, як виглядатиме отриманий граф? Їхня відповідь, опублікована в серії знакових статей, показала, що випадкові графи зазнають різких, майже розривних фазових переходів — не на відміну від замерзання води — зі зміною ймовірності з'єднання. Через понад шістдесят років ті самі переходи проявляються в надрозповсюдженні COVID-19, крихкості енергомереж і дивовижній стійкості Всесвітньої павутини.

1. Випадкові графи Ердеша–Реньї та гігантська компонента

Канонічна модель Ердеша–Реньї, позначена G(n, p), породжує граф на n вузлах, де кожне ребро існує незалежно з імовірністю p. Очікувана кількість ребер:

E[ребра] = p · n(n−1)/2 ≈ pn²/2

Ключовий керуючий параметр — не сама p, а середній ступінь:

⟨k⟩ = p(n−1) ≈ pn

Коли ⟨k⟩ < 1, граф складається майже виключно з дрібних компонент; найбільша має розмір O(log n). Збільшуйте p, доки ⟨k⟩ > 1, і різко виникає гігантська зв'язна компонента (ГЗК). Для великих n частка вузлів у ГЗК задовольняє неявне рівняння:

S = 1 − e^{−⟨k⟩ S}

Це трансцендентне рівняння має лише тривіальний розв'язок S = 0, коли ⟨k⟩ ≤ 1, але позитивний розв'язок S > 0 виникає з нізвідки в ту саму мить, коли ⟨k⟩ перевищує 1. Перехід справді різкий: точно при ⟨k⟩ = 1 ГЗК має розмір O(n^2/3) — мезоскопічний режим, що зникає в термодинамічній границі.

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

Розподіл ступенів і статистика Пуассона

У великому графі G(n, p) ступінь окремого вузла підпорядковується біноміальному розподілу, який у границі n → ∞ за фіксованого ⟨k⟩ збігається до розподілу Пуассона:

P(ступінь = d) = e^−⟨k⟩ ⟨k⟩^d / d!

Це має важливий наслідок: розподіл Пуассона має експоненційний хвіст, тобто дуже сильно з'єднані вузли (хаби) надзвичайно рідкісні. Реальні мережі, як ми побачимо, поводяться зовсім інакше.

2. Теорія перколяції та стійкість

Теорія перколяції формалізує питання: якщо ми випадково видалимо частку 1 − f вузлів (або ребер), коли мережа перестане мати функціональну гігантську компоненту? Це саме той сценарій, що стосується цілеспрямованих атак на інфраструктуру або природного вибуття індивідів під час епідемії.

Для випадкового графа з пуассонівським розподілом ступенів критична частка присутності, нижче якої ГЗК зникає, дорівнює:

f_c = 1 − 1/⟨k⟩

Іншими словами, для графа із середнім ступенем ⟨k⟩ = 4 потрібно випадково видалити щонайменше 75% вузлів, перш ніж гігантська компонента розпадеться. Випадкові графи напрочуд стійкі до випадкових збоїв, оскільки видалення випадкового вузла з переважною ймовірністю прибирає вузол низького ступеня, що майже не має структурного значення.

Перколяція по зв'язках проти перколяції по вузлах

Моделі перколяції бувають двох видів. У перколяції по вузлах кожен вузол незалежно зайнятий з імовірністю p; у перколяції по зв'язках кожне ребро зберігається з імовірністю p. Обидва варіанти зазнають фазового переходу при критичному порозі p_c, але конкретне значення залежить від ґратки чи топології мережі. Для двовимірної квадратної ґратки:

p_c(вузли) ≈ 0.5927 p_c(зв'язки) = 0.5 (точно)

Нижче p_c виживають лише скінченні кластери. Точно при p_c розподіл розмірів кластерів стає степеневим законом із показником −187/91 у 2D — ознака самоподібної, фрактальної структури в точці критичності.

Фізична аналогія: перколяція на ґратці математично еквівалентна рівноважним властивостям моделі Ізінга для магнетизму — спостереження, яке відкрило глибокий зв'язок між статистичною фізикою та теорією мереж.

3. Безмасштабні мережі: коли хаби змінюють усе

1999 року Альберт-Ласло Барабаші та Река Альберт вивчали топологію Всесвітньої павутини і виявили те, чого Ердеш і Реньї не передбачали: реальні мережі рішуче не є випадковими. Замість пуассонівського розподілу ступенів із чітко визначеним характерним масштабом розподіл ступенів павутини підпорядковувався степеневому закону:

P(k) ∼ k^−γ (зазвичай 2 < γ < 3)

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

Стійкість проти вразливості

Безмасштабні мережі демонструють разючу двоїстість. Вони надзвичайно стійкі до випадкового видалення вузлів — навіть видалення 80% вузлів навмання залишає гігантську компоненту цілою, оскільки ви переважно потрапляєте у вузли низького ступеня. Але вони катастрофічно крихкі за цілеспрямованої атаки: видалення лише верхніх 5% хабів за ступенем розбиває мережу на роз'єднані фрагменти. Це тому, що другий момент розподілу ступенів, ⟨k²⟩, розходиться при γ ≤ 3, тобто поріг перколяції формально зникає:

f_c = 1 − 1/(⟨k²⟩/⟨k⟩ − 1)

Оскільки ⟨k²⟩ → ∞ при γ ≤ 3, критична частка f_c → 1. Безмасштабна мережа з показником у цьому діапазоні теоретично імунна до випадкового відмовлення вузлів — приголомшливий результат із прямими наслідками для архітектури інтернету.

Застосування до епідемій

У моделі епідемії SIR патоген поширюється вздовж ребер контактної мережі. Базове репродуктивне число R₀ критично залежить від топології мережі. Для мережі з розподілом ступенів P(k) епідемічний поріг дорівнює:

R₀ = β / μ · ⟨k²⟩ / ⟨k⟩

де β — швидкість передачі на контакт, а μ — швидкість одужання. Для безмасштабних мереж, де ⟨k²⟩ розходиться, це означає, що R₀ > 1 для будь-якої ненульової швидкості передачі. На безмасштабній контактній мережі епідемічного порогу не існує — навіть дуже слабо заразний патоген зрештою пошириться по всій популяції. Цей результат, встановлений Пастор-Сатаррасом і Веспіньяні 2001 року, переосмислив підхід до стратегії вакцинації: щоб захистити безмасштабну мережу, потрібно цілитися в хаби, а не у випадкові вузли.

Контекст COVID-19: суперрозповсюджувальні події — коли одна заражена людина інфікує десятки на переповненому заході — це якраз ознака важкохвостих розподілів ступенів у контактних мережах. «Правило 20/80» (20% випадків спричиняють 80% передачі) — це відбиток степеневої неоднорідності.

Спробуйте самі

Наведені вище концепції оживають в інтерактивній симуляції. Три симулятори нижче дозволяють безпосередньо змінювати параметри й спостерігати фазові переходи в реальному часі.

🕸️

Дослідник науки про мережі Перемикайтеся між моделями Ердеша–Реньї, Барабаші–Альберт і Уоттса–Строгаца. Регулюйте ймовірність з'єднання чи середній ступінь повзунком і спостерігайте, як виникає гігантська компонента. Жива гістограма розподілу ступенів показує контраст Пуассона й степеневого закону в реальному часі.

📊

Генератор випадкового графа Побудуйте граф G(n, p) з нуля. Поступово збільшуйте p і визначте точний момент, коли найбільша компонента починає домінувати. Кольорове кодування розміру компонент робить фазовий перехід безпомилково видимим.

🧬

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

Завершальна думка

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

Розуміння взаємодії між топологією мережі та динамічними процесами — чи то електричними сигналами, інфекціями, чи чутками — одна з центральних задач науки XXI століття. Математика випадкових графів дає нам мову, щоб ставити правильні запитання.