Випадковий граф

У математиці випадковий граф — це загальний термін для позначення імовірнісного розподілу графів. Випадкові графи можна описати просто розподілом ймовірності або випадковим процесом, що створює ці графи^[1]. Теорія випадкових графів лежить на стику теорії графів і теорії ймовірностей. З математичної точки зору, випадкові графи необхідні для відповіді на питання про властивості типових графів. Випадкові графи знайшли практичне застосування у всіх галузях, де потрібно змоделювати складні мережі — відома велика кількість моделей випадкових графів, що відображають різноманітні типи складних мереж у різних галузях. У математичному контексті термін випадковий граф означає майже завжди модель випадкових графів Ердеша — Реньї. В інших контекстах будь-яка модель графів означає випадковий граф.

У Вікіпедії є статті про інші значення цього терміна: Граф Радо.

Моделі випадкових графів

Випадковий граф отримують із множини n ізольованих вершин шляхом послідовного випадкового додавання ребер, що з'єднують вершини. Метою моделювання випадкових графів є визначення того, на якому етапі з'являється певна властивість графу^[2]. Різні моделі випадкових графів дають різні розподіли ймовірностей на графі.

Найчастіше вивчається розподіл, запропонований Гільбертом^[en], що позначається ${\displaystyle G(n,p)}$, в якому будь-яке можливе ребро з'являється незалежно з імовірністю ${\displaystyle 0<p<1}$. Ймовірність отримання графу з m ребрами дорівнює ${\displaystyle {\tbinom {N}{m}}}$ ${\displaystyle p^{m}(1-p)^{N-m}}$ де ${\displaystyle N={\tbinom {n}{2}}}$^[3].

Близька до нього модель Ердеша — Реньї, що позначається G(n,M), дає однакову ймовірність для всіх графів, які мають рівно M ребер. Якщо позначити ${\displaystyle N={n \choose 2},}$ з 0 ≤ M ≤ N, G(n,p) буде містити ${\displaystyle {N \choose M}}$ елементів і будь-який елемент випадає з імовірністю ${\displaystyle {N \choose M}^{-1}}$^[2]. Цю модель можна розглядати як знімок для деякого моменту часу (M) випадкового процесу на графі ${\displaystyle {\tilde {G}}_{n}}$, який починається з n вершин без ребер і на кожному кроці додається нове ребро, що вибирається рівномірно з множини відсутніх ребер.

Якщо ж починати з нескінченної множини вершин і вибирати кожне можливе ребро незалежно з імовірністю 0 < p < 1, вийде об'єкт G, званий нескінченним випадковим графом. За винятком тривіальних випадків, коли p дорівнює 0 або 1, такий G майже напевно має такі властивості:

Якщо задано будь-які n + m елементів ${\displaystyle a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V}$, існує вершина c у V, яка суміжна з кожною вершиною ${\displaystyle a_{1},\ldots ,a_{n}}$ і не пов'язана з жодною з ${\displaystyle b_{1},\ldots ,b_{m}}$.

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

Інша модель, що узагальнює гільбертову модель випадкового графу, — це модель випадкового скалярного добутку. Граф випадкового скалярного добутку пов'язує з кожною вершиною дійсний вектор. Ймовірність ребра uv між будь-якими вершинами u і v є деякою функцією скалярного добутку u • v відповідних їм векторів.

Матриці ймовірності мережі^[en] моделюють випадкові графи через імовірності ребер ${\displaystyle p_{i,j}}$ таким чином, що дане ребро ${\displaystyle e_{i,j}}$ існує в зазначений період часу. Цю модель можна поширити на орієнтовані та неорієнтовані графи, зважені і незважені, на статичні й динамічні.

Для M ≃ pN, де N — найбільше можливе число ребер, найчастіше використовуються моделі G(n,M) і G(n,p), які майже завжди взаємозамінні^[4].

Випадковий регулярний граф^[en] утворює особливий випадок, що має властивості, які в загальному випадку можуть відрізнятися від випадкових графів.

Якщо ми маємо модель випадкових графів, будь-яка функція на графах стає випадковою величиною. Завдання вивчення цієї моделі — визначити, або, принаймні, оцінити ймовірність появи властивості^[3].

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

Термін «майже напевно» в контексті випадкових графів стосується послідовності просторів і ймовірностей, таких що ймовірність помилки прямує до нуля^[3].

Властивості випадкових графів

Теорія випадкових графів вивчає типові властивості випадкових графів, які виконуються з великою ймовірністю для графів, отриманих для певного розподілу. Наприклад, ми можемо запитати для заданих значень n і p, яка ймовірність, що G(n,p) зв'язний. Під час вивчення таких питань дослідники часто концентруються на асимптотичній поведінці випадкових графів — значеннях, до яких прямують різні ймовірності за зростання n. Теорія перколяції описує зв'язність випадкових графів, особливо необмежено великих.

Перколяція пов'язана зі стійкістю графу (званого також мережею). Нехай дано випадковий граф з n вершинами і середнім степенем ${\displaystyle \langle k\rangle }$. Видалимо випадкову 1−p частину ребер і залишимо p частину. Існує критичний поріг перколяції ${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$, нижче від якого мережа стає фрагментованою, тоді як вище p_c існують величезні компоненти зв'язності^{[1][5][4][6] [7][8]}.

Випадкові графи широко використовуються в імовірнісному методі, коли намагаються довести існування графів з певними властивостями. Існування властивості на випадкових графах може часто мати наслідком, за лемою регулярності Семереді, існування цієї властивості майже для всіх графів.

Для випадкових регулярних графів G(n,r-reg) — це множина r-регулярних графів з r = r(n), таких що n та m — натуральні числа, 3 ≤ r < n, і rn = 2m парне^[2].

Послідовність степенів графу G в Gⁿ залежить тільки від числа ребер у множинах^[2]

${\displaystyle 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 містить досконале парування. Зокрема, в момент, коли зникає остання ізольована вершина, майже у всіх випадкових графах, граф стає зв'язним^[2].

Майже будь-який процес побудови графу з парним числом вершин за досягнення найменшого степеня 1 або випадкового графу за досягнення трохи більше, ніж (n/4)log(n) ребер з близькою до 1 імовірністю забезпечує існування повного парування, за винятком, можливо, однієї вершини.

Для деякої константи c майже кожен позначений граф з n вершинами і як мінімум cnlog(n) ребрами є гамільтоновим. З імовірністю, яка прямує до 1, додавання ребра, що збільшує мінімальний степінь графу до 2, робить його гамільтоновим.

Розфарбовування випадкових графів

Якщо задано випадковий граф G порядку n з вершинами V(G) = {1, …, n}, розфарбування можна отримати за допомогою жадібного алгоритму (вершина 1 фарбується кольором 1, вершина 2 отримує колір 1 якщо вона не суміжна 1, в іншому отримує колір 2, і так далі)^[2].

Випадкові дерева

Випадковим деревом^[en] називається дерево або орієнтоване дерево^[en], утворене випадковим процесом. У великому діапазоні випадкових графів порядку n і розміру M(n) розподіл кількості дерев порядку k асимптотично підпорядкований закону Пуассона. Типи випадкових дерев включають уніформні кістякові дерева, випадкові мінімальні кістякові дерева^[en], випадкові двійкові дерева^[en], декартові дерева, швидко досліджувані випадкові дерева^[en], броунівські дерева і випадкові ліси.

Історія

Випадкові графи вперше визначили Ердеш і Реньї в книзі 1959 року «On Random Graphs»^[8] і незалежно Гільберт у статті «Random graphs»^[5].

Див. також

• Граф Радо
• Складні мережі
• Перколяція

Примітки

1. Béla Bollobás^[en]. Random Graphs. — Cambridge University Press, 2001.
2. Béla Bollobás. Random Graphs. — London : Academic Press Inc, 1985.
3. Béla Bollobás. Probabilistic Combinatorics and Its Applications. — Providence : American Mathematical Society, 1991.
4. Mathematical results on scale-free random graphs. Handbook of Graphs and Networks. — Weinheim : Wiley VCH, 2003.
5. E. N. Gilbert. Random graphs. — Annals of Mathematical Statistics. — 1959. — Т. 30. — С. 1141—1144. — DOI:10.1214/aoms/1177706098.
6. M. E. J. Newman. Networks: An Introduction. — Oxford, 2010.
7. Reuven Cohen, Shlomo Havlin. Complex Networks: Structure, Robustness and Function. — Cambridge University Press, 2010.
8. P. Erdős, A Rényi. On Random Graphs I. — Publ. Math. — 1959. — Т. 6. — С. 290—297.

Література

• А.М. Райгородский. Модели случайных графов. — М. : МЦНМО, 2011. — 136 с. — ISBN 978-5-94057-840-6.