Модель Эрдёша — Реньи

Модель Эрдёша — Реньи — это одна из двух тесно связанных моделей генерации случайных графов. Модели названы именами математиков Пала Эрдёша и Альфреда Реньи, которые первыми представили одну из моделей в 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)}$ одна из наиболее используемых сегодня, частично из-за простоты анализа, которую даёт независимость рёбер.

Свойства графа ${\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)}$ (что рёбра независимы и что каждое ребро одинаково вероятно) могут быть неприемлемыми для моделирования некоторых явлений реальной жизни. В частности, распределение степеней вершин графов Эрдёша — Реньи не имеет тяжёлых хвостов распределения, в то время как считается, что распределение имеет тяжёлый хвост во многих реальных сетях. Более того, графы Эрдёша — Реньи имеют низкую кластеризацию, что не имеет место во многих социальных сетях. Для популярных альтернатив моделей см. статьи Модель Барабаши — Альберт и Модель Уаттса и Строугэтса^[англ.]. Эти альтернативные модели не являются процессами перколяции, а вместо этого являются моделями роста и перемонтажа, соответственно. Модель взаимодействия сетей Эрдёша — Реньи недавно развивали Булдырев с соавторами[9].

История

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

Вариации и обобщения

• Графон (теория графов) — более общая модель случайного графа.

• Граф Радо, образованный расширением модели ${\displaystyle G(n,p)}$ на графы со счётным числом вершин. В отличие от конечного случая, результат этого бесконечного процесса является (с вероятностью 1) тем же графом с точностью до изоморфизма.

• Модель Барабаши — Альберт.

Примечания

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, 17–61) Используемая здесь вероятность 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. — doi:10.1103/PhysRevE.64.026118. — Bibcode: 2001PhRvE..64b6118N. — arXiv:cond-mat/0007235., 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.
• David W. Matula. The employee party problem // Notices of the American Mathematical Society. — 1972. — Февраль (т. 19). — С. A-382.
• Ramezanpour A., Karimipour V., Mashaghi A. Generating correlated networks from uncorrelated ones // Physical Review E. — 2003. — Апрель (т. 67, вып. 4). — doi:10.1103/PhysRevE.67.046107. — Bibcode: 2003PhRvE..67d6107R. — arXiv:cond-mat/0212469.
• Erdős P., Rényi A. On Random Graphs. I // Publicationes Mathematicae. — 1959. — Т. 6.
• 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. — doi:10.1017/S0305004100053056. — Bibcode: 1976MPCPS..80..419B.
• Buldyrev S. V., Parshani R., Paul G., Stanley H. E., Havlin S. Catastrophic cascade of failures in interdependent networks // Nature. — 2010. — Т. 464, вып. 7291. — doi:10.1038/nature08932. — Bibcode: 2010Natur.464.1025B. — arXiv:0907.1182. — PMID 20393559.
• Gilbert E.N. Random Graphs // Annals of Mathematical Statistics. — 1959. — Т. 30, вып. 4. — 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.
• Complex Networks: Structure, Robustness and Function. — 2010.