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

График, созданный случайным процессом

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

Модели

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

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

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

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

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

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

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

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

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

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

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

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

Характеристики

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

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

Локализованная перколяция означает удаление узла, его соседей, следующих ближайших соседей и т. д. до тех пор, пока часть узлов не будет удалена из сети. Показано, что для случайного графа с пуассоновским распределением степеней то же самое, что и для случайного удаления. ${\displaystyle 1-p}$ ${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$

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

В случайных регулярных графах , - множество -регулярных графов с такими, что и - натуральные числа, и четно. ^[3] ${\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}}$

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

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

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

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

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

Раскраска

Дан случайный граф G порядка n с вершиной V ( G ) = {1,..., n }, с помощью жадного алгоритма по количеству цветов вершины можно раскрасить в цвета 1, 2,... (вершина 1 окрашена в цвет 1, вершина 2 окрашена в цвет 1, если она не смежна с вершиной 1, в противном случае она окрашена в цвет 2 и т. д.). ^[3] Число правильных раскрасок случайных графов при заданном количестве q цветов, называемое хроматическим многочленом , до сих пор остается неизвестным. Масштабирование нулей хроматического полинома случайных графов с параметрами n и числом ребер m или вероятностью соединения p исследовано эмпирически с использованием алгоритма, основанного на символьном сопоставлении с образцом. ^[10]

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

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

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

Рассмотрим данную модель случайного графа, определенную в вероятностном пространстве, и пусть это функция с действительным знаком, которая присваивает каждому графу вектор из m свойств. При фиксированном значении условные случайные графы представляют собой модели, в которых вероятностная мера присваивает нулевую вероятность всем графам таким, что ' . ${\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} }$

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

История

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

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

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

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

Рекомендации

1. Боллобас, Бела (2001). Случайные графики (2-е изд.). Издательство Кембриджского университета.
2. Фриз, Алан; Каронски, Михал (2015). Введение в случайные графы . Издательство Кембриджского университета.
3. Бела Боллобас , Случайные графики , 1985, Academic Press Inc., London Ltd.
4. Бела Боллобас , Вероятностная комбинаторика и ее приложения , 1991, Провиденс, Род-Айленд: Американское математическое общество.
5. Боллобас, Б. и Риордан, О.М. «Математические результаты для безмасштабных случайных графов» в «Справочнике по графикам и сетям» (С. Борнхолдт и Х.Г. Шустер (редакторы)), Wiley VCH, Weinheim, 1-е изд., 2003 г.
6. Гилберт, EN (1959), «Случайные графики», Анналы математической статистики , 30 (4): 1141–1144, doi : 10.1214/aoms/1177706098.
7. Ньюман, MEJ (2010). Сети: Введение . Оксфорд.
8. Эрдеш, П. Реньи, А (1959) «О случайных графах I» в Publ. Математика. Дебрецен 6, с. 290–297 [1] Архивировано 7 августа 2020 г. в Wayback Machine.
9. Рамезанпур, А.; Каримипур, В.; Машаги, А. (2003). «Генерация коррелированных сетей из некоррелированных». Физ. Преподобный Е. 67 (46107): 046107. arXiv : cond-mat/0212469 . Бибкод : 2003PhRvE..67d6107R. doi : 10.1103/PhysRevE.67.046107. PMID  12786436. S2CID  33054818.
10. Ван Бассел, Фрэнк; Эрлих, Кристоф; Флигнер, Денни; Стольценберг, Себастьян; Тимме, Марк (2010). «Хроматические полиномы случайных графов». Дж. Физ. А: Математика. Теор . 43 (17): 175002. arXiv : 1709.06209 . Бибкод : 2010JPhA...43q5002V. дои : 10.1088/1751-8113/43/17/175002. S2CID  15723612.
11. Морено, Джейкоб Л.; Дженнингс, Хелен Холл (январь 1938 г.). «Статистика социальных конфигураций» (PDF) . Социометрия . 1 (3/4): 342–374. дои : 10.2307/2785588. JSTOR  2785588.
12. Соломонов, Рэй; Рапопорт, Анатолий (июнь 1951 г.). «Связность случайных сетей». Вестник математической биофизики . 13 (2): 107–117. дои : 10.1007/BF02478357.