Модель Ердеша — Реньї

Є два тісно пов'язані варіанти моделі Ердеша — Реньї випадкового графу.

Граф, згенерований біноміальною моделлю Ердеша — Реньї (p = 0,01)

• У моделі ${\displaystyle G(n,M)}$ граф вибирається однорідно і випадково з набору всіх графів, які мають n вершин і M ребер. Наприклад, у моделі ${\displaystyle G(3,2)}$ кожен з трьох можливих графів з трьома вершинами та двома ребрами вибирається з імовірністю 1/3.
• У моделі ${\displaystyle G(n,p)}$ граф будується випадковим додаванням ребер. Кожне ребро включається до графу з імовірністю p, незалежно від інших ребер. Еквівалентно, всі графи з n вузлами і M ребрами мають однакову імовірність.

${\displaystyle p^{M}(1-p)^{{n \choose 2}-M}.}$

Параметр p в цій моделі можна розглядати як функцію ваги. В міру зростання p від 0 до 1 модель включає з більшою ймовірністю графи з великим числом ребер. Зокрема, випадок p=0,5 відповідає випадку, коли всі ${\displaystyle 2^{\binom {n}{2}}}$ графи з n вершинами будуть вибрані з рівною ймовірністю.

Поведінка випадкових графів часто вивчається у випадку, коли n, число вершин графу, прямує до нескінченності. Хоча p і M можуть бути в цьому випадку як фіксованими, так і залежними від функції від n. Наприклад, твердження: Майже всі графи в ${\displaystyle G(n,2ln(n)/n)}$ зв'язні

означає: При прямуванні n до нескінченності ймовірність, що граф з n вершинами і ймовірністю включення ребра 2ln(n)/n зв'язний, прямує до 1.

Математичне очікування числа ребер в ${\displaystyle G(n,p)}$ дорівнює ${\displaystyle {\tbinom {n}{2}}p}$ і за законом великих чисел будь-який граф ${\displaystyle G(n,p)}$ буде майже напевно мати приблизно таке число ребер. Тому, грубо кажучи, якщо ${\displaystyle pn^{2}\to \infty }$, то G(n,p) повинен поводитись подібно до G(n, M) з ${\displaystyle M={\tbinom {n}{2}}p}$ при зростанні n.

Для багатьох властивостей графу це має місце. Якщо P є будь-якою властивістю графу, яка монотонна відносно впорядкування підграфів (це означає, що якщо A є підграфом графу B і A задовольняє P, то B буде задовольняти також P), то твердження «P має місце для майже всіх графів в ${\displaystyle G(n,p)}$» і «P має місце для майже всіх графів у ${\displaystyle G(n,{\tbinom {n}{2}}p)}$» еквівалентні (при ${\displaystyle pn^{2}\to \infty }$). Наприклад, це виконується, якщо P є властивістю бути зв'язним, або якщо P є властивістю мати гамільтонів цикл. Однак це не обов'язково буде виконуватися для немонотонних властивостей (наприклад, властивості мати парне число ребер).

На практиці, модель ${\displaystyle G(n,p)}$ одна з найвикористовуваніших сьогодні, частково через простоту аналізу, яку дає незалежність ребер.

З вищенаведеними позначеннями граф ${\displaystyle G(n,p)}$ має в середньому ${\displaystyle {\tbinom {n}{2}}p}$ ребер. Розподіл степеня вершин біноміальний[4]:

${\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

де n дорівнює загальному числу вершин у графі. Оскільки

${\displaystyle P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}}$ при ${\displaystyle n\to \infty }$ і ${\displaystyle np={\text{constant}},}$

цей розподіл є розподілом Пуассона для великих n і np=константі.

У статті 1960 року Ердеша і Реньї[5] дуже точно описано поведінку ${\displaystyle G(n,p)}$ для різних значень p. Їхні результати включають:

• Якщо np < 1, то граф ${\displaystyle G(n,p)}$ не буде майже напевно мати зв'язних компонент розміру, більшого ніж O(log(n)).
• Якщо np=1, то граф ${\displaystyle G(n,p)}$ буде майже напевно мати великі компоненти, розмір яких порядку n^2/3.
• Якщо ${\displaystyle np\to c>1}$, де c є константою, то граф ${\displaystyle G(n,p)}$ буде майже напевно мати єдину гігантську компоненту, що містить додатну частку вершин. Ніяка інша компонента не буде мати більше ніж O(log(n)) вершин.
• Якщо ${\displaystyle p<{\tfrac {(1-\varepsilon )\ln n}{n}}}$, то граф ${\displaystyle G(n,p)}$ буде майже напевно містити ізольовані вершини, а тому буде незв'язним.
• Якщо ${\displaystyle p>{\tfrac {(1+\varepsilon )\ln n}{n}}}$, то граф ${\displaystyle G(n,p)}$ буде майже напевно зв'язним.

Таким чином, ${\displaystyle {\tfrac {\ln n}{n}}}$ є точною пороговою ймовірністю для зв'язності ${\displaystyle G(n,p)}$.

Подальші властивості графу можна описати майже точно при прямуванні n до нескінченності. Наприклад, існує k(n) (приблизно рівний 2log₂(n)), такий, що найбільша кліка в ${\displaystyle G(n,0,5)}$ має майже напевно або розмір k(n), або ${\displaystyle k(n)+1}$[6].

Тоді, хоча задача знаходження розміру найбільшої кліки в графі NP-повна, розмір найбільшої кліки в типовому графі (відповідно до цієї моделі) добре зрозумілий.

Двоїсті за ребрами графи графів Ердеша — Реньї є графами з майже тими ж розподілами степенів, але з кореляцією степенів і істотно вищим коефіцієнтом кластеризації[7].

В теорії перколяції досліджується скінченний або нескінченний граф і випадково видаляються ребра (або зв'язки). Тоді процес Ердеша — Реньї, фактично, є незваженою перколяцією на повному графі. Оскільки теорія перколяції має глибокі корені у фізиці, значне число досліджень зроблено для ґраток в евклідових просторах. Перехід при np=1 від гігантської компоненти до малої компоненти має аналоги для цих графів, але для ґраток точку переходу важко визначити. Фізики часто говорять про вивчення повного графу як про метод самоузгодженого поля. Тоді процес Ердеша — Реньї є випадком середнього поля перколяції.

Деякі суттєві роботи зроблено також для перколяції на випадкових графах. З фізичної точки зору модель залишається моделлю середнього поля, так що мотивування досліджень часто формулюється в термінах стійкості графу, що розглядається як мережа комунікації. Нехай дано випадковий граф з ${\displaystyle n\gg 1}$ вузлами з середнім степенем <k>. Видалимо частку ${\displaystyle 1-p'}$ вузлів і залишимо частку p мережі. Існує критичний поріг просочування ${\displaystyle p'_{c}={\tfrac {1}{\langle k\rangle }}}$, нижче від якого мережа стає фрагментованою, тоді як вище від порогу ${\displaystyle p'_{c}}$ існує гігантська зв'язна компонента порядку n. Відносний розмір гігантської компоненти ${\displaystyle P_{\infty }}$ задається формулою[5][1][2][8]

${\displaystyle P_{\infty }=p'[1-\exp(-\langle k\rangle P_{\infty })].\,}$

Головні припущення обох моделей ${\displaystyle G(n,p)}$ (що ребра незалежні і що кожне ребро однаково ймовірне) можуть бути неприйнятними для моделювання деяких явищ реального життя. Зокрема, розподіл степенів вершин графів Ердеша — Реньї не має важких хвостів розподілу, тоді як вважається, що розподіл має важкий хвіст у багатьох реальних мережах. Більш того, графи Ердеша — Реньї мають низьку кластеризацію, що не має місця в багатьох соціальних мережах. Для популярних альтернатив моделей див. статті Модель Барабаші — Альберт і Модель Воттса — Строгаца. Ці альтернативні моделі не є процесами перколяції, а натомість є моделями зростання і перемонтажу, відповідно. Модель взаємодії мереж Ердеша — Реньї нещодавно (2010) розвивали Булдирєв зі співавторами[9].

Модель ${\displaystyle G(n,p)}$ першим запропонував Едгар Гільберт у статті 1959 року вивчаючи згаданий вище поріг зв'язності[3]. Модель ${\displaystyle G(n,M)}$ запропонували Ердеш і Реньї в їхній статті 1959 року. Як і у випадку Гільберта, вони досліджували зв'язність ${\displaystyle G(n,M)}$, а детальніший аналіз проведено 1960 року.

• Граф Радо, утворено розширенням моделі ${\displaystyle G(n,p)}$ на графи зі зліченним числом вершин. На відміну від скінченного випадку, результат цього нескінченного процесу є (з імовірністю 1) тим самим графом з точністю до ізоморфізму.
• Двофазне розгортання описує шляхи, в яких властивості, асоційовані з моделлю Ердеша — Реньї, призводять до появи порядку в системах.
• Експоненціальні моделі випадкових графів описують загальний імовірнісний розподіл графів на «n» вузлах, що отримується при заданих мережевих статистиках, і різних параметрів, пов'язаних з ними.
• Стохастична блокова модель, узагальнення моделі Ердеша — Реньї для графів з прихованими структурами.
• Модель Воттса — Строгаца.
• Модель Барабаші — Альберт.

• Райгородский А. М. Модели случайных графов. — М. : МЦНМО, 2011. — ISBN 978-5-94057-840-6.
• Douglas B. West. Introduction to Graph Theory. — 2001. — ISBN 0-13-014400-2.
• Newman M. E. J. Networks: An Introduction. — 2010.
• Reuven Cohen, Shlomo Havlin. Complex Networks: Structure, Robustness and Function. — 2010.