Случайный график - Random graph

Для счетно-бесконечного случайного графа см. График Rado.

В математика, случайный граф это общий термин для обозначения распределения вероятностей над графики. Случайные графы могут быть описаны просто распределением вероятностей или случайный процесс который их порождает.^[1][2] Теория случайных графов лежит на пересечении теория графов и теория вероятности. С математической точки зрения случайные графы используются для ответа на вопросы о свойствах типичный графики. Его практическое применение можно найти во всех областях, в которых сложные сети необходимо моделировать - таким образом, известно много моделей случайных графов, отражающих различные типы сложных сетей, встречающихся в различных областях. В математическом контексте случайный граф относится почти исключительно к Модель случайного графа Эрдеша – Реньи. В других контекстах любую модель графа можно назвать случайный граф.

Модели

Случайный граф получается, начиная с набора п изолированные вершины и случайным образом добавляя друг к другу рёбра. Цель исследования в этой области - определить, на каком этапе может возникнуть то или иное свойство графа.^[3] Другой модели случайных графов производить разные распределения вероятностей на графиках. Наиболее часто изучается вариант, предложенный Эдгар Гилберт, обозначенный г(п,п), в котором каждое возможное ребро встречается независимо с вероятностью 0 < п <1. Вероятность получения любой конкретный случайный граф с м края ${\displaystyle p^{m}(1-p)^{N-m}}$ с обозначениями ${\displaystyle N={\tbinom {n}{2}}}$.^[4]

Тесно родственная модель, Модель Эрдеша – Реньи обозначенный г(п,M), назначает равную вероятность всем графам с точно M края. При 0 ≤ M ≤ N, г(п,M) имеет ${\displaystyle {\tbinom {N}{M}}}$ элементы, и каждый элемент встречается с вероятностью ${\displaystyle 1/{\tbinom {N}{M}}}$.^[3] Последнюю модель можно рассматривать как снимок в определенное время (M) из случайный граф ${\displaystyle {\tilde {G}}_{n}}$, который является случайный процесс что начинается с п вершин и без ребер, и на каждом шаге добавляет одно новое ребро, равномерно выбираемое из множества отсутствующих ребер.

Если вместо этого мы начнем с бесконечного набора вершин и снова позволим каждому возможному ребру возникать независимо с вероятностью 0 < п <1, то получаем объект г называется бесконечный случайный граф. За исключением тривиальных случаев, когда п равно 0 или 1, такое г почти наверняка обладает следующим свойством:

Учитывая любые п + м элементы ${\displaystyle a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V}$, есть вершина c в V который примыкает к каждому из ${\displaystyle a_{1},\ldots ,a_{n}}$ и не граничит ни с одним из ${\displaystyle b_{1},\ldots ,b_{m}}$.

Оказывается, если множество вершин счетный тогда есть, вплоть до изоморфизм, только один граф с этим свойством, а именно График Rado. Таким образом, любой счетно бесконечный случайный граф почти наверняка является графом Радо, который по этой причине иногда называют просто графом. случайный граф. Однако аналогичный результат неверен для несчетных графов, из которых существует много (неизоморфных) графов, удовлетворяющих вышеуказанному свойству.

Другая модель, которая обобщает модель случайных графов Гилберта, - это модель модель случайного скалярного произведения. Случайный граф скалярного произведения сопоставляет каждой вершине a реальный вектор. Вероятность перевеса УФ между любыми вершинами ты и v некоторая функция скалярное произведение ты • v соответствующих векторов.

В матрица вероятностей сети моделирует случайные графы через вероятности ребер, которые представляют вероятность ${\displaystyle p_{i,j}}$ что данный край ${\displaystyle e_{i,j}}$ существует в течение указанного периода времени. Эта модель расширяется до направленной и ненаправленной; взвешенные и невзвешенные; и статическая или динамическая структура графов.

Для M ≃ pN, где N максимально возможное количество ребер, две наиболее широко используемые модели, г(п,M) и г(п,п), практически взаимозаменяемы.^[5]

Случайные регулярные графы образуют частный случай со свойствами, которые могут отличаться от случайных графов в целом.

Когда у нас есть модель случайных графиков, каждая функция на графиках становится случайная переменная. Изучение этой модели состоит в том, чтобы определить, или, по крайней мере, оценить вероятность того, что свойство может появиться.^[4]

Терминология

Термин «почти каждый» в контексте случайных графов относится к последовательности пространств и вероятностей, такой что вероятности ошибки стремятся к нулю.^[4]

Свойства

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

Перколяция связана с надежностью графа (также называемого сетью). Учитывая случайный график ${\displaystyle n}$ узлы и средняя степень ${\displaystyle \langle k\rangle }$. Далее мы случайным образом удаляем дробь ${\displaystyle 1-p}$ узлов и оставьте только часть ${\displaystyle p}$. Существует критический порог перколяции ${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$ ниже которого сеть становится фрагментированной, а выше ${\displaystyle p_{c}}$ существует гигантская связная компонента.^{[1][5][6][7][8][9]}

Локализованная перколяция означает удаление узла его соседей, следующих ближайших соседей и т. Д. До тех пор, пока не будет достигнута доля ${\displaystyle 1-p}$ узлов из сети удаляется. Было показано, что для случайного графа с пуассоновским распределением степеней ${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$ точно так же, как при случайном удалении. Для других типов степеней распределения ${\displaystyle p_{c}}$ для локализованной атаки отличается от случайной атаки^[10](пороговые функции, эволюция ${\displaystyle {\tilde {G}}}$)

Случайные графы широко используются в вероятностный метод, где пытаются доказать существование графов с определенными свойствами. Существование свойства на случайном графе часто может подразумевать через Лемма Семереди о регулярности, существование этого свойства почти на всех графах.

В случайные регулярные графы, ${\displaystyle G(n,r-reg)}$ это набор ${\displaystyle r}$-регулярные графы с ${\displaystyle r=r(n)}$ такой, что ${\displaystyle n}$ и ${\displaystyle m}$ натуральные числа, ${\displaystyle 3\leq r<n}$, и ${\displaystyle rn=2m}$ даже.^[3]

Последовательность степеней графа ${\displaystyle G}$ в ${\displaystyle G^{n}}$ зависит только от количества ребер в наборах^[3]

${\displaystyle V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.}$

Если края, ${\displaystyle M}$ в случайном графе, ${\displaystyle G_{M}}$ достаточно большой, чтобы гарантировать, что почти каждый ${\displaystyle G_{M}}$ имеет минимальную степень не менее 1, то почти каждый ${\displaystyle G_{M}}$ связано и, если ${\displaystyle n}$ ровно, почти каждый ${\displaystyle G_{M}}$ имеет идеальное соответствие. В частности, в момент, когда последняя изолированная вершина обращается в нуль почти в каждом случайном графе, граф становится связным.^[3]

Почти каждый граф обрабатывает четное число вершин с ребром, увеличивающим минимальную степень до 1, или случайный граф с чуть более чем ${\displaystyle {\tfrac {n}{4}}\log(n)}$ ребер и с вероятностью, близкой к 1, гарантирует, что граф имеет полное соответствие, за исключением не более одной вершины.

Для некоторой постоянной ${\displaystyle c}$, почти каждый помеченный граф с ${\displaystyle n}$ вершины и не менее ${\displaystyle cn\log(n)}$ края Гамильтониан. С вероятностью, стремящейся к 1, конкретное ребро, которое увеличивает минимальную степень до 2, делает граф гамильтонианом.

Свойства случайного графа могут изменяться или оставаться инвариантными при преобразованиях графа. Машаги А. и др., например, продемонстрировали, что преобразование, которое преобразует случайные графы в их графы с двойным ребром (или линейные графы), дает ансамбль графов с почти одинаковым распределением степеней, но со степенью корреляции и значительно более высоким коэффициентом кластеризации.^[11]

Окраска

Учитывая случайный граф г порядка п с вершиной V(г) = {1, ..., п}, посредством жадный алгоритм по количеству цветов вершины можно раскрасить в цвета 1, 2, ... (вершина 1 окрашена в 1, вершина 2 окрашена в 1, если она не смежна с вершиной 1, в противном случае она окрашена в 2 и т. д.) .^[3]Количество правильных раскрасок случайных графов при заданном количестве q цвета, названные его хроматический полином, пока остается неизвестным. Масштабирование нулей хроматического полинома случайных графов с параметрами п и количество ребер м или вероятность соединения п был изучен эмпирически с использованием алгоритма, основанного на символьном сопоставлении с образцом.^[12]

Случайные деревья

Основная статья: Случайное дерево

А случайное дерево это дерево или древообразование который формируется случайный процесс. В большом количестве случайных графиков порядка п и размер M(п) распределение количества составляющих дерева порядка k асимптотически Пуассон. Типы случайных деревьев включают единое остовное дерево, случайное минимальное остовное дерево, случайное двоичное дерево, трогать, быстрое изучение случайного дерева, Броуновское дерево, и случайный лес.

Условные случайные графы

Рассмотрим данную модель случайного графа, определенную на вероятностном пространстве ${\displaystyle (\Omega ,{\mathcal {F}},P)}$ и разреши ${\displaystyle {\mathcal {P}}(G):\Omega \rightarrow R^{m}}$ быть вещественной функцией, которая присваивается каждому графику в ${\displaystyle \Omega }$ вектор м свойства. Для фиксированного ${\displaystyle \mathbf {p} \in R^{m}}$, условные случайные графы модели, в которых вероятностная мера ${\displaystyle P}$ присваивает нулевую вероятность всем графам, таким что '${\displaystyle {\mathcal {P}}(G)\neq \mathbf {p} }$.

Особые случаи условно однородные случайные графы, где ${\displaystyle P}$ присваивает равную вероятность всем графам с заданными свойствами. Их можно рассматривать как обобщение Модель Эрдеша – Реньи г(п,M), когда условной информацией не обязательно является количество ребер M, но любое другое свойство произвольного графа ${\displaystyle {\mathcal {P}}(G)}$. В этом случае доступно очень мало аналитических результатов, и требуется моделирование для получения эмпирических распределений средних свойств.

Взаимозависимые графы

Во взаимозависимых графах узлы в одной сети (графе) зависят от функционирования других сетей. Таким образом, сбои в одном или нескольких графах вызывают каскадные отказы между графами, которые могут привести к внезапному коллапсу.^[13][14]

История

Самое раннее использование модели случайного графа было Хелен Холл Дженнингс и Джейкоб Морено в 1938 г., когда «случайная социограмма» (направленная модель Эрдеша-Реньи) рассматривалась при изучении сравнения доли взаимных связей в их сетевых данных со случайной моделью.^[15] Другое использование под названием «случайная сеть» было сделано Соломоновым и Рапопортом в 1951 году, когда они использовали модель ориентированных графов с фиксированной исходящей степенью и случайно выбранными присоединениями к другим вершинам.^[16]

В Модель Эрдеша – Реньи случайных графов был впервые определен Пол Эрдёш и Альфред Реньи в своей статье 1959 г. «О случайных графах»^[9] и независимо Гилбертом в его статье «Случайные графы».^[6]

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

• Конденсация Бозе – Эйнштейна: подход теории сетей
• Метод полости
• Сложные сети
• Двухфазная эволюция
• Модель Эрдеша – Реньи
• Модель экспоненциального случайного графа
• Теория графов
• Взаимозависимые сети
• Сетевая наука
• Перколяция
• Теория перколяции
• Регулярный график
• Сеть без масштабирования
• Полулинейный отклик
• Стохастическая блочная модель
• Тест Lancichinetti – Fortunato – Radicchi

использованная литература

1. Боллобаш, Бела (2001). Случайные графы (2-е изд.). Издательство Кембриджского университета.
2. Frieze, Алан; Каронски, Михал (2015). Введение в случайные графы. Издательство Кембриджского университета.
3. Béla Bollobás, Случайные графы, 1985, Academic Press Inc., London Ltd.
4. Béla Bollobás, Вероятностная комбинаторика и ее приложения, 1991, Провиденс, Род-Айленд: Американское математическое общество.
5. Боллобас, Б. и Риордан, О. «Математические результаты по безмасштабным случайным графам» в «Справочнике по графам и сетям» (С. Борнхольдт и Х. Г. Шустер (редакторы)), Wiley VCH, Weinheim, 1-е изд., 2003 г.
6. Гилберт, Э. (1959), «Случайные графы», Анналы математической статистики, 30 (4): 1141–1144, Дои:10.1214 / aoms / 1177706098.
7. Ньюман, М. Э. Дж. (2010). Сети: введение. Оксфорд.
8. Реувен Коэн и Шломо Хавлин (2010). Сложные сети: структура, надежность и функции. Издательство Кембриджского университета.
9. Эрдеш, П. Реньи, А (1959) «О случайных графах I» в Publ. Математика. Дебрецен 6, стр. 290–297 [1]
10. Шао, Шуай; Хуанг, Сюцин; Стэнли, Х. Юджин; Хавлин, Шломо (2015). «Распространение локальных атак на сложные сети». Новый журнал физики. 17 (2): 023049. arXiv:1412.3124. Bibcode:2015NJPh ... 17b3049S. Дои:10.1088/1367-2630/17/2/023049. ISSN  1367-2630.
11. Рамезанпур, А .; Каримипур, В .; Машаги, А. (2003). «Создание коррелированных сетей из некоррелированных». Phys. Ред. E. 67 (46107): 046107. arXiv:cond-mat / 0212469. Bibcode:2003PhRvE..67d6107R. Дои:10.1103 / PhysRevE.67.046107. PMID  12786436.
12. Ван Бассел, Франк; Эрлих, Кристоф; Флигнер, Денни; Штольценберг, Себастьян; Тимм, Марк (2010). «Хроматические многочлены случайных графов». J. Phys. A: Математика. Теор. 43 (17): 175002. arXiv:1709.06209. Bibcode:2010JPhA ... 43q5002V. Дои:10.1088/1751-8113/43/17/175002.
13. Булдырев, Сергей В .; Паршани, Рони; Пол, Джеральд; Стэнли, Х. Юджин; Хавлин, Шломо (2010). «Катастрофический каскад отказов во взаимозависимых сетях». Природа. 464 (7291): 1025–1028. arXiv:1012.0206. Bibcode:2010Натура.464.1025Б. Дои:10.1038 / природа08932. ISSN  0028-0836. PMID  20393559.
14. Гао, Цзяньси; Булдырев, Сергей В .; Стэнли, Х. Юджин; Хавлин, Шломо (2011). «Сети, образованные из взаимозависимых сетей». Природа Физика. 8 (1): 40–48. Bibcode:2012НатФ ... 8 ... 40Г. CiteSeerX  10.1.1.379.8214. Дои:10.1038 / nphys2180. ISSN  1745-2473.
15. Морено, Джейкоб Л; Дженнингс, Хелен Холл (январь 1938 г.). «Статистика социальных конфигураций». Социометрия. 1 (3/4): 342–374. Дои:10.2307/2785588. JSTOR  2785588.
16. Соломонов, Рэй; Рапопст, Анатолий (июнь 1951 г.). «Связность случайных сетей». Бюллетень математической биофизики. 13 (2): 107–117. Дои:10.1007 / BF02478357.