В математике случайный граф – это общий термин , обозначающий распределения вероятностей по графам . Случайные графы можно описать просто распределением вероятностей или случайным процессом , который их генерирует. [1] [2] Теория случайных графов находится на стыке теории графов и теории вероятностей . С математической точки зрения случайные графы используются для ответа на вопросы о свойствах типичных графов. Его практическое применение можно найти во всех областях, в которых необходимо моделировать сложные сети – таким образом, известно множество моделей случайных графов, отражающих разнообразные типы сложных сетей, встречающихся в разных областях. В математическом контексте случайный граф относится почти исключительно к модели случайного графа Эрдеша-Реньи . В других контекстах любую графовую модель можно назвать случайным графом .
Случайный граф получается, если начать с набора из n изолированных вершин и случайным образом добавить между ними последовательные ребра. Целью исследования в этой области является определение того, на каком этапе вероятно возникновение того или иного свойства графа. [3] Различные модели случайных графов создают разные распределения вероятностей на графах. Наиболее часто изучается граф, предложенный Эдгаром Гилбертом и обозначенный G ( n , p ), в котором каждое возможное ребро возникает независимо с вероятностью 0 < p <1. Вероятность получения любого конкретного случайного графа с m ребрами обозначается обозначением . [4]
Близкородственная модель, модель Эрдеша-Реньи, обозначаемая G ( n , M ), назначает равную вероятность всем графам ровно с M ребрами. При 0 ≤ M ≤ N G ( n , M ) имеет элементы, и каждый элемент встречается с вероятностью . [3] Последнюю модель можно рассматривать как снимок в определенный момент времени ( M ) процесса случайного графа , который представляет собой стохастический процесс , который начинается с n вершин и без ребер и на каждом шаге добавляет одно новое ребро, равномерно выбранное из набор недостающих ребер.
Если вместо этого мы начнем с бесконечного набора вершин и снова позволим каждому возможному ребру возникать независимо с вероятностью 0 < p <1, то мы получим объект G , называемый бесконечным случайным графом . За исключением тривиальных случаев, когда p равно 0 или 1, такой G почти наверняка обладает следующим свойством:
Для любых n + m элементов существует вершина c в V , которая смежна с каждым из и не смежна ни с одним из .
Оказывается, если множество вершин счетно , то с точностью до изоморфизма существует только один граф с этим свойством, а именно граф Радо . Таким образом, любой счетный бесконечный случайный граф почти наверняка является графом Радо, который по этой причине иногда называют просто случайным графом . Однако аналогичный результат неверен для несчетных графов, среди которых существует множество (неизоморфных) графов, удовлетворяющих указанному выше свойству.
Другая модель, которая обобщает модель случайного графа Гилберта, — это модель случайного скалярного произведения . Случайный граф скалярного произведения сопоставляет каждой вершине действительный вектор . Вероятность ребра uv между любыми вершинами u и v является некоторой функцией скалярного произведения u • v их соответствующих векторов.
Матрица вероятностей сети моделирует случайные графы с помощью вероятностей ребер, которые представляют вероятность существования данного ребра в течение определенного периода времени. Эту модель можно расширить до направленной и ненаправленной; взвешенные и невзвешенные; и статическая или динамическая структура графиков.
Для M ≃ pN , где N — максимально возможное количество ребер, две наиболее широко используемые модели, G ( n , M ) и G ( n , p ), почти взаимозаменяемы. [5]
Случайные регулярные графы представляют собой особый случай, свойства которого могут отличаться от случайных графов в целом.
Когда у нас есть модель случайных графиков, каждая функция на графике становится случайной величиной . Целью изучения этой модели является определение того, может ли или, по крайней мере, оценить вероятность того, что свойство может возникнуть. [4]
Термин «почти каждый» в контексте случайных графов относится к последовательности пространств и вероятностей, в которой вероятности ошибок стремятся к нулю. [4]
Теория случайных графов изучает типичные свойства случайных графов, которые с высокой вероятностью справедливы для графов, построенных на основе определенного распределения. Например, мы можем запросить заданное значение и какова вероятность того, что оно связано . Изучая подобные вопросы, исследователи часто концентрируются на асимптотическом поведении случайных графов — значениях, к которым сходятся различные вероятности при очень большом росте. Теория перколяции характеризует связность случайных графов, особенно бесконечно больших.
Перколяция связана с надежностью графа (также называемого сетью). Дан случайный граф узлов и средняя степень . Далее мы случайным образом удаляем часть узлов и оставляем только часть . Существует критический порог перколяции , ниже которого сеть становится фрагментированной, тогда как выше существует гигантский связный компонент. [1] [5] [6] [7] [8]
Локализованная перколяция означает удаление узла, его соседей, следующих ближайших соседей и т. д. до тех пор, пока часть узлов не будет удалена из сети. Показано, что для случайного графа с пуассоновским распределением степеней то же самое, что и для случайного удаления.
Случайные графы широко используются в вероятностном методе , где пытаются доказать существование графов с определенными свойствами. Существование свойства на случайном графе часто может подразумевать, посредством леммы о регулярности Семереди , существование этого свойства почти на всех графах.
В случайных регулярных графах , - множество -регулярных графов с такими, что и - натуральные числа, и четно. [3]
Последовательность степеней графа в зависит только от количества ребер в множествах [3]
Если ребра в случайном графе достаточно велики, чтобы гарантировать, что почти каждое из них имеет минимальную степень не ниже 1, то почти каждое ребро связно, а если оно четное, то почти каждое имеет идеальное паросочетание. В частности, в тот момент, когда последняя изолированная вершина почти в каждом случайном графе исчезает, граф становится связным. [3]
Почти каждый графовый процесс на четном числе вершин с ребром, повышающим минимальную степень до 1, или случайный граф с чуть большим количеством ребер и с вероятностью, близкой к 1, обеспечивает полное совпадение графа, за исключением не более чем одной вершины. .
Для некоторой константы почти каждый помеченный граф с вершинами и хотя бы ребрами является гамильтоновым . При вероятности, стремящейся к 1, конкретное ребро, которое увеличивает минимальную степень до 2, становится гамильтонианом графа.
Свойства случайного графа могут изменяться или оставаться неизменными при преобразованиях графа. Машаги А. и др., например, продемонстрировали, что преобразование, которое преобразует случайные графы в их двойные по ребрам графы (или линейные графы), создает ансамбль графов с почти таким же распределением степеней, но с корреляциями степеней и значительно более высокой кластеризацией. коэффициент. [9]
Дан случайный граф G порядка n с вершиной V ( G ) = {1,..., n }, с помощью жадного алгоритма по количеству цветов вершины можно раскрасить в цвета 1, 2,... (вершина 1 окрашена в цвет 1, вершина 2 окрашена в цвет 1, если она не смежна с вершиной 1, в противном случае она окрашена в цвет 2 и т. д.). [3] Число правильных раскрасок случайных графов при заданном количестве q цветов, называемое хроматическим полиномом , до сих пор остается неизвестным. Масштабирование нулей хроматического полинома случайных графов с параметрами n и числом ребер m или вероятностью соединения p исследовано эмпирически с использованием алгоритма, основанного на символьном сопоставлении с образцом. [10]
Случайное дерево — это дерево или древовидное дерево , которое формируется в результате случайного процесса . В большом диапазоне случайных графов порядка n и размера M ( n ) распределение числа компонентов дерева порядка k является асимптотически пуассоновским . Типы случайных деревьев включают однородное остовное дерево , случайное минимальное остовное дерево , случайное двоичное дерево , треп , быстрое исследование случайного дерева , броуновское дерево и случайный лес .
Рассмотрим данную модель случайного графа, определенную в вероятностном пространстве, и пусть это функция с действительным знаком, которая присваивает каждому графу вектор из m свойств. При фиксированном значении условные случайные графы представляют собой модели, в которых вероятностная мера присваивает нулевую вероятность всем графам таким, что ' .
Особыми случаями являются условно равномерные случайные графы , где всем графам с заданными свойствами присваивается равная вероятность. Их можно рассматривать как обобщение модели Эрдеша-Реньи G ( n , M ), когда обуславливающей информацией является не обязательно количество ребер M , а любое другое произвольное свойство графа . В этом случае доступно очень мало аналитических результатов, и для получения эмпирических распределений средних свойств требуется моделирование.
Самое раннее использование модели случайного графа было осуществлено Хелен Холл Дженнингс и Джейкобом Морено в 1938 году, когда «случайная социограмма» (направленная модель Эрдеша-Реньи) рассматривалась при исследовании сравнения доли взаимных ссылок в их сетевых данных со случайной моделью. . [11] Другое использование под названием «случайная сеть» было осуществлено Рэем Соломоновым и Анатолем Рапопортом в 1951 году с использованием модели ориентированных графов с фиксированной исходящей степенью и случайно выбранными привязками к другим вершинам. [12]
Модель случайных графов Эрдеша-Реньи была впервые определена Полом Эрдешем и Альфредом Реньи в их статье 1959 года «О случайных графах» [8] и независимо Гилбертом в его статье «Случайные графы». [6]