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

Граф Эрдеша – Реньи – Гилберта с 1000 вершинами при критической вероятности ребра. $p=1/(n-1)$, показывающий большой компонент и множество мелких

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

Определение

Существует два тесно связанных варианта модели случайных графов Эрдеша – Реньи.

График, созданный биномиальной моделью Эрдеша и Реньи ( p = 0,01).

• В $G(n,M)$ модели граф выбирается равномерно случайным образом из совокупности всех графов, имеющих $n$ узлы и $M$ края. Узлы считаются помеченными, то есть графы, полученные друг из друга перестановкой вершин, считаются различными. Например, в $G(3,2)$ В модели имеется три двуреберных графа на трех помеченных вершинах (по одному для каждого выбора средней вершины в двухреберном пути), и каждый из этих трех графов включен с вероятностью ${\tfrac {1}{3}}$.
• В $G(n,p)$ В модели граф строится путем случайного соединения помеченных узлов. Каждое ребро входит в граф с вероятностью $p$, независимо от любого другого ребра. Эквивалентно, вероятность создания каждого графа, который имеет $n$ узлы и $M$ края это $$p^{M}(1-p)^{{n \choose 2}-M}.$$ Параметр $p$ в этой модели ее можно рассматривать как весовую функцию; как $p$ увеличивается с $0$ к $1$, модель становится все более и более склонной включать графы с большим количеством ребер и все менее и менее вероятно включать графы с меньшим количеством ребер. В частности, случай $p={\tfrac {1}{2}}$ соответствует случаю, когда все $2^{\binom {n}{2}}$ графики на $n$ вершины выбираются с равной вероятностью.

Поведение случайных графов часто изучают в случае, когда $n$, число вершин, стремится к бесконечности. Хотя $p$ и $M$ в этом случае могут быть фиксированными, они также могут быть функциями в зависимости от $n$. Например, утверждение о том, что почти каждый график в $G(n,2\ln(n)/n)$ связан, означает, что, поскольку $n$ стремится к бесконечности, вероятность того, что график на $n$ вершины с вероятностью ребра $2\ln(n)/n$ связан, имеет тенденцию $1$.

Сравнение двух моделей

Ожидаемое количество ребер в G ( n , p ) равно ${\tbinom {n}{2}}p$, и по закону больших чисел любой граф в G ( n , p ) почти наверняка будет иметь примерно такое же количество ребер (при условии, что ожидаемое количество ребер стремится к бесконечности). Следовательно, грубая эвристика состоит в том, что если pn ² → ∞, то G ( n , p ) должен вести себя аналогично G ( n , M ) с $M={\tbinom {n}{2}}p$ по мере увеличения n .

Для многих свойств графа это так. Если P — любое свойство графа, которое монотонно относительно порядка подграфов (это означает, что если A — подграф B и B удовлетворяет P , то A также будет удовлетворять P ), тогда утверждения « P справедливы почти для всех графов в G ( n , p )" и " P выполняется почти для всех графов в $G(n,{\tbinom {n}{2}}p)$" эквивалентны (при условии, что pn ² → ∞). Например, это справедливо, если P является свойством связности или если P является свойством содержать гамильтонов цикл . Однако это не обязательно будет справедливо для немонотонных свойств (например, свойства наличия четного числа ребер).

На практике G ( n , p сегодня чаще используется модель ), отчасти из-за простоты анализа, обеспечиваемой независимостью ребер.

Свойства G ( n , p )

С учетом приведенных выше обозначений граф в G ( n , p ) имеет в среднем ${\tbinom {n}{2}}p$ края. Распределение степени любой конкретной вершины является биномиальным :

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

где n — общее количество вершин в графе. С

$P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\text{ as }}n\to \infty {\text{ and }}np={\text{constant}},$

это распределение является пуассоновским для больших n и np = const.

В статье 1960 года Эрдеш и Реньи очень точно описал поведение G ( n , p ) для различных значений p . Их результаты включали следующее:

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

Таким образом ${\tfrac {\ln n}{n}}$ является резким порогом связности G ( n , p ).

Дальнейшие свойства графа можно описать почти точно при стремлении n к бесконечности. Например, существует k ( n ) (приблизительно равное 2log ₂ ( n )), такое что наибольшая клика в G ( n , 0,5) почти наверняка имеет либо размер k ( n ), либо k ( n )+1.

Таким образом, хотя определение размера наибольшей клики в графе является NP-полным , размер наибольшей клики в «типичном» графе (согласно этой модели) очень хорошо понятен.

Реберно-двойственные графы графов Эрдеша-Реньи — это графы с почти таким же распределением степеней, но с корреляциями степеней и значительно более высоким коэффициентом кластеризации .

Отношение к перколяции

В теории перколяции исследуют конечный или бесконечный граф и случайным образом удаляют ребра (или связи). Таким образом, процесс Эрдеша-Реньи на самом деле представляет собой перколяцию невзвешенных связей на полном графе . (Один из них относится к перколяции, при которой узлы и/или связи удаляются с разнородными весами, как взвешенная перколяция). Поскольку теория перколяции во многом уходит корнями в физику , большая часть исследований была посвящена решеткам в евклидовых пространствах. Переход при np = 1 от гигантской компоненты к малой имеет аналоги для этих графиков, но для решеток точку перехода определить сложно. Физики часто называют изучение полного графа теорией среднего поля . Таким образом, процесс Эрдеша – Реньи представляет собой случай перколяции среднего поля.

Некоторая значительная работа была также проделана по просачиванию на случайных графах. С точки зрения физика это все равно будет модель среднего поля, поэтому обоснование исследования часто формулируется с точки зрения надежности графа, рассматриваемого как коммуникационная сеть. Дан случайный граф из n ≫ 1 узлов со средней степенью $\langle k\rangle$. Удалить случайно дробь $1-p'$ узлов и оставьте только часть $p'$ из сети. Существует критический порог перколяции. $p'_{c}={\tfrac {1}{\langle k\rangle }}$ ниже которого сеть становится фрагментированной, а выше $p'_{c}$ существует гигантская компонента связности порядка n . Относительный размер гигантского компонента P _∞ определяется выражением

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

Предостережения

Оба основных предположения модели G ( n , p ) (о том, что ребра независимы и что каждое ребро одинаково вероятно) могут быть непригодны для моделирования некоторых явлений реальной жизни. Графики Эрдеша-Реньи имеют низкую кластеризацию, в отличие от многих социальных сетей. Некоторые альтернативы моделирования включают модель Барабаши-Альберта и модель Уоттса и Строгаца . Эти альтернативные модели не являются процессами просачивания, а представляют собой модели роста и перестройки соответственно. Еще одним альтернативным семейством моделей случайных графов, способных воспроизводить многие явления реальной жизни, являются экспоненциальные модели случайных графов .

История

Модель G ( n , p ) была впервые представлена ​​Эдгаром Гилбертом в статье 1959 года, посвященной упомянутому выше порогу связности. Модель G ( n , M ) была представлена ​​Эрдёшем и Реньи в их статье 1959 года. Как и в случае с Гилбертом, их первые исследования касались связности G ( n , M ), а более подробный анализ последовал в 1960 году.

Континуальное предельное представление критического G ( n , p )

Броуновское движение с квадратичным отрицательным дрейфом разлагается на броуновские отклонения уменьшающихся размеров.

Непрерывный предел графа был получен, когда $p$ в порядке $1/n$. В частности, рассмотрим последовательность графов $G_{n}:=G(n,1/n+\lambda n^{-{\frac {4}{3}}})$ для $\lambda \in \mathbb {R}$. Предел объекта может быть построен следующим образом:

• Сначала создадим диффузию $W^{\lambda }(t):=W(t)+\lambda t-{\frac {t^{2}}{2}}$ где $W$ является стандартным броуновским движением .
• Из этого процесса мы определяем отраженный процесс $R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)$. Этот процесс можно рассматривать как содержащий множество последовательных отклонений (не совсем броуновских, см. ). Потому что дрейф $W^{\lambda }$ преобладает $-{\frac {t^{2}}{2}}$, эти экскурсии становятся все короче и короче по мере того, как $t\to +\infty$. В частности, их можно отсортировать в порядке убывания длины: мы можем разделить $\mathbb {R}$ на интервалы $(C_{i})_{i\in \mathbb {N} }$ уменьшающейся длины такой, что $R^{\lambda }$ ограничено $C_{i}$ является броуновским экскурсом для любого $i\in \mathbb {N}$.
• Теперь рассмотрим экскурсию $(e(s))_{s\in [0,1]}$. Постройте случайный граф следующим образом:

  

  Броуновский экскурс $(e(t))_{t\in [0,1]}$. Здесь процесс $\Xi$ имеет одну точку, отмеченную красной точкой. Красная линия соответствует одному внутреннему узлу соответствующего дерева. $T_{e}$зеленая линия соответствует листу $T_{e}$. Если добавить ребро между двумя узлами, получится граф с одним циклом.

  • Построить настоящее дерево $T_{e}$ (см. Броуновское дерево ).
  • Рассмотрим точечный процесс Пуассона $\Xi$ на $[0,1]\times \mathbb {R} _{+}$ с единичной интенсивностью. К каждой точке $(x,s)\in \Xi$ такой, что $x\leq e(s)$, соответствует базовому внутреннему узлу и листу дерева $T_{e}$. Определив две вершины, дерево $T_{e}$ становится графиком $\Gamma _{e}$

Применяя эту процедуру, получаем последовательность случайных бесконечных графов уменьшающихся размеров: $(\Gamma _{i})_{i\in \mathbb {N} }$. Теорема утверждает, что этот граф в определенном смысле соответствует предельному объекту $G_{n}$ как $n\to +\infty$.

См. также

• Граф Радо — бесконечный граф, содержащий все счетные графы, граф, сформированный путем расширения модели G ( n , p ) до графов со счетным бесконечным числом вершин. В отличие от конечного случая, результатом этого бесконечного процесса является (с вероятностью 1 ) один и тот же граф с точностью до изоморфизма.
• Двухфазная эволюция - процесс, который стимулирует самоорганизацию в сложных адаптивных системах, описывает способы, которыми свойства, связанные с моделью Эрдеша-Реньи, способствуют возникновению порядка в системах.
• Экспоненциальные модели случайных графов - статистические модели для сетевого анализа. Страницы, отображающие описания викиданных в качестве запасного варианта, описывают общее распределение вероятностей графов на «n» узлах с учетом набора сетевой статистики и различных параметров, связанных с ними.
• Стохастическая блочная модель , обобщение модели Эрдеша – Реньи для графов со скрытой структурой сообщества.
• Модель Уоттса – Строгаца – метод генерации случайных графов маленького мира
• Модель Барабаши – Альберта – Алгоритм создания безмасштабной сети

Литература

• Уэст, Дуглас Б. (2001). Введение в теорию графов (2-е изд.). Прентис Холл. ISBN  0-13-014400-2 .
• Ньюман, МЭД (2010). Сети: Введение . Оксфорд.

Внешние ссылки

• Видео: случайный граф Эрдеша-Реньи