В математической области теории графов модель Эрдеша – Реньи представляет собой либо две тесно связанных модели для генерации случайных графов, либо эволюцию случайной сети . Они названы в честь венгерских математиков Пола Эрдеша и Альфреда Реньи , которые впервые представили одну из моделей в 1959 году [1] [2], в то время как Эдгар Гилберт представил другую модель одновременно и независимо от Эрдеша и Реньи. [3]В модели Эрдеша и Реньи все графы на фиксированном множестве вершин с фиксированным числом ребер равновероятны; в модели, введенной Гилбертом, каждое ребро имеет фиксированную вероятность присутствия или отсутствия, независимо от других ребер. Эти модели могут использоваться в вероятностном методе для доказательства существования графов, удовлетворяющих различным свойствам, или для обеспечения строгого определения того, что означает выполнение свойства почти для всех графов.
Определение
Существует два тесно связанных варианта модели случайных графов Эрдеша – Реньи.
- в модели, граф выбирается равномерно случайным образом из набора всех графов, которые имеют узлы и края. Узлы считаются помеченными, что означает, что графы, полученные друг от друга путем перестановки вершин, считаются различными. Например, в модели есть три двухреберных графа на трех помеченных вершинах (по одному для каждого выбора средней вершины в двухреберном пути), и каждый из этих трех графов включен с вероятностью .
- в В модели граф строится путем случайного соединения помеченных узлов. Каждое ребро входит в граф с вероятностью, независимо от любого другого края. Эквивалентно вероятность создания каждого графа, имеющего узлы и края Параметр в этой модели можно рассматривать как весовую функцию; в виде увеличивается с к , модель с большей вероятностью будет включать графы с большим количеством ребер и с меньшей и меньшей вероятностью включать графы с меньшим количеством ребер. В частности, дело соответствует случаю, когда все графики на вершины выбираются с равной вероятностью.
Поведение случайных графов часто исследуют в случае, когда , количество вершин стремится к бесконечности. Хотя а также могут быть исправлены в этом случае, они также могут быть функциями в зависимости от . Например, утверждение, что почти каждый график в связано означает, что, поскольку стремится к бесконечности, вероятность того, что граф на вершины с вероятностью ребра связан имеет тенденцию к .
Сравнение двух моделей
Ожидаемое количество ребер в G ( n , p ) равно, и по закону больших чисел любой граф в G ( n , p ) почти наверняка будет иметь примерно такое же количество ребер (при условии, что ожидаемое количество ребер стремится к бесконечности). Следовательно, грубая эвристика состоит в том, что если pn 2 → ∞, то G ( n , p ) должен вести себя аналогично G ( n , M ) спри увеличении n .
Это так для многих свойств графа. Если P - любое свойство графа, которое монотонно относительно упорядочения подграфов (это означает, что если A является подграфом B и A удовлетворяет P , то B также удовлетворяет P ), то утверждения « P верны почти для всех графов в G ( n , p ) "и" P выполняется почти для всех графов в"эквивалентны (при условии, что pn 2 → ∞). Например, это верно, если P является свойством связности или если P является свойством содержать гамильтонов цикл . Однако это не обязательно будет выполняться для немонотонных свойств ( например, свойство иметь четное количество ребер).
На практике сегодня чаще всего используется модель G ( n , p ), отчасти из-за простоты анализа, обеспечиваемой независимостью ребер.
Свойства G ( n , p )
С учетом приведенных выше обозначений граф в G ( n , p ) в среднем имееткрая. Распределение степени любой конкретной вершины биномиально : [4]
где n - общее количество вершин в графе. С
это распределение является пуассоновским для больших n и np = const.
В статье 1960 года Эрдеш и Реньи [5] очень точно описали поведение 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 ) почти наверняка будет содержать изолированные вершины и, следовательно, будет несвязным.
- Если , то граф в G ( n , p ) почти наверняка будет связным.
Таким образом является точным порогом связности G ( n , p ).
Дальнейшие свойства графа можно описать почти точно, поскольку n стремится к бесконечности. Например, существует k ( n ) (приблизительно равное 2log 2 ( n )) такое, что наибольшая клика в G ( n , 0,5) почти наверняка имеет размер k ( n ) или k ( n ) + 1. [ 6]
Таким образом, даже несмотря на то, что определение размера самой большой клики в графе является NP-полным , размер самой большой клики в «типичном» графе (согласно этой модели) очень хорошо изучен.
Графы с двойным ребром графов Эрдеша-Реньи - это графы с почти одинаковым распределением степеней, но со степенью корреляции и значительно более высоким коэффициентом кластеризации . [7]
Отношение к перколяции
В теории перколяции изучается конечный или бесконечный граф и случайным образом удаляются ребра (или связи). Таким образом, процесс Эрдеша – Реньи на самом деле является невзвешенной перколяцией ссылок на полный граф . (Один относится к перколяции, при которой узлы и / или связи удаляются с разнородными весами как взвешенная перколяция). Поскольку теория перколяции в значительной степени уходит корнями в физику , большая часть исследований проводилась на решетках в евклидовых пространствах. Переход при np = 1 от гигантской компоненты к малой имеет аналоги для этих графиков, но для решеток точку перехода определить сложно. Физики часто называют изучение полного графа теорией среднего поля . Таким образом, процесс Эрдеша – Реньи является среднеполевым случаем перколяции.
Также была проделана значительная работа по перколяции случайных графов. С точки зрения физика это все равно будет моделью среднего поля, поэтому обоснование исследования часто формулируется в терминах надежности графа, рассматриваемого как сеть связи. Для случайного графа из n ≫ 1 узлов со средней степенью . Удалить случайным образом дробь узлов и оставьте только часть из сети. Существует критический порог перколяции. ниже которого сеть становится фрагментированной, а выше существует гигантская связная компонента порядка n . Относительный размер гигантского компонента P ∞ определяется формулой [5] [1] [2] [8]
Предостережения
Оба основных допущения модели G ( n , p ) (что ребра независимы и что каждое ребро одинаково вероятно) могут не подходить для моделирования некоторых реальных явлений. Графы Эрдеша – Реньи имеют низкую кластеризацию, в отличие от многих социальных сетей. [ Править ] Некоторые варианты моделирования включают Barabási-Альберт модели и ватты и Строгац модель . Эти альтернативные модели не являются процессами перколяции, а вместо этого представляют собой модель роста и перепрограммирования соответственно. Модель взаимодействия сетей Эрдеша – Реньи была недавно разработана Булдыревым и др. [9]
История
Модель G ( n , p ) была впервые представлена Эдгаром Гилбертом в статье 1959 года, в которой изучается упомянутый выше порог связности. [3] Модель G ( n , M ) была введена Эрдешем и Реньи в их статье 1959 года. Как и в случае с Гилбертом, их первые исследования касались связности G ( n , M ), а в 1960 году последовал более подробный анализ.
Смотрите также
- Граф Радо - бесконечный граф, содержащий все счетные графы, граф, образованный расширением модели G ( n , p ) до графов со счетно бесконечным числом вершин. В отличие от конечного случая, результатом этого бесконечного процесса является (с вероятностью 1 ) тот же граф, с точностью до изоморфизма.
- Двухфазная эволюция - процесс, который управляет самоорганизацией в сложных адаптивных системах, описывает способы, которыми свойства, связанные с моделью Эрдеша – Реньи, способствуют возникновению порядка в системах.
- Экспоненциальные модели случайных графов описывают общее распределение вероятностей графов на «n» узлах с учетом набора сетевой статистики и различных параметров, связанных с ними.
- Стохастическая блочная модель , обобщение модели Эрдеша – Реньи для графов со скрытой структурой сообщества.
- Модель Уоттса – Строгаца
- Модель Барабаши – Альберта
Рекомендации
- ^ a b Erdős, P .; Реньи, А. (1959). «О случайных графах. I» (PDF) . Publicationes Mathematicae . 6 : 290–297.
- ^ а б Боллобаш, Б. (2001). Случайные графы (2-е изд.). Издательство Кембриджского университета. ISBN 0-521-79722-5.
- ^ а б Гилберт, EN (1959). «Случайные графы» . Анналы математической статистики . 30 (4): 1141–1144. DOI : 10.1214 / АОМ / 1177706098 .
- ^ Ньюман, Марк. EJ; Strogatz, SH; Уоттс, ди-джей (2001). «Случайные графы с произвольными распределениями степеней и их приложения». Physical Review E . 64 : 026118. arXiv : cond-mat / 0007235 . Bibcode : 2001PhRvE..64b6118N . DOI : 10.1103 / PhysRevE.64.026118 . PMID 11497662 ., Уравнение (1)
- ^ а б Erdős, P .; Реньи, А. (1960). «Об эволюции случайных графов» (PDF) . Мадьяр Тудоманьос Академия Математикаи Кутато Интезетенек Кезлеменьей [Публикации Математического института Венгерской академии наук] . 5 : 17–61.Вероятность p, используемая здесь, относится к
- ^ Матула, Дэвид В. (февраль 1972 г.). «Сотрудник партийной проблемы». Уведомления Американского математического общества . 19 : А-382.
- ^ Рамезанпур, А .; Каримипур, В .; Машаги, А. (апрель 2003 г.). «Создание коррелированных сетей из некоррелированных». Physical Review E . 67 (4): 046107. arXiv : cond-mat / 0212469 . Bibcode : 2003PhRvE..67d6107R . DOI : 10.1103 / PhysRevE.67.046107 . PMID 12786436 .
- ^ Bollobás, B .; Эрдеш, П. (1976). «Клики в случайных графах». Математические труды Кембриджского философского общества . 80 (3): 419–427. Bibcode : 1976MPCPS..80..419B . DOI : 10.1017 / S0305004100053056 .
- ^ Булдырев С.В.; Паршани, Р .; Paul, G .; Стэнли, HE; Хавлин, С. (2010). «Катастрофический каскад отказов во взаимозависимых сетях» . Природа . 464 (7291): 1025–8. arXiv : 0907.1182 . Bibcode : 2010Natur.464.1025B . DOI : 10,1038 / природа08932 . PMID 20393559 .
Литература
- Уэст, Дуглас Б. (2001). Введение в теорию графов (2-е изд.). Прентис Холл. ISBN 0-13-014400-2.
- Ньюман, MEJ (2010). Сети: Введение . Оксфорд.
- Реувен Коэн и Шломо Хэвлин (2010). Сложные сети: структура, надежность и функции . Издательство Кембриджского университета.
Веб ссылки
- Видео: случайный граф Эрдоша-Реньи