Náhodný graf - Random graph

V matematice je náhodný graf obecný termín pro rozdělení pravděpodobnosti na grafy . Náhodné grafy lze popsat jednoduše rozdělením pravděpodobnosti nebo náhodným procesem, který je generuje. Teorie náhodných grafů leží na průsečíku mezi teorií grafů a teorií pravděpodobnosti . Z matematického hlediska se k zodpovězení otázek o vlastnostech typických grafů používají náhodné grafy. Jeho praktické aplikace se nacházejí ve všech oblastech, ve kterých je třeba modelovat složité sítě - je tedy známo mnoho modelů náhodných grafů, které odrážejí různé typy komplexních sítí vyskytujících se v různých oblastech. V matematickém kontextu se náhodný graf vztahuje téměř výhradně na model náhodných grafů Erdős – Rényi . V jiných kontextech může být jakýkoli grafický model označován jako náhodný graf .

Modely

Náhodný graf získáme tak, že začneme sadou n izolovaných vrcholů a náhodným přidáním po sobě jdoucích hran mezi ně. Cílem studie v této oblasti je určit, v jaké fázi je pravděpodobné, že konkrétní vlastnost grafu vznikne. Různé modely náhodných grafů vytvářejí na grafech různá rozdělení pravděpodobnosti . Nejčastěji se studuje ten, který navrhl Edgar Gilbert , označený G ( n , p ), ve kterém se každá možná hrana vyskytuje nezávisle s pravděpodobností 0 < p <1. Pravděpodobnost získání jakéhokoli konkrétního náhodného grafu s m hranami je s notací . ${\ Displaystyle p^{m} (1-p)^{Nm}}$ ${\ displaystyle N = {\ tbinom {n} {2}}}$

Úzce související model, model Erdős – Rényi označovaný G ( n , M ), přiřazuje stejnou pravděpodobnost všem grafům s přesně M hranami. S 0 ≤ M ≤ N má G ( n , M ) prvky a každý prvek se vyskytuje s pravděpodobností . Druhý model lze považovat za snímek v určitém čase ( M ) procesu náhodného grafu , což je stochastický proces, který začíná n vrcholy a žádnými hranami a v každém kroku přidává jednu novou hranu zvolenou jednotně ze sady chybějící hrany. ${\ displaystyle {\ tbinom {N} {M}}}$ ${\ displaystyle 1/{\ tbinom {N} {M}}}$ ${\ displaystyle {\ tilde {G}} _ {n}}$

Pokud místo toho začneme s nekonečnou sadou vrcholů a opět necháme každou možnou hranu, aby se vyskytovala nezávisle s pravděpodobností 0 < p <1, pak dostaneme objekt G nazývaný nekonečný náhodný graf . S výjimkou triviálních případů, kdy p je 0 nebo 1, má takové G téměř jistě následující vlastnost:

Vzhledem k jakýmkoli n + m prvkům existuje vrchol c ve V, který sousedí s každým a nesousedí s žádným z nich . ${\ Displaystyle a_ {1}, \ ldots, a_ {n}, b_ {1}, \ ldots, b_ {m} \ v V}$ ${\ displaystyle a_ {1}, \ ldots, a_ {n}}$ ${\ displaystyle b_ {1}, \ ldots, b_ {m}}$

Ukazuje se, že pokud je množina vrcholů počitatelná, pak existuje až do izomorfismu pouze jeden graf s touto vlastností, a to Rado graf . Jakýkoli spočitatelně nekonečný náhodný graf je tedy téměř jistě Rado graf, který se z tohoto důvodu někdy nazývá jednoduše náhodný graf . Analogický výsledek však neplatí pro nespočetné grafy, kterých je mnoho (neizomorfních) grafů splňujících výše uvedenou vlastnost.

Dalším modelem, který generalizuje Gilbertův model náhodných grafů, je model náhodných bodů . Náhodný graf bodového produktu spojuje s každým vrcholem skutečný vektor . Pravděpodobnost uv uv mezi libovolnými vrcholy u a v je nějakou funkcí součinu bodů u • v jejich příslušných vektorů.

Tyto sítě pravděpodobnost matrice modely náhodné grafy prostřednictvím okrajových pravděpodobností, které představují pravděpodobnost , že daný okraj existuje po určitou dobu. Tento model je rozšiřitelný na směrovaný i neorientovaný; vážený a nevážený; a strukturou statických nebo dynamických grafů. ${\ displaystyle p_ {i, j}}$ ${\ displaystyle e_ {i, j}}$

Pro M ≃ pN , kde N je maximální počet možných hran, jsou dva nejpoužívanější modely G ( n , M ) a G ( n , p ) téměř zaměnitelné.

Náhodné pravidelné grafy tvoří zvláštní případ s vlastnostmi, které se mohou obecně lišit od náhodných grafů.

Jakmile máme model náhodných grafů, každá funkce na grafech se stane náhodnou proměnnou . Studie tohoto modelu má určit, zda, nebo alespoň odhadnout pravděpodobnost, že vlastnost může nastat.

Terminologie

Termín „téměř každý“ v kontextu náhodných grafů odkazuje na posloupnost mezer a pravděpodobností, takže pravděpodobnosti chyb bývají nulové.

Vlastnosti

Teorie náhodných grafů studuje typické vlastnosti náhodných grafů, které s vysokou pravděpodobností platí pro grafy čerpané z určité distribuce. Můžeme se například zeptat na danou hodnotu a jaká je pravděpodobnost, že je spojena . Při studiu takových otázek se vědci často soustředí na asymptotické chování náhodných grafů - hodnoty, ke kterým se různé pravděpodobnosti sbíhají, jak velmi rostou. Teorie perkolace charakterizuje propojenost náhodných grafů, zejména nekonečně velkých. ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ Displaystyle G (n, p)}$ ${\ displaystyle n}$

Perkolace souvisí s robustností grafu (nazývaného také síť). Daný náhodný graf uzlů a průměrný stupeň . Dále náhodně odstraníme zlomek uzlů a ponecháme pouze zlomek . Existuje kritický prah perkolace, pod kterým se síť fragmentuje, zatímco nad obří připojenou komponentou existuje. ${\ displaystyle n}$ ${\ displaystyle \ langle k \ rangle}$ ${\ Displaystyle 1-p}$ ${\ displaystyle p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$

Lokalizovaná perkolace znamená odstranění uzlu jeho sousedů, dalších nejbližších sousedů atd., Dokud nebude odstraněn zlomek uzlů ze sítě. Ukázalo se, že pro náhodný graf s Poissonovou distribucí stupňů přesně jako pro náhodné odstranění. U jiných typů rozdělení stupňů pro lokalizovaný útok se liší od náhodného útoku (prahové funkce, vývoj ) ${\ Displaystyle 1-p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$ ${\ displaystyle {\ tilde {G}}}$

Náhodné grafy jsou široce používány v pravděpodobnostní metodě , kde se člověk snaží dokázat existenci grafů s určitými vlastnostmi. Existence vlastnosti na náhodném grafu může často znamenat prostřednictvím lemmatu pravidelnosti Szemerédi existenci této vlastnosti téměř na všech grafech.

V náhodných pravidelných grafů , je množina -regular grafů s taková, že a jsou přirozená čísla, a je dokonce. ${\ Displaystyle G (n, r-reg)}$ ${\ displaystyle r}$ ${\ Displaystyle r = r (n)}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ Displaystyle 3 \ leq r <n}$ ${\ displaystyle rn = 2m}$

Stupeň sekvence graf in závisí pouze na počtu hran v sadách ${\ displaystyle G}$ ${\ displaystyle G^{n}}$

{\ Displaystyle V_ {n}^{(2)} = \ left \ {ij \: \ 1 \ leq j \ leq n, i \ neq j \ right \} \ podmnožina V^{(2)}, \ qquad i = 1, \ cdots, n.}

Pokud jsou hrany v náhodném grafu dostatečně velké, aby zajistily, že téměř každý má minimální stupeň alespoň 1, pak je téměř každý propojen a pokud je sudý, téměř každý má perfektní shodu. Zejména v okamžiku, kdy téměř každý náhodný graf zmizí poslední izolovaný vrchol, graf se propojí. ${\ displaystyle M}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle n}$ ${\ displaystyle G_ {M}}$

Téměř každý graf zpracovává na sudém počtu vrcholů s okrajem zvyšujícím minimální stupeň na 1 nebo náhodným grafem s mírně více než hranami as pravděpodobností blízkou 1 zajišťuje, že graf má úplnou shodu, s výjimkou nejvýše jednoho vrcholu . ${\ displaystyle {\ tfrac {n} {4}} \ log (n)}$

Pro nějakou konstantu je téměř každý označený graf s vrcholy a alespoň hranami hamiltonovský . S pravděpodobností tendující k 1, konkrétní hrana, která zvyšuje minimální stupeň na 2, dělá graf hamiltonovský. ${\ displaystyle c}$ ${\ displaystyle n}$ ${\ displaystyle cn \ log (n)}$

Vlastnosti náhodného grafu se mohou při transformaci grafu změnit nebo zůstat neměnné. Mashaghi A. et al. Například prokázali, že transformace, která převádí náhodné grafy na jejich hranové duální grafy (nebo čárové grafy), vytváří soubor grafů s téměř stejným rozložením stupňů, ale s korelací stupňů a výrazně vyšším shlukováním součinitel.

Zbarvení

Vzhledem k náhodnému grafu G řádu n s vrcholem V ( G ) = {1, ..., n }, podle chamtivého algoritmu o počtu barev lze vrcholy obarvit barvami 1, 2, ... (vrchol 1 je barevný 1, vrchol 2 je barevný 1, pokud není sousedící s vrcholem 1, jinak je barevný 2 atd.). Počet vlastních zbarvení náhodných grafů daný počtem barev q , nazývaných jeho chromatický polynom , zůstává dosud neznámý. Škálování nul chromatického polynomu náhodných grafů s parametry n a počtem hran m nebo pravděpodobností připojení p bylo studováno empiricky pomocí algoritmu založeného na symbolické shodě vzorů.

Náhodné stromy

Náhodný strom je strom nebo stromová struktura , která je tvořena stochastických procesů . Ve velkém rozsahu náhodných grafů řádu n a velikosti M ( n ) je distribuce počtu složek stromu řádu k asymptoticky Poissonova . Mezi druhy náhodných stromů patří jednotný spanning strom , náhodný minimální spanning strom , random binární strom , treap , rychle zkoumající náhodný strom , Brownův strom a náhodný les .

Podmíněné náhodné grafy

Zvažte daný model náhodného grafu definovaný na pravděpodobnostním prostoru a nechte být funkcí s reálnou hodnotou, která přiřadí každému grafu ve vektoru m vlastností. Pro pevné , podmíněné náhodné grafy jsou modely, ve kterých míra pravděpodobnosti přiřazuje všem grafům nulovou pravděpodobnost, že ' . ${\ displaystyle (\ Omega, {\ mathcal {F}}, P)}$ ${\ displaystyle {\ mathcal {P}} (G): \ Omega \ rightarrow R^{m}}$ ${\ displaystyle \ Omega}$ ${\ Displaystyle \ mathbf {p} \ v R^{m}}$ ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G) \ neq \ mathbf {p}}$

Zvláštními případy jsou podmíněně jednotné náhodné grafy , kde všem grafům se zadanými vlastnostmi přiřadí stejnou pravděpodobnost. Mohou být vnímány jako zobecnění Erdős – Rényiho modelu G ( n , M ), kdy podmínkou informace není nutně počet hran M , ale jakákoli jiná vlastnost libovolného grafu . V tomto případě je k dispozici velmi málo analytických výsledků a pro získání empirických rozdělení průměrných vlastností je nutná simulace. ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G)}$

Vzájemně závislé grafy

V vzájemně závislých grafech fungují uzly v jedné síti (graf) na jiných sítích. Neúspěchy v jednom nebo několika grafech způsobují kaskádové chyby mezi grafy, které mohou vést k náhlému kolapsu.

Dějiny

Nejčasnější použití modelu náhodného grafu bylo Helen Hall Jenningsovou a Jacobem Morenem v roce 1938, kde byl při studiu porovnávání zlomku vzájemných odkazů v jejich síťových datech s náhodným modelem zvažován „sociogram náhody“ (směrovaný model Erdős-Rényi). . Další použití pod názvem „náhodná síť“ provedli Solomonoff a Rapoport v roce 1951 za použití modelu směrovaných grafů s pevným přesahem a náhodně zvolenými přílohami k jiným vrcholům.

Erdős-Rényi modelu náhodných grafů byl poprvé definován Paulem Erdős a Alfréd Rényi v jejich 1959 papíru „On náhodný graf“ a nezávisle Gilbert ve své knize „náhodný graf“.

Languages

In other projects