Erdos-Renyi Пересипання: поріг великого компонента

Граф, зроблений з кишенькових підкидань

Візьміть N ізольованих вузлів і для кожного з можливих 1/2 * N * (N - 1) пар з'єднайте їх ребрами незалежно з ймовірністю p. Це вся рецептура випадкового графа Erdos-Renyi G(N,p), представлений Палом Ердошом та Альфредом Рені у 1959 році (з еквівалентною моделею рівномірного графа, вивченою Едгаром Гербертом того ж року). Жоден вузол не є особливим, жодне ребро не більш ймовірне за будь-яке інше - і все ж, коли p перетинає один чіткий поріг, глобальна форма графа переходить від розсіювання малих шматків до одного домінуючого клаптя.

Це перехідний етап, такий самий як у воді, що перетворюється на пару, і тому просочування з'являється скрізь від епідеміології до науки про матеріали: це найпростіша модель того, як локальні зв’язки додаються до глобальної зв’язності.

Рахування ребер, а не вузлів

Контрольна змінна не є p само по собі, а середній ступінь, c = p(N-1), який приблизно дорівнює pN для великих N - очікувана кількість ребер, що торкаються типового вузла. Ердош і Реньі показали, що розмір найбільшого зв’язного компоненту раптово змінюється в c = 1, тобто p_c = 1/N.

c 1 (p > 1/N): з’являється один великий компонент, розмір пропорційний N Нижче порогу граф є лісом малих дерев і циклів - жоден компонент не містить більше ніж логарифмічного відрізка вузлів, і додавання більшої кількості ребер просто створює більше маленьких шматочків. Перетнеться c = 1 і великий компонент конденсується з шуму майже миттєво: його розмір зростає з O(log N) до позитивної частки всього графа протягом вікна p, яке зменшується зі збільшенням N. Це прихований аргумент про розмноження - кожен вузол, який ви досліджуєте з початкової вершини, відкриває в середньому c нових ребер, і процес розмноження із середнім потомством c припиняється напевно, якщо c не більше 1, але виживає з позитивною ймовірністю, якщо c перевищує 1.

c < 1  (p < 1/N):  every component is small - the largest is O(log N) nodes
c = 1  (p = 1/N):  the critical point - component sizes follow a power law
c > 1  (p > 1/N):  a single giant component emerges, size proportional to N

Що виглядає велика компонента

Відразу ж над порогом велика компонента залишається крихкою: її відносна величина s задовольняє рівняння s = 1 - e^(-cs), трансцендентне рівняння, яке дає значення s близькі до нуля безпосередньо після c = 1 і схиляється до 1, коли c зростає понад 3 або 4. Уточнюючи c = 1, розподіл розміру компоненти відповідає закону степенів з показником -5/2, що є ознакою критичної системи без характерного масштабу – того самого показника, який виявляється в інших моделях середнього поля перколяції та моделей розбіжності процесів.

Це також, не випадково, математика, яка лежить в основі базового числа репродукції епідемії R0. Якщо кожна інфікована особа заражає в середньому R0 інших осіб, R0 менше 1 означає, що ланцюг інфекцій вимирає (підкритичний), а R0 більше 1 означає можливість масового спалаху (надкритичний) – модель SIR на випадковій мережі контактів майже точно зводиться до перколяції зв’язків із p, пов'язаним із ймовірністю передачі.

Випадкові графіки проти реальних мереж

Реальні соціальні, біологічні та інфраструктурні мережі не є графами Ердоша-Рейні – у них значно більше вузлів з високим ступенем, ніж передбачає розподіл за законом Пуассона, зазвичай ближче до закону потужності (модель Barabasi-Albert про тертя відданості захоплює це). Ця різниця має велике практичне наслідування, виявлене Реккою Альберт, Хавонгом Чонгом та Альбертом-Ласлом Барабасі у 2000 році: мережі з масштабованою потужністю вражаючим чином стійкі до випадкового відключення вузлів – видалення випадкових вузлів майже не погіршує великий компонент, оскільки більшість вузлів мають низький ступінь – але крихкі до цілеспрямованого видалення вузлів з найвищим ступенем, які можуть зруйнувати зв’язність лише за невелику частку відключених вузлів. Граф Ердоша-Рейні, навпаки, однаково вразливий (або однаково стійкий) до випадкових та цілеспрямованих атак, оскільки кожен вузол статистично однаковий.

Моделювання

for i in range(N): for j in range(i + 1, N): if random() < p: add_edge(i, j) # union-find відслідковує розміри компонентів у ~O(N alpha(N)) під час додавання ребер find_largest_component_size() Відстежуйте найбільший розмір компоненти за допомогою структури union-find, коли додаються ребра по одному (а не перераховуючи з’єднання з нуля після кожного ребра) і ви можете спостерігати, як велика компонента конденсується в реальному часі - полотно зверху додає ребра з фіксованим темпом і перемальовує розміри компонентів, тому момент, коли c перетинає 1, відображається як видимий стрибок, а не поступовий нахил.

for i in range(N):
    for j in range(i + 1, N):
        if random() < p:
            add_edge(i, j)
# union-find tracks component sizes in ~O(N alpha(N)) as edges are added
find_largest_component_size()

Frequently asked questions

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

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