Случайные графы: Модели Эрдёша-Реньи и законы малых миров

Основателями этого направления стали величайшие математики XX века Пал Эрдёш и Альфред Реньи. В 1959 году они предложили классическую Модель Эрдёша-Реньи (G(n, p)). Представьте n изолированных вершин. Для каждой возможной пары вершин мы бросаем невидимую монету, и с вероятностью p соединяем их ребром. Что получится в итоге?

Главным открытием Эрдёша и Реньи стали фазовые переходы (Threshold phenomenons) — внезапные, резкие изменения свойств всего графа при достижении вероятностью p определенного критического порога. Подобно тому, как вода при 0 градусов мгновенно превращается в лед, случайный граф скачкообразно меняет свои характеристики:

• Если вероятность p меньше порога 1/n, граф представляет собой "пыль" из крошечных изолированных деревьев.
• Когда p достигает 1/n, происходит чудо: независимые кусочки внезапно сливаются в Гигантскую компоненту связности, охватывающую значительную часть всех вершин.
• Когда p достигает порога (ln n)/n, граф почти со стопроцентной вероятностью становится полностью связным (от любой вершины можно дойти до любой).

Модель Эрдёша-Реньи красива математически, но она плохо описывает реальный интернет. В G(n, p) степени вершин распределены по Пуассону, то есть большинство вершин имеют примерно одинаковое количество связей. В реальном интернете (как и в экономике) работает правило "богатые богатеют" (закон Парето).

Для описания этого феномена Альберт-Ласло Барабаши и Река Альберт предложили Модель Барабаши-Альберта, основанную на принципе предпочтительного присоединения (Preferential attachment). Сеть растет динамически: когда появляется новый узел (например, новый сайт), он с гораздо большей вероятностью соединяется с теми узлами, у которых уже много связей (популярными сайтами). Это порождает безмасштабные сети (Scale-free networks), где существует небольшое количество хабов-гигантов (Google, Facebook) с миллионами связей, и огромное множество узлов-аутсайдеров. Эта модель блестяще объясняет топологию Всемирной паутины и ее невероятную устойчивость к случайным поломкам серверов, но крайнюю уязвимость к целенаправленным атакам на хабы.