Теорія мереж: від шести рукостискань до енергосистем

Математика зв'язків

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

Три числа виконують основну роботу з характеристики якісної структури мережі:

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

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

Шість рукостискань

У 1967 році соціальний психолог Стенлі Мілґрем провів на позір простий експеримент. Він попросив випадково обраних людей у Небрасці та Канзасі передати лист цільовій особі в Бостоні — але лише через особисто знайомих. Листи, що дійшли (не всі дійшли), пройшли в середньому лише через шість посередників: шість рукостискань.

Ця властивість "малого світу" — короткі середні довжини шляху навіть у величезних мережах — здається парадоксальною. Як можуть 7 мільярдів людей бути настільки близькими? Відповідь криється у далекосяжних скороченнях. Навіть невелика частка ребер, що охоплюють великі соціальні відстані, може різко скоротити середню довжину шляху в усій мережі.

Дункан Воттс і Стівен Строгац формалізували це у своїй знаковій моделі 1998 року. Почніть із кільця з N вузлів, кожен з яких з'єднаний зі своїми K найближчими сусідами, — це висококластеризована, але суто локально з'єднана мережа з дуже довгими шляхами. Тепер випадково "перекомутуйте" невелику частку p ребер, з'єднавши віддалені вузли. При напрочуд малих значеннях p середня довжина шляху різко падає, тоді як кластеризація лишається високою: мережа одночасно набуває обох властивостей реальних соціальних мереж.

Культурних прикладів безліч. Число Ердеша вимірює "співавторську відстань" математика від плідного угорського математика Пала Ердеша; більшість практикуючих математиків мають число Ердеша менше 6. Число Кевіна Бейкона застосовує ту саму ідею до голлівудських акторів через спільні кінематографічні титри. Обидва приклади демонструють, що великі, різноманітні людські мережі мають властивість малого світу.

Безмасштабні мережі та хаби

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

P(k) ~ k^(-γ)    де γ зазвичай перебуває між 2 і 3

Це означає, що невелика кількість хабів має величезну кількість зв'язків, тоді як переважна більшість вузлів мають дуже мало зв'язків. У вебі Google і Wikipedia посилаються на мільйони сторінок; типова вебсторінка посилається на кілька. У клітинній біології невелика кількість білків взаємодіє із сотнями партнерів, тоді як більшість — лише з одним чи двома.

Альберт-Ласло Барабаші та Река Альберт пояснили це у 1999 році за допомогою моделі преференційного приєднання: коли до мережі приєднуються нові вузли, вони з більшою імовірністю з'єднуються з вузлами, які вже добре з'єднані. "Багаті стають багатшими." Це природно породжує степеневий розподіл без жодного явного задуму. Щоразу, коли запускається новий сайт і посилається на Google, а не на маловідомі сторінки, він підсилює хабову структуру вебу.

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

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

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

Але цілеспрямовані атаки — зовсім інша історія. Видаліть верхні 5–10% вузлів, ранжованих за ступенем, — хаби — і мережа швидко розпадається на роз'єднані компоненти. Гігантський зв'язний компонент руйнується. Це пояснює два на перший погляд загадкові спостереження:

• Інтернет надзвичайно стійкий до випадкових апаратних збоїв (маршрутизатори постійно виходять з ладу, а пакети безшовно перенаправляються), проте вразливий до скоординованих атак на великі точки обміну трафіком.
• Багато патогенів експлуатують хаби біологічних мереж. ВІЛ переважно вражає CD4+ Т-хелпери, які є хабами в мережі імунної сигналізації — руйнуючи здатність мережі до координації.

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

Поширення епідемій у мережах

Епідеміологи використовують SIR-модель для відстеження поширення хвороби: кожна людина або сприйнятлива (Susceptible), або інфікована (Infected), або одужала (Recovered, з імунітетом). У добре перемішаній популяції, чи розгориться епідемія, залежить від базового репродуктивного числа R₀ — середньої кількості людей, яких заражає одна інфікована особа. Якщо R₀ > 1, епідемія зростає; якщо R₀ < 1, вона згасає.

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

Це має прямі наслідки для охорони здоров'я. COVID-19 поширювався з лякаючою швидкістю через авіаційні хаби на кшталт Хітроу, JFK та Дубая — не тому, що ці міста мали якусь особливу біологію, а тому, що вони перебувають у центрі безмасштабної мережі подорожей. Кампанії вакцинації, спрямовані на хаби (часті подорожні, медичні працівники, соціальні "з'єднувачі"), придушують епідемії значно ефективніше, ніж випадкова вакцинація.

Біологічні та технологічні мережі

Сила теорії мереж — у її універсальності: та сама математика описує системи в абсолютно різних сферах:

• Метаболічні мережі: приблизно 5 000 біохімічних реакцій у клітині людини утворюють мережу. Хабові метаболіти, як-от АТФ і піруват, беруть участь у сотнях реакцій; видаліть їх — і клітина гине.
• Коннектоми: нематода C. elegans має рівно 302 нейрони, і всі ~7 000 синаптичних зв'язків нанесено на карту. Її коннектом має властивості малого світу, попри те що вміщується на вушку голки.
• Харчові мережі: екосистеми як спрямовані графи стосунків "хижак-жертва". Ключові види — це хаби; їх видалення каскадом поширюється харчовою мережею.
• Всесвітня павутина: понад 60 трильйонів сторінок, спрямовані ребра від посилань. Вхідний ступінь підпорядковується степеневому закону; PageRank експлуатує той факт, що хаби, на які посилаються інші хаби, є найавторитетнішими сторінками.
• Мережі регуляції генів: транскрипційні фактори, що активують чи пригнічують десятки генів, є мережевими хабами; мутації в цих хабах (як p53, "охоронець геному") часто спричиняють рак.

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