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

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список  / матрица смежности Список  / матрица заболеваемости Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
МетрикиАлгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия / SIR
СпискиКатегории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

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

Модели [ править ]

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

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

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

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

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

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

Терминология [ править ]

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

Свойства [ править ]

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

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

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

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

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

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

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

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

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

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

Свойства случайного графа могут изменяться или оставаться инвариантными при преобразованиях графа. Mashaghi A. et al., Например, продемонстрировали, что преобразование, которое преобразует случайные графы в их дуальные по ребрам графы (или линейные графы), дает ансамбль графов с почти одинаковым распределением степеней, но со степенью корреляции и значительно более высокой кластеризацией. коэффициент. ^[11]

Раскраска [ править ]

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

Случайные деревья [ править ]

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

Условные случайные графики [ править ]

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

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

Взаимозависимые графики [ править ]

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

История [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]