Сетевая динамика и распространение процессов

COVID-19 разнёсся по 180 странам за 2 недели - это топология scale-free сети международных перелётов. SIR-модель на реальном графе контактов предсказала пик заражений в Европе за 2 месяца. PageRank Google - та же математика: стационарное распределение динамики на графе из 50 млрд вершин.

• **COVID-19:** агентные SIR-модели на реальных графах мобильности (SafeGraph) предсказали волны с точностью 85% за 2 недели. Таргетированные ограничения на хабы эффективнее тотального локдауна.
• **Блэкаут 2003:** 55 млн человек, $6 млрд убытков. Анализ уязвимости через перколяцию - стандарт NERC (North American Electric Reliability Corporation) с 2005.
• **Google PageRank:** 50 миллиардов страниц, power iteration сходится за ~50 итераций. Spectral gap λ₂/λ₁ определяет скорость - та же теория, что и у синхронизации Курамото.

Предварительные знания

• Continuous Dynamical Systems
• Population Dynamics

Графы и динамика: λ₁ определяет всё

COVID-19 убил не только из-за вируса - из-за структуры нашей социальной сети. Аэропорты-хабы разнесли SARS-CoV-2 по 180 странам за 2 недели. SIR-модель на сети предсказала пик заражений в Европе за 2 месяца до пика - просто зная спектр матрицы контактов.

Граф G = (V, E): матрица смежности A_{ij} = 1 если узлы i и j связаны. Степень узла kᵢ = Σⱼ Aᵢⱼ. Самое важное число для динамики - **спектральный радиус λ₁(A)** - наибольшее собственное значение матрицы смежности.

**PageRank = динамика на сети.** Google's PageRank - стационарное распределение случайного блуждания по веб-графу: πᵢ = Σⱼ (Aⱼᵢ/kⱼ) · πⱼ. Это собственный вектор транспонированной матрицы переходов, соответствующий λ₁ = 1. Спектральная теория графов в действии.

SIR: от уравнения к R₀

SIR-модель придумана в 1927 году Кермаком и Маккендриком. За 90 лет она предсказала корь, оспу, грипп, COVID-19. Три переменные: S (восприимчивые), I (заражённые), R (выздоровевшие). Один параметр, который решает всё: R₀.

**Herd immunity:** эпидемия прекращается при S < 1/R₀. Минимальный охват вакцинации: h_c = 1 - 1/R₀. При R₀ = 2.5 (COVID): h_c = 60%. При R₀ = 12 (корь): h_c = 92% - поэтому любая брешь в вакцинации от кори опасна.

Каскадные отказы и перколяция

14 августа 2003: перегрелась одна ЛЭП в Огайо. За 4 часа без света - 55 млн человек в США и Канаде. Это не случайность: каскадные отказы в scale-free сетях математически неизбежны при атаке на хабы.

Теория перколяции: при удалении доли f узлов сеть фрагментируется. Критическая доля f_c - ниже неё гигантская связная компонента исчезает. Для scale-free сетей (γ < 3) - парадоксальный результат.

**Интернет-парадокс:** IPv4-интернет (scale-free, γ ≈ 2.1) почти не разрушается от случайных отказов маршрутизаторов - но несколько крупных провайдеров-хабов (AT&T, Cloudflare) при отказе роняют значительную часть трафика. Cloudflare outage 2022: 19% HTTP-трафика упало при атаке на один хаб.

PageRank: динамическая система как алгоритм

Google PageRank - это решение задачи нахождения стационарного распределения случайного блуждания по веб-графу. Граф из 50 миллиардов страниц. Алгоритм: power iteration - та же динамика, которую изучали для синхронизации.

Идея: страница важна, если на неё ссылаются важные страницы. Рекурсивное определение. Математически: PageRank πᵢ = Σⱼ (Aⱼᵢ/kⱼ)·πⱼ - это собственный вектор транспонированной матрицы переходов M = D^{-1}A.

**Power iteration = динамика Курамото для рангов.** Математически: xₖ₊₁ = M·xₖ - линейная дискретная динамическая система. Сходится к стационарному состоянию со скоростью |λ₂/λ₁| - отношение второго к первому собственному значению. Spectral gap = скорость сходимости.

Ключевые идеи

• **Спектральный порог**: эпидемия при β > γ/λ₁(A). λ₁ зависит от топологии - хабы снижают порог
• **R₀ = β/γ**: базовое репродуктивное число. Herd immunity: h_c = 1 - 1/R₀
• **Scale-free парадокс**: устойчивость к случайным отказам (f_c → 1), но уязвимость к целевым атакам на хабы
• **Перколяция**: f_c = 1 - 1/(κ-1), κ = <k²>/<k>. При γ < 3: f_c → 1 для случайных атак
• **PageRank** = стационарное распределение случайного блуждания = собственный вектор M^T при λ=1
• **Power iteration** = линейная динамика xₖ₊₁ = M·xₖ. Сходится со скоростью |λ₂/λ₁| (spectral gap)

Связанные темы

Сетевая динамика синтезирует популяционную динамику, теорию графов и спектральные методы ML:

• Популяционная динамика — SIR - обобщение Лотки-Вольтерра на дискретные сети с гетерогенными взаимодействиями
• Синхронизация (Курамото) — Kc ≈ γ/λ₁(A) - прямая аналогия с порогом эпидемии; power iteration для PageRank - та же идея, что и mean-field Курамото
• Теория управления — Распределённое управление в сетях: каждый узел - свой контроллер. Консенсусные алгоритмы как диффузия на лапласиане

Вопросы для размышления

• Алгоритмы соцсетей максимизируют вовлечённость - фактически увеличивают λ₁ информационного графа и снижают порог для распространения контента. Как это связано с ростом поляризации?
• Graph Neural Networks (GNN) реализуют диффузию признаков по графу: x_{k+1} = σ(A·x_k·W). Это дискретный шаг теплопроводности на графе. Какой у GNN spectral gap и как он влияет на глубину сети?
• Можно ли построить сеть, одновременно устойчивую к случайным отказам И к целевым атакам? Что говорит о возможности такой сети теория перколяции?

Связанные уроки

• dist-03-fallacies