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

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

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

Содержание

1 Определение
2 Сравнение двух моделей
3 Свойства G (n, p)
4 Отношение к просачиванию
5 Предостережения
6 История
7 См. Также
8 Ссылки
9 Литература
10 Веб-ссылки

Определение

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

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

В модели G (n, M) граф выбирается равномерно случайным образом из набора всех графов, которые имеют n узлов и M ребер. Например, в модели G (3, 2) каждый из трех возможных графов на трех вершинах и двух ребрах включен с вероятностью 1/3.
В модели G (n, p) a Граф строится путем случайного соединения узлов. Каждое ребро входит в граф с вероятностью p независимо от всех остальных ребер. Эквивалентно, все графы с n узлами и M ребрами имеют равную вероятность

p M (1 - p) (n 2) - M. {\ displaystyle p ^ {M} (1-p) ^ {{n \ choose 2} -M}.}

p ^ M (1-p) ^ {{n \ choose 2} -M}.

Параметр p в этой модели можно рассматривать как весовую функцию; по мере увеличения p от 0 до 1 модель с большей вероятностью будет включать графы с большим количеством ребер и с меньшей и меньшей вероятностью включать графы с меньшим количеством ребер. В частности, случай p = 0,5 соответствует случаю, когда выбраны все

2 (n 2) {\ displaystyle 2 ^ {\ binom {n} {2}}}

2 ^ \ binom {n} {2}

графы на n вершинах с равной вероятностью.

Поведение случайных графов часто изучается в случае, когда n - количество вершин, стремится к бесконечности. Хотя p и M в этом случае можно зафиксировать, они также могут быть функциями, зависящими от n. Например, утверждение

Почти каждый граф в G (n, 2ln (n) / n) связан.

означает

Поскольку n стремится к бесконечности, вероятность того, что граф на n вершинах с вероятностью ребра 2ln (n) / n связано, стремится к 1.

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

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

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

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

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

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

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

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

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

P (deg ⁡ (v) = k) → (n p) k e - n p k! как n → ∞ и np = константа, {\ displaystyle P (\ deg (v) = k) \ to {\ frac {(np) ^ {k} \ mathrm {e} ^ {- np}} {k!} } \ quad {\ text {as}} n \ to \ infty {\ text {and}} np = {\ text {constant}},}

{\ 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 года Эрдеш и Реньи очень точно описали поведение G (n, p) для различных значений p. Их результаты включали следующее:

Если np < 1, then a graph in G(n, p) will almost surely have no connected components of size larger than O(log(n)).
Если np = 1, то граф в G (n, p) почти наверняка будет иметь самый большой компонент, размер которого имеет порядок n.
Если np → c>1, где c - константа, то граф в G (n, p) почти наверняка будет иметь единственную гигантскую компоненту, содержащую положительную долю вершин. Никакой другой компонент не будет содержать более O (log (n)) вершин.
Если $p < ( 1 − ε) ln ⁡ n n {\displaystyle p<{\tfrac {(1-\varepsilon)\ln n}{n}}}$ ${\ displaystyle p <{\ tfrac {(1- \ varepsilon) \ ln n} {n}}}$ , то граф в G (n, p) почти наверняка будет содержать изолированные вершины и, следовательно, будет несвязным.
Если $p>(1 + ε) ln ⁡ nn {\ displaystyle p>{\ tfrac {(1+ \ varepsilon) \ ln n} {n}}}$ $p>{ \ tfrac {(1+ \ varepsilon) \ ln n} {n}}$ , тогда граф в G (n, p) почти наверняка будет связан.

Таким образом, $ln ⁡ nn {\ displaystyle {\ tfrac {\ ln n} {n} }}$ ${\ displaystyle {\ tfrac {\ ln n} {n} }}$ - это связность G (n, p).

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

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

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

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

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

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

P ∞ = p ′ [1 - exp ⁡ (- ⟨k⟩ P ∞)]. {\ displaystyle P _ {\ infty} = p '[1- \ exp (- \ langle k \ rangle P _ {\ infty})]. \,}

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) до графов с счетно бесконечным числом вершин. В отличие от конечного случая, результатом этого бесконечного процесса является (с вероятностью 1 ) тот же граф, с точностью до изоморфизма.
Двухфазная эволюция - процесс, который стимулирует самоорганизацию в сложных адаптивных системах описывает способы, которыми свойства, связанные с моделью Эрдеша – Реньи, способствуют возникновению порядка в системах.
Экспоненциальные модели случайных графов описывают общее распределение вероятностей графов на "n" узлах для заданного набора сетевой статистики и различных параметров, связанных с ними.
Стохастическая блочная модель, обобщение модели Эрдеша – Реньи для графов со скрытой структурой сообщества
Модель Уоттса – Строгаца
Модель Барабаши – Альберта

Ссылки

Литература

West, Douglas B. (2001). Введение в теорию графов (2-е изд.). Прентис Холл. ISBN 0-13-014400-2.
Ньюман, М. Э. Дж. (2010). Сети: Введение. Оксфорд.
Реувен Коэн и Шломо Хэвлин (2010). Сложные сети: структура, надежность и функции. Cambridge University Press.

Веб-ссылки

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