Рандомові графи Ердоша–Ренеї: Фаза переходу великого компонента

Модель G(n,p)

Модель Erdős–Rényi випадкового графа G(n,p) складається з n позначених вершин і для кожного з C(n,2) = n(n−1)/2 можливих ребер незалежно включає його з ймовірністю p. Едгар Гилберт представив цю точну формулювання в 1959 році, той самий рік, коли Паул Ердеш і Альфред Реньі опублікували свою пов'язану модель G(n,M), яка замість цього фіксує точно M ребер, вибраних випадковим чином. Обидві моделі асимптомічно еквівалентні, коли M ≈ p·C(n,2), і G(n,p) є тим, що більшість людей сьогодні означають як «ER графік», оскільки незалежність між ребрами робить математику набагато простішою.

Розподіл ступенів: Пуассон, а не степенястий

Кожна вершина має n−1 потенційних сусідів, кожен з яких незалежно включається з ймовірністю p, тому ступінь вершини є Біноміальним(n−1, p). Зростаючи n і фіксуючи np = λ, це сходиться до розподілу Пуассона:

E[deg(v)] = (n-1)·p ≈ np = λ P(deg(v) = k) → e^(-λ)·λ^k / k! (Пуассон, n → ∞) Експоненційний хвіст затухає — вершини, що знаходяться далеко вище середнього ступеня, є надзвичайно рідкісними. Цей єдиний факт є коренем найвідомішого обмеження моделі, обговореного нижче.

E[deg(v)] = (n-1)·p ≈ np = λ
P(deg(v) = k) → e^(-λ)·λ^k / k!   (Poisson, n → ∞)

Перехід фази великого компонента

Під час переходу середнього ступеня λ = np до 1, найбільший зв’язаний компонент проходить чесну фазову трансформацію, подібно до замерзання води:

λ < 1 (підкритичний): найбільший компонент O(log n) — розсіяні фрагменти λ = 1 (критичний): найбільший компонент Θ(n^(2/3)) λ > 1 (надкритичний): виникає великий компонент розміром f(λ)·n, де f(λ) = 1 - e^(-λ·f(λ)) Вікно навколо λ = 1 надзвичайно вузьке — невеликі зміни в p перевертають графік з «відсутності великого компонента» до «одного компонента, що поглинає позичну частку кожного вершини». Незалежний, ще більш різкий поріг регулює повну зв’язність: при p = ln(n)/n ізольовані вершини зникають і весь граф стає зв’язаним з високою ймовірністю.

λ < 1 (subcritical): largest component O(log n) — scattered fragments
λ = 1 (critical):     largest component Θ(n^(2/3))
λ > 1 (supercritical): a giant component of size f(λ)·n emerges,
                       where f(λ) = 1 - e^(-λ·f(λ))

Пояснення, чому модель недостатньо потужна сама по собі

ER-графіки справді відтворюють властивість "малого світу" — довжини шляхів, які ростуть лише як ln(n)/ln(np), що відповідає "шестерому ступені відомих". Але реальні соціальні та біологічні мережі демонструють набагато більше кластерів, ніж ER-графік тієї ж щільності, і послідовно проявляють розподіли степеня з властивостями закону потужність із невеликою кількістю надзвичайно високих ступенів вузлів — закономірність, яку просто не може створити модель на основі Пойссона. Це спостереження, підкреслене Барбаші та Альбертом у 1999 році, призвело до моделей з переважним притяганням, де нові вершини переважно з'єднуються з уже популярними. ER-графіки залишаються необхідною відправною точкою саме тому, що вони показують, на чому виглядає структура в повній відсутності таких механізмів — стандартний нульовий шаблон, проти якого порівнюється кластерізація та розподіл ступеня будь-якої реальної мережі.

Frequently asked questions

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

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