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

Модель Ердеша — Реньї — це одна з двох тісно пов'язаних моделей генерування випадкових графів. Моделі названо іменами математиків Пала Ердеша і Альфреда Реньї, які першими представили одну з них 1959 року^[1][2], тоді як Едгар Гільберт запропонував іншу модель одночасно і незалежно від Ердеша і Реньї^[3]. У моделі Ердеша і Реньї всі графи з фіксованим набором вершин і фіксованим набором ребер однаково ймовірні. У моделі, запропонованій Гільбертом, кожне ребро має фіксовану ймовірність присутності або відсутності, незалежну від інших ребер. Ці моделі можна використовувати в імовірнісному методі для доведення існування графів, що мають певні властивості, або для забезпечення точного визначення, це для властивості розуміється, що означає «властивість зберігається майже для всіх графів».

Визначення

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

Граф, згенерований біноміальною моделлю Ердеша — Реньї (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)}$ одна з найвикористовуваніших сьогодні, частково через простоту аналізу, яку дає незалежність ребер.

Властивості графу G ( n , 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) тим самим графом з точністю до ізоморфізму.
• Двофазне розгортання^[en] описує шляхи, в яких властивості, асоційовані з моделлю Ердеша — Реньї, призводять до появи порядку в системах.
• Експоненціальні моделі випадкових графів^[en] описують загальний імовірнісний розподіл графів на «n» вузлах, що отримується при заданих мережевих статистиках, і різних параметрів, пов'язаних з ними.
• Стохастична блокова модель^[en], узагальнення моделі Ердеша — Реньї для графів з прихованими структурами.
• Модель Воттса — Строгаца.
• Модель Барабаші — Альберт.

Примітки

1. Erdős, Rényi, 1959, с. 290–297.
2. Bollobás, 2001.
3. Gilbert, 1959, с. 1141–1144.
4. Newman, Strogatz, Watts, 2001, с. 026118.
5. (Erdős, Rényi, 1960) Використана тут імовірність p стосується ${\displaystyle N(n)={\tbinom {n}{2}}p}$
6. Matula, 1972, с. A-382.
7. Ramezanpour, Karimipour, Mashaghi, 2003, с. 046107.
8. Bollobás, Erdős, 1976, с. 419–427.
9. Buldyrev, Parshani, Paul, Stanley, Havlin, 2010, с. 1025–8.

Література

• Mark E. J. Newman, Strogatz S. H., Watts D. J. Random graphs with arbitrary degree distributions and their applications // Physical Review E. — 2001. — Т. 64 (10 листопада). — arXiv:cond-mat/0007235. — Bibcode:2001PhRvE..64b6118N. — DOI:10.1103/PhysRevE.64.026118., Eq. (1)
• Erdős P., Rényi A. On the evolution of random graphs // Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences]. — 1960. — Т. 5 (10 листопада). Архівовано з джерела 1 лютого 2021. Процитовано 4 січня 2021.
• David W. Matula. The employee party problem // Notices of the American Mathematical Society. — 1972. — Т. 19 (February). — С. A-382.
• Ramezanpour A., Karimipour V., Mashaghi A. Generating correlated networks from uncorrelated ones // Physical Review E. — 2003. — Т. 67, вип. 4 (April). — arXiv:cond-mat/0212469. — Bibcode:2003PhRvE..67d6107R. — DOI:10.1103/PhysRevE.67.046107.
• Erdős P., Rényi A. On Random Graphs. I // Publicationes Mathematicae. — 1959. — Т. 6 (10 листопада). Архівовано з джерела 7 серпня 2020. Процитовано 4 січня 2021.
• Bollobás B. Random Graphs. — 2nd. — 2001. — ISBN 0-521-79722-5.
• Bollobás B., Erdős P. Cliques in Random Graphs // Mathematical Proceedings of the Cambridge Philosophical Society. — 1976. — Т. 80, вип. 3 (10 листопада). — Bibcode:1976MPCPS..80..419B. — DOI:10.1017/S0305004100053056.
• Buldyrev S. V., Parshani R., Paul G., Stanley H. E., Havlin S. Catastrophic cascade of failures in interdependent networks // Nature. — 2010. — Т. 464, вип. 7291 (10 листопада). — arXiv:0907.1182. — Bibcode:2010Natur.464.1025B. — DOI:10.1038/nature08932. — PMID 20393559 . Архівовано з джерела 18 жовтня 2017. Процитовано 4 січня 2021.
• Gilbert E.N. Random Graphs // Annals of Mathematical Statistics. — 1959. — Т. 30, вип. 4 (10 листопада). — DOI:10.1214/aoms/1177706098.

Література для подальшого читання

• Райгородский А. М. Модели случайных графов. — М. : МЦНМО, 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.  — 2010. Архівовано з джерела 4 жовтня 2011