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

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

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

Модели

Случайный граф получается, если начать с набора из 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 года «О случайных графах». и независимо Гилбертом в его статье «Случайные графы».

См. также

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