Наука про мережі: Чому кілька вузлів керують усією графом

Все є графом

Граф G = (V, E) — це просто набір вершин і ребер, які їх з’єднують, і ця абстракція виявляється майже універсальною: нейрони, що з’єднані в коннектомі, білки, які взаємодіють у клітині, гіперпосилання, що формують веб-сайт, люди, які дружать — все це можна представити як вершини та ребра. Результат, який заклав фундамент для цієї галузі – рішення Ейлера від 1736 року проблеми з мостом Кенігсберг: існує шлях, що проходить через кожен міст рівно один раз, лише якщо кожна вершина має парну ступінь, це абстрактний інсайт, який запустив теорію графів за два з половиною століття до того, як «наука про мережі» стала назвою для цієї галузі.

Кілька чисел описують форму графа. Ступінь k(v) вершини – це кількість її зв’язків; розподіл ступенів P(k) — ймовірність того, що випадкова вершина має ступінь k — часто є найбільш інформативною статистикою про мережу, оскільки вона миттєво повідомляє, наскільки граф близький до однорідності або домінує кілька екстремальних відхилень. Матриця суміжності A (Aᵢⱼ = 1, якщо i та j з’єднані) робить алгебру графів конкретною: степені A рахують шляхи заданої довжини між будь-якими двома вершинами.

Зміцнення зв’язків: шість випадкових знайомств

Експеримент Стенлі Мільграма 1967 року показав, що повідомлення може досягти незнайомої людини в Бостоні приблизно за шести кроків особистих знайомств — походження «шестеро ступенів відома». У 2016 році було проведено аналіз графа Facebook і виявлено середню кількість лише 3,57 ступенів для 1,6 мільярда користувачів. Модель Воттса-Строґаца (1998 року) пояснює, чому це є загальним явищем, а не випадковістю: почніть з регулярної кільцевої решітки, де кожен вузол підключений до своїх k найближчих сусідів, потім переробіть кожне з’єднання випадковим чином з певною ймовірністю p. Навіть якщо p ≈ 0.01 — одне з сто з’єднань стало довгодіючим коротким маршрутом — це зменшує середню довжину шляху, майже не змінюючи високу локальну зв’язність решітки. Цей вузький діапазон між порядком і випадковістю є режимом малого світу.

Розподіл ступенів та перевага притягання

Більшість реальних мереж йдуть далі, ніж малий світ: їх розподіл ступенів має важкий хвіст, а не симетричну форму, дотримуючись закону сили P(k) ~ k⁻ᵞ з γ, що зазвичай коливається між 2 та 3. Невелика кількість вузлів — хаби — мають набагато більше зв’язків, ніж у середньому, і жодне «типове» значення ступеня не описує мережу, що й означає «розріджена».

Модель Barabási–Albert росту: почніть із невеликої з’єднаної початкової графа кожного нового вузла додається m ребер, які приєднуються до існуючого вузла i з: Π(k_i) = k_i / Σ_j k_j // «багатенькі стають ще багатшими» повторюйте це, коли мережа зростає → P(k) ~ k^-γ, γ ≈ 3 Тому що ранні, добре з’єднані вузли продовжують приваблювати непропорційну кількість нових ребер, це просте правило росту плюс приєднання відтворює веб-сайт, мережі цитування та карти авіаліній без будь-якого дизайну. Це також пояснює асиметрію стійкості: розріджені мережі добре витримують випадкове збійне видалення вузлів, оскільки більшість вузлів мають низький ступінь і рідко мають значення, але вони швидко фрагментуються під час цілеспрямованого видалення їх кількох хабів — властивість, яка має прямі наслідки для проектування інфраструктури та контролю епідемій.

Barabási–Albert growth model:
  start with a small connected seed graph
  each new node adds m edges, attaching to existing node i with:
    Π(k_i) = k_i / Σ_j k_j        // "rich get richer"
  repeat as the network grows  →  P(k) ~ k^-γ,  γ ≈ 3

Зв’язки та коефіцієнт кластерності

Реальні мережі не є однорідними сумішами — вони містять щільно пов'язані кластери, що вільне зшиті разом. Коефіцієнт кластерності C(v) вимірює локальну зв’язність: частку сусідів вузла, які також з’єднані. Якщо ваші двоє друзів також знають один одного, ваш місцевий район є тісно зв'язаним; в середньому це робиться для всіх вузлів і дає глобальне значення, яке для реальних соціальних мереж значно перевищує те, що було б у випадкової графа такого ж розміру та щільності. Триадний закриття — «друг друга дружина стає другом» — є механізмом локального підвищення коефіцієнту кластерності з часом.

Знаходження спільнот формально означає розділення вузлів для максимізації модульності Q — частка ребер, що падають всередину спільнот, мінус те, чого можна було б очікувати, якщо б ребра були розміщені випадково. Алгоритм Girvan–Newman повторно видаляє ребро з найвищою міжзв’язністю до тих пір, поки граф не розділиться на спільноти; метод Louvain жадібно об'єднує вузли в спільноти для підвищення модульності і є практичним стандартом, який працює приблизно за O(n log n) навіть на графах із мільйонами вузлів.

PageRank: важливість як випадковий хід

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

PR(A) = (1 - d)/N + d · Σ_(B→A) PR(B) / L(B) d = коефіцієнт затухання, зазвичай 0.85 N = кількість вузлів, L(B) = ступінь виходу B Стаціонарний розподіл цього ходу — частка часу, яку серфер проводить на кожній сторінці — є її PageRank, обчислюється ітеративно або за допомогою методів розрідженого власного вектора. Той самий випадковий-хідний погляд пояснює, чому топологія мережі впливає на поширення епідемій: на неоднорідній графі число реплікацій масштабується з ⟨k²⟩/⟨k⟩, отже вузли діють як суперрозповсюджувачі та вакцинування їх значно ефективніше зупиняє спалахи, ніж вакцинування випадкових осіб.

PR(A) = (1 - d)/N  +  d · Σ_(B→A) PR(B) / L(B)
  d = damping factor, conventionally 0.85
  N = number of nodes, L(B) = out-degree of B

Frequently asked questions

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

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