Теория сетей: структура взаимодействий

Многие сложные системы лучше всего описываются не уравнениями, а сетями — графами, где узлы — агенты, а рёбра — взаимодействия. Структура сети принципиально определяет динамику: как быстро распространится болезнь, насколько уязвима энергосистема, насколько эффективно распространяется информация.

Основные характеристики сетей

Граф G = (V, E): V — множество узлов (вершин), E ⊆ V×V — множество рёбер. |V| = n, |E| = m.

Степень вершины d(v): число рёбер, инцидентных v. Средняя степень ⟨k⟩ = 2m/n. Распределение степеней P(k) = доля вершин степени k — ключевая характеристика.

Кратчайший путь L(u,v): минимальное число рёбер между u и v. Средний путь L̄ = (1/n(n−1)) Σᵤ≠ᵥ L(u,v).

Коэффициент кластеризации Cᵥ: доля пар соседей v, которые сами связаны рёбрами: Cᵥ = 2eₙ/(dᵥ(dᵥ−1)), где eₙ — число рёбер между соседями. Глобальный C̄ = ⟨Cᵥ⟩.

Центральность (betweenness centrality): bᵥ = Σᵤ≠ᵥ σᵤᵥ(v)/σᵤᵥ, где σᵤᵥ — число кратчайших путей u→v, σᵤᵥ(v) — число из них, проходящих через v. Высокое betweenness → «брокерская» роль в сети.

Феномен малого мира (Watts & Strogatz, 1998)

Эксперимент Милгрэма (1967): письмо нужно доставить адресату в Бостоне через цепочку знакомых из Омахи, Небраска. Средняя длина цепочки: 6 рукопожатий (число шагов). Это феномен «шести степеней разделения».

Модель Уоттса-Строгаца: начальная регулярная решётка (высокий C, большой L) → случайно «перемотаем» часть рёбер (вероятность p). При p ≈ 0.01: L резко падает (глобальное «короткое замыкание»), C остаётся высоким. Малый мир: C ≫ C_{random}, L ≈ L_{random}.

Реальные примеры малого мира:

• WWW: L ≈ 19 (Barabási, 1999)
• Нейронная сеть C. elegans: L = 2.65, C = 0.28 (vs случайный граф L = 2.25, C = 0.05)
• Соавторство учёных: L = 4.79, C = 0.43

Безмасштабные сети (Barabási & Albert, 1999)

Случайный граф Эрдёша-Реньи: P(k) ~ Poisson — большинство узлов имеют степень около ⟨k⟩. Реальные сети: другие! P(k) ~ k^{−γ} — степенной закон (power law). «Хвост» распределения значительно тяжелее пуассоновского.

Безмасштабная сеть: γ ∈ (2, 3) для большинства реальных сетей. Характерного масштаба нет — отсюда название. «Хабы» — узлы с очень высокой степенью (аэропорты-хабы, Google, Facebook).

Механизм образования: preferential attachment. Новый узел подключается к существующим узлам с вероятностью, пропорциональной их степени: P(присоединиться к v) = d(v)/Σᵤ d(u). «Богатые становятся богаче». Результат: γ = 3.

Реальные примеры: WWW (входящие ссылки: γ ≈ 2.1), цитирования (γ ≈ 3), авиамаршруты, биологические сети белок-белок.

Уязвимость и устойчивость сетей

Устойчивость к случайным отказам: при удалении случайных узлов безмасштабная сеть устойчива — большинство узлов имеют малую степень, их удаление не разрушает связность. Значительный гигантский компонент сохраняется до удаления ≈80% узлов.

Уязвимость к направленным атакам: удаление хабов катастрофично. Удаление топ-8% узлов по степени → фрагментация сети. Пример: WWW теряет связность при «атаке» на Google, Yahoo, Baidu.

Эпидемиологическое следствие: в безмасштабных сетях нет эпидемического порога (Albert, 2000): SIR-модель с R₀ > 1 всегда распространяется. Хабы — суперспредеры.

Численный пример: интернет-граф

Граф: 100000 узлов. Случайный граф (p = 0.0001): C ≈ 0.0001, L ≈ 5.0, max degree ≈ 20. Безмасштабный (γ ≈ 2.3): C ≈ 0.4, L ≈ 4.2, max degree ≈ 2000. Соответствует реальному интернету: высокая кластеризация + малый мир + хабы.

Задание: Используйте NetworkX (Python). Создайте три графа (n=1000 узлов): (1) Случайный (Erdős–Rényi, p=0.01); (2) Малый мир (Watts-Strogatz, k=10, p=0.05); (3) Безмасштабный (Barabási-Albert, m=5). Для каждого: вычислите L, C, P(k), betweenness centrality. Визуализируйте распределение степеней в log-log масштабе — у какого графа степенной закон? Симулируйте эпидемию SIR (β=0.1, γ=0.05) — в каком графе она распространяется быстрее?