Erdős-Renyiho model

Erdős-Rényiho model je jedním ze dvou úzce souvisejících modelů generování náhodných grafů . Modely jsou pojmenovány po matematicích Pal Erdős a Alfred Rényi , kteří poprvé představili jeden z modelů v roce 1959 [1] [2] , zatímco Edgar Hilbert navrhl jiný model současně a nezávisle na Erdősovi a Rényi [3] . V Erdősově a Rényiho modelu jsou všechny grafy s pevnou sadou vrcholů a pevnou sadou hran stejně pravděpodobné. V Hilbertově modelu má každá hrana pevnou pravděpodobnost přítomnosti nebo nepřítomnosti nezávislou na ostatních hranách. Tyto modely lze použít v pravděpodobnostní metodě k prokázání existence grafů splňujících různé vlastnosti nebo k poskytnutí přesné definice toho, zda je vlastnost chápána jako platná pro téměř všechny grafy.

Definice

Existují dvě úzce související verze Erdős-Rényiho modelu náhodného grafu.

V modelu je graf vybrán rovnoměrně a náhodně z množiny všech grafů, které mají n vrcholů a M hran. Například v modelu je každý ze tří možných grafů se třemi vrcholy a dvěma hranami vybrán s pravděpodobností 1/3. $G(n,M)$ $G(3,2)$
V modelu je graf sestaven náhodným přidáváním hran. Každá hrana je zahrnuta do grafu s pravděpodobností p , bez ohledu na ostatní hrany. Stejně tak všechny grafy s n uzly a M hranami mají stejnou pravděpodobnost. $G(n,p)$

p^{M}(1-p)^{{n \vyberte 2}-M}.

Parametr p v tomto modelu lze považovat za funkci hmotnosti. Jak p roste z 0 na 1, je pravděpodobnější, že model bude obsahovat grafy s více hranami. Zejména případ p = 0,5 odpovídá případu, kdy budou se stejnou pravděpodobností vybrány všechny grafy s n vrcholy.

2^{\binom {n}{2))

Chování náhodných grafů je často studováno, když n , počet vrcholů v grafu, má tendenci k nekonečnu. Ačkoli p a M mohou být v tomto případě fixní, mohou také záviset na funkci n . Například prohlášení

Téměř všechny grafy jsou propojené

G(n,2ln(n)/n)

prostředek

Protože n směřuje k nekonečnu, pravděpodobnost, že je spojen graf s n vrcholy a pravděpodobností zahrnutí hran 2ln( n )/ n , má tendenci k 1.

Porovnání obou modelů

Matematické očekávání počtu hran v se rovná , a podle zákona velkých čísel bude mít každý graf v B téměř jistě přibližně tento počet hran. Zhruba řečeno, jestliže , pak by se G ( n , p ) mělo chovat jako G ( n , M ) s , když n roste . $G(n,p)$ ${\tbinom {n}{2}}p$ $G(n,p)$ $pn^{2}\to \infty$ $M={\tbinom {n}{2}}p$

To je případ mnoha vlastností grafu. Je-li P jakákoliv vlastnost grafu, která je monotónní vzhledem k uspořádání podgrafů (to znamená, že pokud A je podgrafem B a A splňuje P , pak B splňuje i P ), pak tvrzení „ P platí pro téměř všechny grafy v " a " P platí pro téměř všechny grafy v " jsou ekvivalentní (pro ). Například to platí, pokud P má vlastnost být spojen, nebo pokud má P vlastnost mít hamiltonovský cyklus . To však nemusí nutně platit pro nemonotónní vlastnosti (například vlastnost mít sudý počet hran). $G(n,p)$ $G(n,{\tbinom {n}{2}}p)$ $pn^{2}\to \infty$

V praxi je model dnes jedním z nejpoužívanějších, částečně kvůli snadné analýze, kterou poskytuje nezávislost na hranách. $G(n,p)$

Vlastnosti grafu $G(n,p)$

S výše uvedeným zápisem má graf v průměru hrany. Rozdělení stupňů vrcholů je binomické [4] : $G(n,p)$ ${\tbinom {n}{2}}p$

P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},

kde n je celkový počet vrcholů v grafu. Protože

P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!)}}

v a

n\to\infty

np={\text{constant)),

toto rozdělení je Poissonovo rozdělení pro velká n a np = konstanta.

V článku z roku 1960 Erdős a Rényi [5] popsali chování velmi přesně pro různé hodnoty p . Mezi jejich výsledky patří: $G(n,p)$

Pokud np < 1, pak graf téměř jistě nebude mít spojené složky o velikosti větší než O(log( n )). $G(n,p)$
Je-li np =1, pak graf v bude mít téměř jistě velké složky, jejichž velikost je řádově n 2/3 . $G(n,p)$
Jestliže , kde c je konstanta, pak graf bude mít téměř jistě jednu obří složku obsahující kladný podíl vrcholů. Žádná jiná složka nebude mít více než O(log( n )) vrcholů. $np\to c>1$ $G(n,p)$
Jestliže , pak graf v bude téměř jistě obsahovat izolované vrcholy, a proto bude odpojen. $p<{\tfrac {(1-\varepsilon )\ln n}{n))$ $G(n,p)$
Pokud , pak graf v bude téměř jistě propojený. $p>{\tfrac {(1+\varepsilon )\ln n}{n))$ $G(n,p)$

Je tedy přesná prahová pravděpodobnost pro konektivitu . ${\tfrac {\ln n}{n))$ $G(n,p)$

Další vlastnosti grafu lze popsat téměř přesně, protože n má tendenci k nekonečnu. Například existuje k ( n ) (přibližně se rovná 2log 2 ( n )), takže největší klika v má téměř jistě buď velikost k ( n ) nebo [6] . $G(n,0,5)$ $k(n)+1$

Pak, ačkoliv problém nalezení velikosti největší kliky v grafu je NP-úplný , velikost největší kliky v "typickém" grafu (podle tohoto modelu) je dobře pochopena.

Hranové-duální grafy Erdős-Rényiho grafů jsou grafy s téměř stejným rozdělením stupňů, ale se stupněm korelace a mnohem vyšším shlukovacím koeficientem [7] .

Vztah k perkolaci

V perkolační teorii se zkoumá konečný nebo nekonečný graf a hrany (nebo odkazy) jsou náhodně odstraněny. Potom je Erdős-Rényiho proces ve skutečnosti neváženou perkolací na kompletním grafu . Protože teorie perkolace má hluboké kořeny ve fyzice , velké množství výzkumu bylo děláno na mřížích v euklidovských prostorech. Přechod na np =1 z obří složky do malé složky má pro tyto grafy analoga, ale pro mříže je obtížné určit bod přechodu. Fyzici často mluví o studiu kompletního grafu jako o samokonzistentní metodě pole . Pak je Erdős-Rényiho proces případem průměrného perkolačního pole.

Některé významné práce byly také provedeny na perkolaci na náhodných grafech. Z fyzikálního hlediska model zůstává modelem středního pole, takže motivace pro výzkum je často formulována ve smyslu stability grafu nahlíženého jako komunikační síť. Nechť je dán náhodný graf s uzly s průměrným stupněm < k >. Odebereme podíl uzlů a ponecháme podíl p′ sítě. Existuje kritický perkolační práh , pod kterým se síť fragmentuje, zatímco nad prahem je obří propojená složka řádu n . Relativní velikost obří složky je dána vzorcem [5] [1] [2] [8] . $n\gg 1$ $1-p'$ $p'_{c}={\tfrac {1}{\langle k\rangle ))$ ${\displaystyle p'_{c))$ ${\displaystyle P_{\infty ))$

P_{\infty }=p'[1-\exp(-\langle k\rangle P_{\infty })].\,

Varování

Hlavní předpoklady obou modelů (že hrany jsou nezávislé a že každá hrana je stejně pravděpodobná) nemusí být vhodné pro modelování některých reálných jevů. Zejména distribuce stupňů vrcholů Erdős-Rényiho grafů nemá těžké konce distribuce, zatímco distribuce je v mnoha skutečných sítích považována za těžká . Erdős-Rényiho grafy mají navíc nízké shlukování, což není případ mnoha sociálních sítí. Oblíbené alternativy modelů naleznete v článcích The Barabasi-Albert Model a The Watts and Strogats Model . Tyto alternativní modely nejsou procesy perkolace , ale jsou to modely růstu a přepojování. Erdős-Rényiho síťový interakční model nedávno vyvinul Buldyrev et al [9] . $G(n,p)$

Historie

Model poprvé navrhl Edgar Hilbert v článku z roku 1959, který studoval výše zmíněný práh konektivity [3] . Model navrhli Erdős a Renyi ve svém článku z roku 1959. Stejně jako v případě Hilberta zkoumali konektivitu a v roce 1960 byla provedena podrobnější analýza. $G(n,p)$ $G(n,M)$ $G(n,M)$

Variace a zobecnění

Grafon (teorie grafů) je obecnější model náhodného grafu.

Rado graf , vytvořený rozšířením modelu na grafy s počitatelným počtem vrcholů. Na rozdíl od konečného případu je výsledkem tohoto nekonečného procesu (s pravděpodobností 1 ) stejný graf až do izomorfismu. $G(n,p)$

Model Barabashi-Albert .

Poznámky

↑ 1 2 Erdős, Rényi, 1959 , s. 290–297.
↑ 12 Bollobás , 2001 .
↑ 1 2 Gilbert, 1959 , str. 1141–1144.
↑ Newman, Strogatz, Watts, 2001 , str. 026118.
↑ 1 2 ( Erdős, Rényi 1960 , 17–61) Zde použitá pravděpodobnost p se vztahuje k $N(n)={\tbinom {n}{2}}p$
↑ Matula, 1972 , str. A-382.
↑ Ramezanpour, Karimipour, Mashaghi, 2003 , str. 046107.
↑ Bollobás, Erdős, 1976 , str. 419–427.
↑ Buldyrev, Parshani, Paul, Stanley, Havlin, 2010 , str. 1025–8.

Literatura

Mark EJ Newman, Strogatz SH, Watts DJ Náhodné grafy s libovolným rozdělením stupňů a jejich aplikace // Physical Review E. - 2001. - T. 64 . - doi : 10.1103/PhysRevE.64.026118 . - . - arXiv : cond-mat/0007235 . , Eq. (jeden)
Erdős P., Rényi A. O evoluci náhodných grafů // Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publikace Matematického ústavu Maďarské akademie věd]. - 1960. - T. 5 .
David W. Matula. Problém zaměstnaneckých stran // Notices of the American Mathematical Society. - 1972. - únor ( 19. díl ). - S. A-382 .
Ramezanpour A., Karimipour V., Mashaghi A. Generování korelovaných sítí z nekorelovaných // Physical Review E. - 2003. - Duben ( vol. 67 , issue 4 ). - doi : 10.1103/PhysRevE.67.046107 . - . - arXiv : cond-mat/0212469 .
Erdős P., Renyi A. O náhodných grafech. I // Publikace Mathematicae. - 1959. - T. 6 .
Bollobas B. Náhodné grafy. — 2. - 2001. - ISBN 0-521-79722-5 .
Bollobás B., Erdős P. Cliques in Random Graphs // Mathematical Proceedings of the Cambridge Philosophical Society. - 1976. - T. 80 , čís. 3 . - doi : 10.1017/S0305004100053056 . - .
Buldyrev SV, Parshani R., Paul G., Stanley HE, Havlin S. Katastrofická kaskáda selhání ve vzájemně závislých sítích // Příroda. - 2010. - T. 464 , č.p. 7291 . - doi : 10.1038/nature08932 . - . - arXiv : 0907.1182 . — PMID 20393559 .
Gilbert EN Náhodné grafy // Annals of Mathematical Statistics. - 1959. - T. 30 , čís. 4 . - doi : 10.1214/aoms/1177706098 .

Čtení pro další čtení

Raigorodskij, Andrej Michajlovič Náhodné modely grafů . - M. : MTSNMO, 2011. - ISBN 978-5-94057-840-6 .
Douglas B. West. Úvod do teorie grafů. - 2001. - ISBN 0-13-014400-2 .
Newman MEJ Networks: Úvod. — 2010.
Komplexní sítě: struktura, robustnost a funkce . — 2010.