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

Случайный ориентированный граф с 20 узлами и вероятностью наличия ребра 0.1, иначе говоря — реализация графа Гильберта G(20; 0.1).

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

Модели случайных графов

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

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

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

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

Если заданы любые n + m элементов ${\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}}$.

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

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

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

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

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

Если мы имеем модель случайных графов, любая функция на графах становится случайной величиной. Задача изучения этой модели — определить, или, по крайней мере, оценить вероятность появления свойства[3].

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

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

Свойства случайных графов

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

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

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

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

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

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

Если множество рёбер M в случайном графе G_M достаточно большое, чтобы почти все G_M имели минимальную степень не меньше 1, то почти любой G_M связен и, для чётного n, почти любой G_M содержит совершенное паросочетание. В частности, в момент, когда исчезает последняя изолированная вершина, почти во всех случайных графах, граф становится связным[2].

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

Для некоторой константы c почти каждый помеченный граф с n вершинами и как минимум cnlog(n) рёбрами является гамильтоновым. С вероятностью, стремящейся к 1, добавление ребра, увеличивающее минимальную степень графа до 2, делает его гамильтоновым.

Раскраска случайных графов

Если задан случайный граф G порядка n с вершинами V(G) = {1, …, n}, раскраску можно получить с помощью жадного алгоритма (вершина 1 выкрашивается цветом 1, вершина 2 получает цвет 1 если она не смежна 1, в противном получает цвет 2, и так далее)[2].

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

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

История

Случайные графы впервые определены Эрдёшем и Реньи в книге 1959 года «On Random Graphs»[8] и независимо Гильбертом в его статье «Random graphs»[5].

См. также

• Граф Радо
• Сложные сети
• Перколяция

Примечания

1. Béla Bollobás^[англ.]. Random Graphs. — Cambridge University Press, 2001.
2. Béla Bollobás^[англ.]. Random Graphs. — London: Academic Press Inc, 1985.
3. Béla Bollobás^[англ.]. Probabilistic Combinatorics and Its Applications. — Providence: American Mathematical Society, 1991.
4. Mathematical results on scale-free random graphs. Handbook of Graphs and Networks / S. Bornholdt, H. G. Schuster. — Weinheim: Wiley VCH, 2003.
5. E. N. Gilbert. Random graphs. — Annals of Mathematical Statistics. — 1959. — Т. 30. — С. 1141—1144. — doi:10.1214/aoms/1177706098.
6. M. E. J. Newman. Networks: An Introduction. — Oxford, 2010.
7. Reuven Cohen, Shlomo Havlin. Complex Networks: Structure, Robustness and Function. — Cambridge University Press, 2010. Архивировано 4 октября 2011 года.
8. P. Erdős, A Rényi. On Random Graphs I. — Publ. Math. — 1959. — Т. 6. — С. 290—297. Архивировано 7 августа 2020 года.

Литература

• А.М. Райгородский. Модели случайных графов. — М.: МЦНМО, 2011. — 136 с. — ISBN 978-5-94057-840-6.