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

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

Модели

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для некоторой константы почти каждый помеченный граф с вершинами и по крайней мере ребрами является гамильтоновым . С вероятностью, стремящейся к 1, конкретное ребро, которое увеличивает минимальную степень до 2, делает граф гамильтоновым. $c$ $n$ $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 асимптотически пуассоново . Типы случайных деревьев включают однородное остовное дерево , случайное минимальное остовное дерево , случайное бинарное дерево , treap , быстро исследуемое случайное дерево , броуновское дерево и случайный лес .

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

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

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

История

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

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

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

Ссылки

^ аб Боллобас, Бела (2001). Случайные графики (2-е изд.). Издательство Кембриджского университета.
^ Фриз, Алан; Каронски, Михал (2015). Введение в случайные графы . Cambridge University Press.
^ abcdef Бела Боллобаш , Случайные графы , 1985, Academic Press Inc., London Ltd.
^ abc Бела Боллобаш , Вероятностная комбинаторика и ее приложения , 1991, Провиденс, Род-Айленд: Американское математическое общество.
^ ab Bollobas, B. и Riordan, OM "Математические результаты по случайным графам без масштабирования" в "Справочнике по графам и сетям" (редакторы S. Bornholdt и HG Schuster), Wiley VCH, Weinheim, 1-е изд., 2003
^ ab Gilbert, EN (1959), «Случайные графы», Annals of Mathematical Statistics , 30 (4): 1141–1144, doi : 10.1214/aoms/1177706098.
^ Newman, MEJ (2010). Сети: Введение . Оксфорд.
^ Аб Эрдеш, П. Реньи, А (1959) «О случайных графах I» в Publ. Математика. Дебрецен 6, с. 290–297 [1] Архивировано 7 августа 2020 г. в Wayback Machine.
^ Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003). "Создание коррелированных сетей из некоррелированных". Phys. Rev. E. 67 ( 46107): 046107. arXiv : cond-mat/0212469 . Bibcode : 2003PhRvE..67d6107R. doi : 10.1103/PhysRevE.67.046107. PMID 12786436. S2CID 33054818.
^ Ван Бассел, Фрэнк; Эрлих, Кристоф; Флигнер, Денни; Стольценберг, Себастьян; Тимме, Марк (2010). «Хроматические полиномы случайных графов». Дж. Физ. А: Математика. Теор . 43 (17): 175002. arXiv : 1709.06209 . Бибкод : 2010JPhA...43q5002V. дои : 10.1088/1751-8113/43/17/175002. S2CID 15723612.
^ Морено, Джейкоб Л.; Дженнингс, Хелен Холл (январь 1938 г.). «Статистика социальных конфигураций» (PDF) . Социометрия . 1 (3/4): 342–374. doi :10.2307/2785588. JSTOR 2785588.
^ Соломонов, Рэй; Рапопорт, Анатолий (июнь 1951 г.). «Связность случайных сетей». Бюллетень математической биофизики . 13 (2): 107–117. doi :10.1007/BF02478357.