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

Модель Эрдёша — Реньи — это одна из двух тесно связанных моделей генерации случайных графов. Модели названы именами математиков Пала Эрдёша и Альфреда Реньи, которые первыми представили одну из моделей в 1959 году^[1][2], в то время как Эдгар Гильберт предложил другую модель одновременно и независимо от Эрдёша и Реньи^[3]. В модели Эрдёша и Реньи все графы с фиксированным набором вершин и фиксированным набором рёбер одинаково вероятны. В модели, предложенной Гильбертом, каждое ребро имеет фиксированную вероятность присутствия или отсутствия, независимую от других рёбер. Эти модели можно использовать в вероятностном методе для доказательства существования графов, удовлетворяющих различным свойствам или для обеспечения точного определения, это для свойства понимается, что оно выполняется для почти всех графов.

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

• В модели ${\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.

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (13 мая 2019) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (13 мая 2019) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.