Erdős-Renyi modell

Erdős-Rényi-modellen är en av två närbesläktade modeller för generering av slumpmässiga grafer . Modellerna är uppkallade efter matematikerna Pal Erdős och Alfred Rényi , som först introducerade en av modellerna 1959 [1] [2] , medan Edgar Hilbert föreslog en annan modell samtidigt och oberoende av Erdős och Rényi [3] . I Erdős och Rényis modell är alla grafer med en fast uppsättning hörn och en fast uppsättning kanter lika sannolika. I Hilberts modell har varje kant en fast närvaro- eller frånvaronsannolikhet oberoende av andra kanter. Dessa modeller kan användas i en probabilistisk metod för att bevisa förekomsten av grafer som uppfyller olika egenskaper, eller för att ge en exakt definition av huruvida en egenskap anses hålla för nästan alla grafer.

Definition

Det finns två närbesläktade versioner av Erdős-Rényi-modellen av en slumpmässig graf.

I modellen väljs en graf enhetligt och slumpmässigt från uppsättningen av alla grafer som har n hörn och M kanter. Till exempel, i modellen väljs var och en av de tre möjliga graferna med tre hörn och två kanter med en sannolikhet på 1/3. $G(n,M)$ $G(3,2)$
I modellen byggs en graf genom att slumpmässigt lägga till kanter. Varje kant ingår i grafen med sannolikhet p , oavsett de andra kanterna. På motsvarande sätt har alla grafer med n noder och M kanter samma sannolikhet. $G(n,p)$

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

Parametern p i denna modell kan betraktas som en funktion av vikten. När p växer från 0 till 1 är det mer sannolikt att modellen inkluderar grafer med fler kanter. I synnerhet motsvarar fallet p = 0,5 fallet då alla grafer med n hörn kommer att väljas med lika stor sannolikhet.

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

Beteendet hos slumpmässiga grafer studeras ofta när n , antalet hörn i grafen, tenderar till oändlighet. Även om p och M kan vara fixerade i detta fall kan de också bero på en funktion av n . Till exempel uttalandet

Nästan alla grafer hänger ihop

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

betyder att

Eftersom n tenderar till oändlighet, tenderar sannolikheten att en graf med n hörn och en kantinkluderingssannolikhet 2ln( n )/ n är kopplad till 1.

Jämförelse av de två modellerna

Den matematiska förväntan på antalet kanter i är lika med , och enligt lagen om stora siffror kommer varje graf i B nästan säkert att ha ungefär detta antal kanter. Därför, grovt sett, om , då bör G ( n , p ) bete sig som G ( n , M ) s när n växer . $G(n,p)$ ${\tbinom {n}{2}}p$ $G(n,p)$ $pn^{2}\to \infty$ $M={\tbinom {n}{2}}p$

Detta är fallet för många grafegenskaper. Om P är någon egenskap hos en graf som är monoton med avseende på subgrafordningen (vilket betyder att om A är en subgraf till B och A uppfyller P , då kommer B också att uppfylla P ), då gäller påståendena " P för nästan alla grafer i " och " P gäller för nästan alla grafer i " är ekvivalenta (för ). Detta gäller till exempel om P har egenskapen att vara ansluten, eller om P har egenskapen att ha en Hamiltonsk cykel . Detta gäller dock inte nödvändigtvis för icke-monotona egenskaper (till exempel egenskapen att ha ett jämnt antal kanter). $G(n,p)$ $G(n,{\tbinom {n}{2}}p)$ $pn^{2}\to \infty$

I praktiken är modellen en av de mest använda idag, delvis på grund av den enkla analys som edge-oberoende ger. $G(n,p)$

Grafegenskaper $G(n,p)$

Med ovanstående notation har grafen i genomsnitt kanter. Spetsgradsfördelningen är binomisk [4] : $G(n,p)$ ${\tbinom {n}{2}}p$

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

där n är det totala antalet hörn i grafen. Eftersom det

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

vid och

n\till\infty

np={\text{konstant)),

denna fördelning är Poissonfördelningen för stora n och np = konstant.

I ett papper från 1960 beskrev Erdős och Rényi [5] beteendet mycket exakt för olika p -värden . Deras resultat inkluderar: $G(n,p)$

Om np < 1, så kommer grafen i nästan säkert inte att ha sammankopplade komponenter med storlek större än O(log( n )). $G(n,p)$
Om np =1, så kommer grafen i nästan säkert att ha stora komponenter, vars storlek är i storleksordningen n 2/3 . $G(n,p)$
Om , där c är en konstant, så kommer grafen i nästan säkert att ha en enda gigantisk komponent som innehåller en positiv andel av hörn. Ingen annan komponent kommer att ha fler än O(log( n )) hörn. $np\to c>1$ $G(n,p)$
Om , så kommer grafen i nästan säkert att innehålla isolerade hörn och därför kopplas bort. $p<{\tfrac {(1-\varepsilon )\ln n}{n))$ $G(n,p)$
Om , så kommer grafen i nästan säkert att vara kopplad. $p>{\tfrac {(1+\varepsilon )\ln n}{n))$ $G(n,p)$

Således är den exakta tröskelns sannolikhet för anslutning . ${\tfrac {\ln n}{n))$ $G(n,p)$

Ytterligare egenskaper hos grafen kan beskrivas nästan exakt som n tenderar till oändlighet. Till exempel finns det k ( n ) (ungefär lika med 2log 2 ( n )), så att den största klicken i nästan säkert är antingen storleken k ( n ) eller [6] . $G(n,0,5)$ $k(n)+1$

Sedan, även om problemet med att hitta storleken på den största klicken i en graf är NP-komplett , är storleken på den största klicken i en "typisk" graf (enligt denna modell) väl förstått.

Kant-dual-graferna i Erdős-Rényi-grafer är grafer med nästan samma gradfördelningar, men med gradkorrelation och en mycket högre klusteringskoefficient [7] .

Relation till perkolering

I perkolationsteorin undersöks en ändlig eller oändlig graf och kanter (eller anslutningar) tas slumpmässigt bort. Då är Erdős-Rényi-processen i själva verket en oviktad genomströmning av hela grafen . Eftersom teorin om perkolation har djupa rötter i fysiken , har en stor mängd forskning gjorts på galler i euklidiska utrymmen. Övergången vid np =1 från den gigantiska komponenten till den lilla komponenten har analoger för dessa grafer, men för gitter är övergångspunkten svår att fastställa. Fysiker talar ofta om att studera hela grafen som en självständig fältmetod . Då är Erdős-Rényi-processen fallet med ett genomsnittligt perkolationsfält.

En del betydande arbete har också utförts på genomströmning av slumpmässiga grafer. Ur fysisk synvinkel förblir modellen en medelfältsmodell, varför motivationen för forskning ofta formuleras i termer av stabiliteten hos en graf som ses som ett kommunikationsnätverk. Låt en slumpmässig graf med noder med medelgrad < k > ges. Vi tar bort andelen noder och lämnar andelen p′ för nätverket. Det finns en kritisk perkolationströskel , under vilken nätverket blir fragmenterat, medan det ovanför tröskeln finns en jättelik ansluten komponent av ordningen n . Den relativa storleken på jättekomponenten ges av formeln [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 })].\,

Varningar

De huvudsakliga antagandena för båda modellerna (att kanterna är oberoende och att varje kant är lika trolig) kanske inte är lämpliga för att modellera några verkliga fenomen. I synnerhet har fördelningen av grader av hörn av Erdős-Rényi grafer inte tunga svansar av distributionen, medan distributionen anses ha en tung svans i många verkliga nätverk . Dessutom har Erdős-Rényi-grafer låg klustring, vilket inte är fallet i många sociala nätverk. För populära modellalternativ, se artiklarna The Barabasi-Albert Model och The Watts and Strogats Model . Dessa alternativa modeller är inte perkolationsprocesser utan är istället tillväxt- respektive omkopplingsmodeller. Erdős-Rényi nätverksinteraktionsmodellen utvecklades nyligen av Buldyrev et al [9] . $G(n,p)$

Historik

Modellen föreslogs först av Edgar Hilbert i ett papper från 1959 som studerade anslutningströskeln som nämns ovan [3] . Modellen föreslogs av Erdős och Renyi i deras papper från 1959. Liksom i Hilberts fall undersökte de anslutningsmöjligheter och en mer detaljerad analys genomfördes 1960. $G(n,p)$ $G(n,M)$ $G(n,M)$

Variationer och generaliseringar

En grafon (grafteori) är en mer allmän modell av en slumpmässig graf.

Rado-grafen , bildad genom att utvidga modellen till grafer med ett räknebart antal hörn. Till skillnad från det sista fallet är resultatet av denna oändliga process (med sannolikhet 1 ) samma graf fram till isomorfism. $G(n,p)$

Barabashi-Albert modell .

Anteckningar

↑ 1 2 Erdős, Rényi, 1959 , sid. 290–297.
↑ 12 Bollobás , 2001 .
↑ 1 2 Gilbert, 1959 , sid. 1141–1144.
↑ Newman, Strogatz, Watts, 2001 , sid. 026118.
↑ 1 2 ( Erdős, Rényi 1960 , 17–61) Sannolikheten p som används här avser bl.a. $N(n)={\tbinom {n}{2}}p$
↑ Matula, 1972 , sid. A-382.
↑ Ramezanpour, Karimipour, Mashaghi, 2003 , sid. 046107.
↑ Bollobás, Erdős, 1976 , sid. 419–427.
↑ Buldyrev, Parshani, Paul, Stanley, Havlin, 2010 , sid. 1025–8.

Litteratur

Mark EJ Newman, Strogatz SH, Watts DJ Slumpmässiga grafer med godtyckliga gradfördelningar och deras tillämpningar // Physical Review E. - 2001. - T. 64 . - doi : 10.1103/PhysRevE.64.026118 . - . - arXiv : cond-mat/0007235 . , ekv. (ett)
Erdős P., Rényi A. Om utvecklingen av slumpmässiga grafer // Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Ungerian Academy of Sciences]. - 1960. - T. 5 .
David W. Matula. Medarbetarpartsproblemet // Notices of the American Mathematical Society. - 1972. - Februari ( vol. 19 ). - S. A-382 .
Ramezanpour A., Karimipour V., Mashaghi A. Generera korrelerade nätverk från okorrelerade // Physical Review E. - 2003. - April ( vol. 67 , nummer 4 ). - doi : 10.1103/PhysRevE.67.046107 . - . - arXiv : cond-mat/0212469 .
Erdős P., Renyi A. On Random Graphs. I // Publications Mathematicae. - 1959. - T. 6 .
Bollobas B. Random Graphs. — 2:a. - 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 , nr. 3 . - doi : 10.1017/S0305004100053056 . - .
Buldyrev SV, Parshani R., Paul G., Stanley HE, Havlin S. Katastrofal kaskad av misslyckanden i ömsesidigt beroende nätverk // Nature. - 2010. - T. 464 , nr. 7291 . - doi : 10.1038/nature08932 . - . - arXiv : 0907.1182 . — PMID 20393559 .
Gilbert EN Random Graphs // Annals of Mathematical Statistics. - 1959. - T. 30 , nr. 4 . - doi : 10.1214/aoms/1177706098 .

Läsning för vidare läsning

Raigorodsky, Andrey Mikhailovich Slumpmässiga grafmodeller . - M. : MTSNMO, 2011. - ISBN 978-5-94057-840-6 .
Douglas B. West. Introduktion till grafteori. - 2001. - ISBN 0-13-014400-2 .
Newman MEJ Networks: En introduktion. — 2010.
Komplexa nätverk: struktur, robusthet och funktion . — 2010.