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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение[править | править код]

Имеется две тесно связанные варианта модели Эрдёша — Реньи случайного графа.

Граф, сгенерированный биномиальной моделью Эрдёша — Реньи (p = 0,01)
  • В модели граф выбирается однородно и случайно из набора всех графов, которые имеют n вершин и M рёбер. Например, в модели каждый из трёх возможных графов с тремя вершинами и двумя рёбрами выбираются с вероятностью 1/3.
  • В модели граф строится путём случайного добавления рёбер. Каждое ребро включается в граф с вероятностью p независимо от остальных рёбер. Эквивалентно, все графы с n узлами и M рёбрами имеют одинаковую вероятность.
Параметр p в этой модели можно рассматривать как функцию веса. По мере роста p от 0 к 1 модель включает с большей вероятностью графы с бо́льшим числом рёбер. В частности, случай p=0,5 соответствует случаю, когда все графы с n вершинами будут выбраны с равной вероятностью.

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

Почти все графы в связны

означает

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

Сравнение двух моделей[править | править код]

Математическое ожидание числа рёбер в равно и по закону больших чисел любой граф в будет почти наверняка иметь примерно это число рёбер. Поэтому, грубо говоря, если , то G(n,p) должен вести себя подобно G(n, M) с при росте n.

Для многих свойств графа это имеет место. Если P является любым свойством графа, которое монотонно по отношению к упорядочению подграфов (это означает, что если A есть подграф графа B и A удовлетворяет P, то B будет удовлетворять также P), то утверждения «P имеет место для почти всех графов в » и «P имеет место для почти всех графов в » эквивалентны (при ). Например, это выполняется, если P есть свойство быть связным, или если P есть свойство иметь гамильтонов цикл. Однако это не будет обязательно выполняться для немонотонных свойств (например, свойство иметь чётное число рёбер).

На практике, модель одна из наиболее используемых сегодня, частично из-за простоты анализа, которую даёт независимость рёбер.

Свойства графа [править | править код]

С вышеприведёнными обозначениями граф в имеет в среднем рёбер. Распределение степени вершин биномиально[4]:

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

при и

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

В статье 1960 года Эрдёша и Реньи[5] описали поведение очень точно для различных значений p. Их результаты включают:

  • Если np < 1, то граф в не будет почти наверняка иметь связных компонент размера, большего O(log(n)).
  • Если np=1, то граф в будет почти наверняка иметь большие компоненты, размер которых порядка n2/3.
  • Если , где c является константой, то граф в будет почти наверняка иметь единственную гигантскую компоненту, содержащую положительную долю вершин. Никакая другая компонента не будет иметь более чем O(log(n)) вершин.
  • Если , то граф в будет почти наверняка содержит изолированные вершины, а потому будет несвязным.
  • Если , то граф в будет почти наверняка связен.

Таким образом, является точной пороговой вероятностью для связности .

Дальнейшие свойства графа могут быть описаны почти точно при стремлении n к бесконечности. Например, существует k(n) (примерно равный 2log2(n)), такой, что наибольшая клика в имеет почти наверняка либо размер k(n), либо [6].

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

Двойственные по рёбрам графы графов Эрдёша — Реньи являются графами с почти теми же распределениями степеней, но с корреляцией степеней и существенно более высоким коэффициентом кластеризациеи[en][7].

Отношение к перколяции[править | править код]

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

Некоторые существенные работы были сделаны также для перколяции на случайных графах. С физической точки зрения модель остаётся моделью среднего поля, так что мотивировка исследований часто формулируется в терминах устойчивости графа, рассматриваемого как сеть коммуникации. Пусть дан случайный граф с узлами со средней степенью <k>. Удалим долю узлов и оставим долю p′ сети. Существует критический порог просачивания , ниже которого сеть становится фрагментированной, в то время как выше порога существует гигантская связная компонента порядка n. Относительный размер гигантской компоненты задаётся формулой[5][1][2][8].

Предупреждения[править | править код]

Главные предположения обеих моделей (что рёбра независимы и что каждое ребро одинаково вероятно) могут быть неприемлемыми для моделирования некоторых явлений реальной жизни. В частности, распределение степеней вершин графов Эрдёша — Реньи не имеет тяжёлых хвостов распределения, в то время как считается, что распределение имеет тяжёлый хвост во многих реальных сетях. Более того, графы Эрдёша — Реньи имеют низкую кластеризацию, что не имеет место во многих социальных сетях. Для популярных альтернатив моделей см. статьи Модель Барабаши — Альберт и Модель Уаттса и Строугэтса[en]. Эти альтернативные модели не являются процессами перколяции, а вместо этого являются моделями роста и перемонтажа, соответственно. Модель взаимодействия сетей Эрдёша — Реньи недавно развивали Булдырев с соавторами[9].

История[править | править код]

Модель первым предложил Эдгар Гильберт в статье 1959 года изучая упомянутый выше порог связности[3]. Модель предложили Эрдёш и Реньи в их статье 1959 года. Как и в случае Гильберта, они исследовали связность , а более детальный анализ был проведён в 1960 году.

См. также[править | править код]

Примечания[править | править код]

  1. 1 2 Erdős, Rényi, 1959, с. 290–297.
  2. 1 2 Bollobás, 2001.
  3. 1 2 Gilbert, 1959, с. 1141–1144.
  4. Newman, Strogatz, Watts, 2001, с. 026118.
  5. 1 2 (Erdős, Rényi 1960, 17–61) Используемая здесь вероятность p относится к
  6. Matula, 1972, с. A-382.
  7. Ramezanpour, Karimipour, Mashaghi, 2003, с. 046107.
  8. Bollobás, Erdős, 1976, с. 419–427.
  9. Buldyrev, Parshani, Paul, Stanley, Havlin, 2010, с. 1025–8.

Литература[править | править код]

Литература для дальнейшего чтения[править | править код]