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

Имеется две тесно связанные варианта модели Эрдёша — Реньи случайного графа.

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

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

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

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

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

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