Граф Ердеша-Реньї G(n,p) має n вершин, і кожне з C(n,2) можливих ребер присутнє незалежно з імовірністю p. При збільшенні p вище критичного порогу pc = 1/(n−1) граф зазнає різкого фазового переходу: одна гігантська зв'язна компонента раптово охоплює макроскопічну частку всіх вершин.
Середній ступінь: <k> = (n-1) · p
Критичний поріг: p_c = 1/(n-1), тобто <k>_c = 1
Частка гігантської компоненти S (самоузгоджене рівняння):
S = 1 - exp(-<k> · S)
Підкритичний (<k> < 1): найбільша компонента ~ O(log n)
Надкритичний (<k> > 1): найбільша компонента ~ S·n
Перехід гігантської компоненти математично ідентичний зв'язковій перколяції на повному графі. Та сама різка зміна зв'язності проявляється при поширенні епідемій (хвороба стає ендемічною при R0 > 1), у стійкості інтернету до випадкових відмов та в задачах жорсткості випадкових мереж пружин.
Що таке граф Ердеша-Реньї?
Граф Ердеша-Реньї G(n,p) — це граф із n вершинами, де кожне можливе ребро включається незалежно з імовірністю p. Запроваджений у 1959 році, він є фундаментальною основою теорії випадкових мереж і відправною точкою для розуміння структури мереж.
Що таке фазовий перехід гігантської компоненти?
Коли середній ступінь <k> = (n−1)p перетинає критичне значення 1, найбільша зв'язна компонента раптово зростає від O(log n) до O(n) вершин. Це різкий фазовий перехід — параметр порядку (частка гіганта) змінюється з нуля до ненульового значення при чіткому порозі.
Що таке критична імовірність p_c?
Критична імовірність — p c = 1/(n−1). Нижче цього порогу граф складається з багатьох малих деревоподібних компонент. Вище нього з'являється одна гігантська зв'язна компонента, що охоплює частку S всіх вершин, де S задовольняє S = 1 − exp(−<k>S).
Пошук у ширину починається з невідвіданої вершини і досліджує всі досяжні вершини шар за шаром за допомогою черги. Усі знайдені вершини утворюють одну компоненту. Повторення для всіх невідвіданих вершин розбиває граф на компоненти за час O(n + m).
Вище порогу частка S задовольняє рівняння S = 1 − exp(−<k>S). При <k> = 2 близько 80% вершин входять до гіганта. При <k> → ∞ S → 1, і майже всі вершини з'єднані в одну компоненту.
За аналогією з термодинамікою, система змінює якісний стан при критичному параметрі. Частка гіганта є параметром порядку: нуль нижче pc і ненульова вище, з сингулярною похідною у точці переходу — точно як намагніченість у точці Кюрі.
Кожне ребро діє як пружина, що притягує зв'язані вершини. Усі пари вершин відштовхуються, як заряджені частинки. Ітерація цих сил приводить граф до конфігурації з низькою енергією, де зв'язані кластери групуються разом, роблячи структуру компонент наочно очевидною.
Безпосередньо на критичному порозі найбільша компонента має діаметр O(n1/3), що значно більше O(log n) у надкритичному режимі. Це відображає крихку деревоподібну розгалужену структуру на самому фазовому переході.
Зазвичай ні. Реальні мережі мають степеневий розподіл ступенів, високу кластеризацію і структуру спільнот. Більш реалістичні моделі — Барабаші-Альберт (переважне приєднання) і Ваттс-Строгатц (малий світ). G(n,p) залишається незамінним математичним базисом.
Застосування: епідеміологія (поріг R0 > 1 для пандемії), стійкість інтернету до випадкових відмов маршрутизаторів, аналіз соціальних мереж, LDPC-коди виправлення помилок та поріг виконуваності випадкової 3-SAT в теорії складності обчислень.