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

Две тесно связанные модели для генерации случайных графов

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

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

Определение

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

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

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

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

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

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

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

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

СвойстваГ(н,п)

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

${\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!}}\quad {\text{ as }}n\to \infty {\text{ and }}np={\text{constant}},}$

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

В статье 1960 года Эрдёш и Реньи ^[6] очень точно описали поведение 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 )) вершин.
• Если , то граф в G ( n , p ) почти наверняка будет содержать изолированные вершины и, таким образом, будет несвязным. ${\displaystyle p<{\tfrac {(1-\varepsilon )\ln n}{n}}}$
• Если , то граф в G ( n , p ) почти наверняка будет связным. ${\displaystyle p>{\tfrac {(1+\varepsilon )\ln n}{n}}}$

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

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

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

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

Отношение к просачиванию

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

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

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

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

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

История

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

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

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

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

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

  

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

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

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

Смотрите также

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

Ссылки

1. Erdős, P.; Rényi, A. (1959). "On Random Graphs. I" (PDF) . Publicationes Mathematicae . 6 (3–4): 290–297. doi :10.5486/PMD.1959.6.3-4.12. S2CID  253789267. Архивировано (PDF) из оригинала 2020-08-07 . Получено 2011-02-23 .
2. Bollobás, B. (2001). Случайные графы (2-е изд.). Cambridge University Press. ISBN 0-521-79722-5.
3. Gilbert, EN (1959). «Случайные графы». Annals of Mathematical Statistics . 30 (4): 1141–1144. doi : 10.1214/aoms/1177706098 .
4. Файнберг, Стивен Э. (2012). «Краткая история статистических моделей для анализа сетей и открытых задач». Журнал вычислительной и графической статистики . 21 (4): 825–839. doi :10.1080/10618600.2012.738106. MR  3005799. S2CID  52232135.
5. Ньюман, Марк. EJ; Строгац, SH; Уоттс, DJ (2001). "Случайные графы с произвольными распределениями степеней и их приложения". Physical Review E . 64 (2): 026118. arXiv : cond-mat/0007235 . Bibcode :2001PhRvE..64b6118N. doi :10.1103/PhysRevE.64.026118. PMID  11497662. S2CID  360112., Ур. (1)
6. Эрдеш, П.; Реньи, А. (1960). «Об эволюции случайных графов» (PDF) . Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Публикации Математического института Венгерской академии наук] . 5 : 17–61. Архивировано (PDF) из оригинала 1 февраля 2021 г. Проверено 18 ноября 2011 г.Вероятность p, используемая здесь, относится к ${\displaystyle N(n)={\tbinom {n}{2}}p}$
7. Матула, Дэвид В. (февраль 1972 г.). «Проблема вечеринки служащих». Извещения Американского математического общества . 19 : A-382.
8. Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (апрель 2003 г.). «Создание коррелированных сетей из некоррелированных». Physical Review E. 67 ( 4): 046107. arXiv : cond-mat/0212469 . Bibcode : 2003PhRvE..67d6107R. doi : 10.1103/PhysRevE.67.046107. PMID  12786436. S2CID  33054818.
9. Боллобаш, Б.; Эрдёш, П. (1976). «Клики в случайных графах». Математические труды Кембриджского философского общества . 80 (3): 419–427. Bibcode : 1976MPCPS..80..419B. doi : 10.1017/S0305004100053056. S2CID  16619643.
10. Saberi, Abbas Ali (март 2015 г.). «Последние достижения в теории перколяции и ее приложениях». Physics Reports . 578 : 12. arXiv : 1504.02898 . Bibcode :2015PhR...578....1S. doi :10.1016/j.physrep.2015.03.003. S2CID  119209128 . Получено 30 января 2022 г. .
11. Addario-Berry, L.; Broutin, N.; Goldschmidt, C. (2012-04-01). "Континуальный предел критических случайных графов". Теория вероятностей и смежные области . 152 (3): 367–406. doi : 10.1007/s00440-010-0325-4 . ISSN  1432-2064. S2CID  253980763.
12. Олдос, Дэвид (1 апреля 1997 г.). «Броуновские экскурсии, критические случайные графы и мультипликативные коалесценты». Анналы вероятности . 25 (2). doi : 10.1214/aop/1024404421 . ISSN  0091-1798. S2CID  16578106.

Литература

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

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

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