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

Чтобы узнать о счетно-бесконечном случайном графе, см. График Радо .

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

Модели

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

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

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

Учитывая любые n + m элементов $a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V$ существует вершина c, , в 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 ), почти взаимозаменяемы.

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

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

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

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

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

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

Перколяция связана с надежностью графа (также называемого сетью). Учитывая случайный график $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 }}$ точно так же, как и при случайном удалении.

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

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

Последовательность степеней графа $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.$

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

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

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

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

Раскраска

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

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

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

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

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

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

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

История

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

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

См. также

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