Динамические системы

Комплексные сети и графовая динамика

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

  • Эпидемиология: распространение COVID-19 ускорено хабами (международные аэропорты), что объясняет, почему стратегия 'закрыть 20% самых связных узлов' эффективнее, чем случайный карантин 80% населения
  • Нейронаука: связность мозга (connectome) Homo sapiens имеет структуру тесного мира; нарушения в сетевой топологии коррелируют с шизофренией и болезнью Альцгеймера
  • Инфраструктура: американская энергосеть 2003 года - каскадный отказ начался с одного перегруженного узла, за 8 секунд отключив 55 млн потребителей; теория лапласиана могла это предсказать
  • Социальные сети: алгоритм PageRank Google - собственный вектор лапласиана веб-графа; ценность страницы определяется не числом ссылок, а их качеством

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

  • Теория графов (основы)
  • Матрицы смежности и степени
  • Модель Курамото
  • Предыдущий урок: ds-28

Безмасштабные сети

В 1998 году Ватц и Строгатц обнаружили, что сеть нейронов C. elegans (302 нейрона, 2359 синапсов) обладает «тесным миром»: средняя длина пути L ~ 2.65 как у случайной сети, при высокой кластеризации C ~ 0.28. В 1999 году Барабаши и Альберт показали: интернет (n > 10^9 страниц) растёт по принципу предпочтительного присоединения - отсюда степенной закон P(k) ~ k^{-3}.

Чем характеризуется безмасштабная сеть?

Безмасштабная сеть (Barabási-Albert, 1999) имеет степенное распределение степеней P(k) ~ k^(-gamma). Это объясняет существование hubs - узлов с очень большой степенью (Google, Wikipedia в web-графе). Большинство реальных сетей (web, citation, social) - безмасштабные с 2 < gamma < 3.

Сети малого мира

Модель тесного мира Ватца-Строгатца: начинают с правильного кольца (n узлов, каждый соединён с k соседями), затем каждое ребро с вероятностью p перекоммутируют случайно. При p~0.01 получают малое L (как у случайной сети) и большое C (как у правильного кольца) - именно такая структура у нейронных и социальных сетей.

Безмасштабная сеть и хабы. Интернет - безмасштабная сеть: Google, Amazon, Wikipedia - хабы с миллиардами ссылок, а большинство сайтов имеют лишь несколько ссылок. Если случайно выключить 90% сайтов, сеть останется связной (хабы выживут). Но целенаправленная атака на Google разрушит интернет.

Что отличает сеть малого мира (Watts-Strogatz)?

Уоттс и Строгатц (1998) показали, что добавление малой доли случайных рёбер к регулярной решётке снижает диаметр с O(N) до O(log N), сохраняя локальную кластеризацию. Эксперимент Милгрэма (1967) "6 рукопожатий" - реальный пример: социальная сеть малого мира.

Динамика на сетях: эпидемии и каскады

Robustness against random failures vs. vulnerability to targeted attacks - фундаментальный trade-off безмасштабных сетей. Это применяется в дизайне устойчивых инфраструктур и в стратегии вакцинации (таргетировать хабы).

Диффузия на сетях: уравнение теплопроводности dx/dt = -L*x, где L - лапласиан. Скорость диффузии определяется lambda_2. Спектральный разрыв (lambda_2/lambda_n) определяет скорость смешивания марковской цепи - это связывает теорию графов с эргодической теорией.

МодельP(k)<L>CОсобенность
Случайная (Erdos-Renyi)Пуассонlog(N)/log(<k>)~<k>/NОднородная, порог связности
Тесный мир (Watts-Strogatz)Экспоненциальная~log(N)ВысокоеМалые пути + кластеризация
Безмасштабная (Barabasi-Albert)k^{-3}log(N)/log(log(N))НизкоеХабы, нет порога эпидемии

Почему эпидемический порог в безмасштабных сетях стремится к нулю при N → inf?

Пастор-Саторрас и Веспиньяни (2001): для SIS-эпидемии на сети с P(k) ~ k^(-gamma) с 2 < gamma <= 3 второй момент <k²> расходится при N → inf, поэтому критическое значение скорости заражения lambda_c = <k>/<k²> → 0. Это объясняет, почему компьютерные вирусы и инфекционные заболевания распространяются "по умолчанию" в реальных сетях.

Связи с другими областями

Комплексные сети объединяют теорию графов, динамические системы, статистическую физику и приложения от эпидемиологии до нейронаук.

  • Синхронизация: модель Курамото — Курамото - простейший пример графовой динамики, реализуемый на комплексных сетях
  • Сетевая динамика и распространение процессов — Базовый курс по эпидемиям, каскадам и PageRank на сетях
  • Эргодическая теория: перемешивание и энтропия — Эргодические свойства случайных блужданий на сетях - связь с эргодической теорией

Итоги

  • Лапласиан L = D - A: спектр 0 = lambda_1 <= lambda_2 <= ... <= lambda_n; lambda_2 (Фидлер) - алгебраическая связность
  • BA-сеть: предпочтительное присоединение дает P(k) ~ k^{-3}; <k^2>/<k> -> inf, нет порога эпидемии
  • Тесный мир (Ватц-Строгатц): малые пути L ~ log(N) и высокая кластеризация C; типичны для социальных и нейронных сетей
  • SIR на сети: R_0 = beta/gamma * <k^2>/<k>; для BA-сетей -> inf и любая эпидемия распространяется
  • Синхронизация Курамото на сетях: K_c ~ <k>/<k^2> -> 0 для безмасштабных сетей
  • Диффузия: dx/dt = -L*x; скорость смешивания ~ lambda_2; спектральный разрыв определяет эффективность MCMC

Чему равно число Фидлера lambda_2 лапласиана связного графа и что оно характеризует?

Теорема Фидлера: lambda_2 > 0 тогда и только тогда, когда граф связен. Это число измеряет, насколько 'трудно' разрезать граф на две части (изопериметрическое неравенство Чигера). Для полного K_n: lambda_2 = n. Для цепи: lambda_2 ~ 1/n^2 (медленная диффузия).

Комплексные сети и графовая динамика

0

1

Войти