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

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

Граф Эрдеша-Реньи-Гилберта с 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 )

Согласно приведенным выше обозначениям, граф в 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 ) почти наверняка будет иметь наибольшую компоненту размера порядка n2 ^/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 году.

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

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

Континуальный предел графа был получен, когда имеет порядок . ^[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] утверждает, что этот граф в определенном смысле соответствует предельному объекту as . ${\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. Эрдеш, П.; Реньи, А. (1959). «О случайных графах. I» (PDF) . Публикации Mathematicae . 6 (3–4): 290–297. дои : 10.5486/PMD.1959.6.3-4.12. S2CID  253789267. Архивировано (PDF) из оригинала 7 августа 2020 г. Проверено 23 февраля 2011 г.
2. Боллобас, Б. (2001). Случайные графики (2-е изд.). Издательство Кембриджского университета. ISBN 0-521-79722-5.
3. Гилберт, EN (1959). «Случайные графики». Анналы математической статистики . 30 (4): 1141–1144. дои : 10.1214/aoms/1177706098 .
4. Финберг, Стивен Э. (2012). «Краткая история статистических моделей для сетевого анализа и открытых задач». Журнал вычислительной и графической статистики . 21 (4): 825–839. дои : 10.1080/10618600.2012.738106. МР  3005799. S2CID  52232135.
5. Ньюман, Марк. Э.Дж.; Строгац, С.Х.; Уоттс, диджей (2001). «Случайные графы с произвольным распределением степеней и их приложения». Физический обзор E . 64 (2): 026118. arXiv : cond-mat/0007235 . Бибкод : 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 : А-382.
8. Рамезанпур, А.; Каримипур, В.; Машаги, А. (апрель 2003 г.). «Генерация коррелированных сетей из некоррелированных». Физический обзор E . 67 (4): 046107. arXiv : cond-mat/0212469 . Бибкод : 2003PhRvE..67d6107R. doi : 10.1103/PhysRevE.67.046107. PMID  12786436. S2CID  33054818.
9. Боллобас, Б.; Эрдеш, П. (1976). «Клики в случайных графах». Математические труды Кембриджского философского общества . 80 (3): 419–427. Бибкод : 1976MPCPS..80..419B. дои : 10.1017/S0305004100053056. S2CID  16619643.
10. Сабери, Аббас Али (март 2015 г.). «Последние достижения в теории перколяции и ее приложениях». Отчеты по физике . 578 : 12. arXiv : 1504.02898 . Бибкод : 2015ФР...578....1С. doi :10.1016/j.physrep.2015.03.003. S2CID  119209128 . Проверено 30 января 2022 г.
11. Аддарио-Берри, Л.; Броутен, Н.; Гольдшмидт, К. (1 апреля 2012 г.). «Континуальный предел критических случайных графов». Теория вероятностей и смежные области . 152 (3): 367–406. дои : 10.1007/s00440-010-0325-4 . ISSN  1432-2064. S2CID  253980763.
12. Олдос, Дэвид (1 апреля 1997 г.). «Броуновские экскурсии, критические случайные графы и мультипликативное слияние». Анналы вероятности . 25 (2). дои : 10.1214/аоп/1024404421 . ISSN  0091-1798. S2CID  16578106.

Литература

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

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

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