Випадкові графи Ердоша-Реньї: народження теорії випадкових мереж

3D Simulations

🕸️ Мережі · Теорія випадкових графів

📅 Липень 2026⏱ 12 хв🟡 Середній рівень · Останнє оновлення: 9 липня 2026 р.

Випадкові графи Ердоша-Реньї: народження теорії випадкових мереж

Киньте зважену монетку для кожної можливої пари з n точок на аркуші — випав орел, малюємо ребро; решка — залишаємо порожнім. Цей до абсурду простий рецепт, формалізований Палом Ердошем та Альфредом Реньї в 1959 році, породив цілу математичну галузь. Він також розкрив одне з найяскравіших явищ у всій комбінаториці: випадковий граф може раптово, майже миттєво перейти від розсипу дрібних уламків до однієї гігантської зв'язної маси — і все це запускається лише незначним поворотом однієї-єдиної ручки ймовірності.

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. Моделі G(n,p) і G(n,M)

Випадковий граф Ердоша-Реньї існує у двох тісно пов'язаних варіантах, обидва позначаються літерою G ("граф"):

G(n, p) — "біноміальна" модель (Гілберт, 1959): Візьмемо n позначених вершин. Для кожного з C(n,2) = n(n-1)/2 можливих ребер незалежно включаємо його до графа з ймовірністю p і не включаємо з ймовірністю 1-p. G(n, M) — "рівномірна" модель (Ердош і Реньї, 1959): Візьмемо n позначених вершин і виберемо один граф рівномірно випадково з множини всіх графів, що мають рівно M ребер (еквівалентно: вибираємо M ребер рівномірно без повторень із C(n,2) можливих).

Ці дві моделі асимптотично еквівалентні, коли M ≈ p·C(n,2): більшість властивостей, що виконуються "з високою ймовірністю" в одній моделі, виконуються і в іншій. G(n,p) використовується частіше в сучасній практиці, тому що незалежність між ребрами значно спрощує ймовірнісні обчислення — саме цю модель зазвичай мають на увазі, кажучи "граф Ердоша-Реньї" чи "ER-граф" сьогодні.

2. Очікуваний ступінь і розподіл ступенів

Кожна вершина в G(n,p) має n-1 потенційних сусідів, і кожне потенційне ребро включається незалежно з ймовірністю p. Це робить ступінь будь-якої окремої вершини біноміальною випадковою величиною:

Розподіл ступенів: P(deg(v) = k) = C(n-1, k) \cdot p^k \cdot (1-p)^(n-1-k) Очікуваний ступінь: E[deg(v)] = (n-1)\cdotp \approx np (для великих n) Границя при великих n і фіксованому середньому (n \to \infty, p \to 0, np = λ = const): P(deg(v) = k) \to e^(-λ) \cdot λ^k / k! (розподіл Пуассона)

Саме тому графи Ердоша-Реньї іноді називають "пуассонівськими випадковими графами" — для великих n розподіл ступенів збігається до пуассонівського розподілу із середнім λ = np. Ключовий момент: пуассонівський розподіл має експоненційно спадаючий хвіст — вершини зі ступенем значно вищим за середній зустрічаються надзвичайно рідко. Це математичне коріння найвідомішого обмеження моделі, обговорюваного в розділі 7.

3. Фазовий перехід гігантської компоненти

Найвідоміший результат про G(n,p) стосується того, що відбувається з розміром найбільшої зв'язної компоненти, коли p (еквівалентно, середній ступінь λ = np) перетинає значення 1. Ердош і Реньї довели, що цей перехід — по суті фазовий перехід, у тому ж фізичному сенсі, що й замерзання води:

Фазовий перехід гігантської компоненти (n \to \infty, середній ступінь λ = np): λ < 1 (докритичний): Усі компоненти малі — найбільша компонента має O(log n) вершин з високою ймовірністю. Граф — розсип малих дерев і простих циклів; жодної домінантної компоненти немає. λ = 1 (критична точка): Найбільша компонента має розмір Θ(n^(2/3)) — більший за логарифмічний, але все ще зникома частка від n. λ > 1 (надкритичний): З'являється єдина "гігантська компонента", що містить постійну частку f(λ) усіх n вершин, де f(λ) — єдиний розв'язок у (0,1] рівняння: f(λ) = 1 - e^(-λ\cdotf(λ)) Усі інші компоненти залишаються малими, O(log n).

Вікно переходу навколо λ = 1 надзвичайно вузьке — для великих n достатньо нескінченно малої зміни p, щоб перевести граф зі стану "немає гігантської компоненти" в стан "одна компонента поглинає позитивну частку всіх вершин". Це дискретно-математичний аналог теорії перколяції у фізиці, і його часто наводять як перший строго доведений приклад різкого фазового переходу в суто комбінаторній (нефізичній) системі.

Інтуїція через розгалужувальні процеси: дослідження вихідних сусідів від випадкової вершини протягом кількох кроків поводиться як розгалужувальний процес, де кожна виявлена вершина породжує ≈ λ нових недосліджених сусідів. Розгалужувальний процес із середнім числом нащадків λ вимирає з ймовірністю 1, якщо λ ≤ 1, але виживає назавжди з позитивною ймовірністю, якщо λ > 1 — точно віддзеркалюючи поріг гігантської компоненти.

4. Поріг зв'язності ln(n)/n

Ще різкіший поріг керує повною зв'язністю — чи є весь граф однією зв'язною компонентою без ізольованих вершин узагалі:

Поріг зв'язності (Ердош-Реньї, 1959): Нехай p = (ln n + c) / n для сталої c. При n \to \infty: P(G(n,p) зв'язний) \to e^(-e^(-c)) Зокрема: якщо p = (ln n - ω(n)) / n з ω(n) \to \infty: майже напевно незв'язний (ізольовані вершини зберігаються) якщо p = (ln n + ω(n)) / n з ω(n) \to \infty: майже напевно повністю зв'язний Порогова функція точно дорівнює p* = ln(n) / n.

Доведення майже повністю зводиться до появи ізольованих вершин (вершин нульового ступеня): очікувана кількість ізольованих вершин дорівнює n·(1-p)^(n-1) ≈ n·e^(-np), яка зникає точно тоді, коли p перевищує ln(n)/n, і розходиться нижче цього порогу. Виявляється, що щойно ізольовані вершини зникають, граф — з високою ймовірністю — є зв'язним загалом, що є значно сильнішим і менш очевидним фактом, який вимагає окремого комбінаторного доведення (обчислення у стилі другого моменту / Чебишова щодо кількості малих незв'язних компонент).

5. Діаметр, кластеризація та порівняння з малим світом

Властивість	Ердош-Реньї G(n,p)	Реальні мережі
Розподіл ступенів	Пуассонівський (концентрований)	Часто з важким хвостом / степеневий закон
Середня довжина шляху (діаметр)	≈ ln(n) / ln(np)	Так само мала — властивість "малого світу" зберігається
Коефіцієнт кластеризації	≈ p (дуже низький для розріджених графів)	Зазвичай значно вищий за p
Вершини-хаби (дуже високий ступінь)	Практично відсутні	Поширені (аеропорти, знаменитості, популярні сторінки)

ER-графи справді відтворюють відому властивість "малого світу" — короткі середні довжини шляхів, що зростають лише логарифмічно з розміром мережі, відповідаючи інтуїції "шести рукостискань". Там, де модель дає збій, — це кластеризація: реальні соціальні та біологічні мережі демонструють набагато більше замикання трикутників (ваші друзі, як правило, знайомі одне з одним), ніж передбачив би ER-граф тієї ж щільності, що й спонукало створення моделі малого світу Уоттса-Строгаца як прямого уточнення.

6. Історичний контекст

Пал Ердош і Альфред Реньї опублікували свою основоположну статтю "On Random Graphs I" у 1959 році, за якою пішла серія глибших робіт до початку 1960-х, що встановили описані вище результати про фазовий перехід і зв'язність із повною строгістю. Едгар Гілберт незалежно ввів формулювання G(n,p) того ж року. Разом ці статті по суті заснували теорію випадкових графів як окрему математичну дисципліну, і "еволюція випадкових графів" (спостереження за виникненням структури зі зростанням p від 0 до 1) залишається одним із найбільш цитованих результатів у комбінаториці.

Модель на десятиліття випередила великомасштабні емпіричні набори даних про мережі (веб-графи, соціальні мережі, мережі біологічних взаємодій), які пізніше розкрили її головний недолік — відсутність важкохвостих розподілів ступенів і високої кластеризації, — але вона залишається необхідною математичною базовою лінією, з якою порівнюється і калібрується кожна більш складна модель мережі (преференційне приєднання Барабаші-Альберт, малий світ Уоттса-Строгаца, стохастичні блокові моделі).

7. Застосування та обмеження

Нульова модель / статистична база: найпоширеніше практичне застосування сьогодні — порівняння кластеризації, розподілу ступенів чи структури спільнот реальної мережі з ER-графом того ж n і того самого середнього ступеня, щоб кількісно оцінити, наскільки "невипадковою" насправді є структура реальної мережі.
Теорія перколяції та стійкості: поріг гігантської компоненти безпосередньо моделює перколяцію — наприклад, яка частка ланок в інфраструктурній мережі може випадково вийти з ладу, перш ніж мережа розпадеться на малі незв'язні шматки.
Інтуїція епідемічного порогу: фазовий перехід при λ = 1 структурно аналогічний епідемічному порогу R₀ = 1 у моделях SIR на мережах — обидва є умовами критичності розгалужувального процесу.
Випадкова задача виконуваності обмежень: ER-подібні випадкові гіперграфи лежать в основі вивчення фазових переходів у випадковому k-SAT та інших задачах виконуваності обмежень, пов'язуючи теорію графів із обчислювальною складністю.

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