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

редактировать

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

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

Содержание

1 Модели
2 Терминология
3 Свойства
4 Раскраска
5 Случайные деревья
6 Условные случайные графы
7 Взаимозависимые графы
8 История
9 См. Также
10 Ссылки

Модели

Случайный граф получается путем начала набора из n изолированных вершин и добавления последовательных ребер между ними случайным образом. Цель исследования в этой области - определить, на каком этапе может возникнуть то или иное свойство графа. Различные модели случайных графов производят разные распределения вероятностей на графиках. Чаще всего изучается вариант, предложенный Эдгаром Гилбертом, обозначенный G (n, p), в котором каждое возможное ребро встречается независимо с вероятностью 0 < p < 1. The probability of obtaining any one particular random graph with m edges is $pm (1 - p) N - m {\ displaystyle p ^ {m} (1-p) ^ {Nm}}$ $p ^ {m} (1-p) ^ {Nm}$ с обозначением $N = (n 2) {\ displaystyle N = {\ tbinom {n} {2}}}$ $N = {\ tbinom {n} {2 }}$ .

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

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

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

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

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

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

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

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

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

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

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

Свойства

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

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

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

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

В случайных регулярных графах, $G (n, r - reg) { \ displaystyle G (n, r-reg)}$ ${\ displaystyle G (n, r-reg)}$ - это набор $r {\ displaystyle r}$ $r$ -регулярных графиков с $r = r (n) { \ displaystyle r = r (n)}$ ${\ displaystyle r = r (n)}$ таким образом, что $n {\ displaystyle n}$ $n$ и $m {\ displaystyle m}$ $m$ являются натуральные числа, $3 ≤ r < n {\displaystyle 3\leq r$ ${\ displaystyle 3 \ leq r <n}$ и $rn = 2 m {\ displaystyle rn = 2m}$ ${\ displaystyle rn = 2m}$ четное.

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

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

V_ {n} ^ {(2)} = \ left \ {ij \: \ 1 \ leq j \ leq n, i \ neq j \ right \} \ subset V ^ {(2)}, \ qquad я знак равно 1, \ cdots, n.

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

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

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

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

Раскраска

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

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

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

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

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

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

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

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

История

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

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