Erdős-Renyi model

Erdős-Rényi-modellen er en af to nært beslægtede modeller til generering af tilfældige grafer . Modellerne er opkaldt efter matematikerne Pal Erdős og Alfred Rényi , som først introducerede en af modellerne i 1959 [1] [2] , mens Edgar Hilbert foreslog en anden model samtidigt og uafhængigt af Erdős og Rényi [3] . I Erdős og Rényis model er alle grafer med et fast sæt hjørner og et fast sæt kanter lige sandsynlige. I Hilberts model har hver kant en fast tilstedeværelse eller fraværssandsynlighed uafhængig af andre kanter. Disse modeller kan bruges i en probabilistisk metode til at bevise eksistensen af grafer, der opfylder forskellige egenskaber, eller til at give en præcis definition af, om en egenskab forstås at holde for næsten alle grafer.

Definition

Der er to nært beslægtede versioner af Erdős-Rényi-modellen af en tilfældig graf.

I modellen vælges en graf ensartet og tilfældigt fra sættet af alle grafer, der har n toppunkter og M kanter. Eksempelvis i modellen vælges hver af de tre mulige grafer med tre spidser og to kanter med en sandsynlighed på 1/3. $G(n,M)$ $G(3,2)$
I modellen bygges en graf ved at tilføje kanter tilfældigt. Hver kant er inkluderet i grafen med sandsynlighed p , uanset de andre kanter. Tilsvarende har alle grafer med n noder og M kanter samme sandsynlighed. $G(n,p)$

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

Parameteren p i denne model kan betragtes som en funktion af vægten. Når p vokser fra 0 til 1, er det mere sandsynligt, at modellen inkluderer grafer med flere kanter. Især tilfældet p = 0,5 svarer til tilfældet, hvor alle grafer med n toppunkter vil blive valgt med lige stor sandsynlighed.

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

Tilfældige grafers adfærd studeres ofte, når n , antallet af hjørner i grafen, har en tendens til uendelig. Selvom p og M kan være faste i dette tilfælde, kan de også afhænge af en funktion af n . For eksempel redegørelsen

Næsten alle grafer er forbundet

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

midler

Da n har en tendens til det uendelige, er sandsynligheden for, at en graf med n toppunkter og en kantinklusionssandsynlighed 2ln( n )/ n forbundet, en tendens til 1.

Sammenligning af de to modeller

Den matematiske forventning om antallet af kanter i er lig med , og ifølge loven om store tal vil enhver graf i B næsten helt sikkert have omtrent dette antal kanter. Derfor, groft sagt, hvis , så skulle G ( n , p ) opføre sig som G ( n , M ) s når n vokser . $G(n,p)$ ${\tbinom {n}{2}}p$ $G(n,p)$ $pn^{2}\to \infty$ $M={\tbinom {n}{2}}p$

Dette er tilfældet for mange grafegenskaber. Hvis P er en egenskab ved en graf, der er monoton i forhold til undergrafrækkefølgen (hvilket betyder, at hvis A er en undergraf af B , og A opfylder P , så vil B også opfylde P ), så gælder udsagn " P for næsten alle grafer i " og " P gælder for næsten alle grafer i " er ækvivalente (for ). For eksempel gælder dette, hvis P har egenskaben at være forbundet, eller hvis P har egenskaben at have en Hamiltonsk cyklus . Dette gælder dog ikke nødvendigvis for ikke-monotone egenskaber (f.eks. egenskaben til at have et lige antal kanter). $G(n,p)$ $G(n,{\tbinom {n}{2}}p)$ $pn^{2}\to \infty$

I praksis er modellen en af de mest brugte i dag, blandt andet på grund af den nemme analyse, som edge-uafhængighed giver. $G(n,p)$

Grafegenskaber $G(n,p)$

Med ovenstående notation har grafen i gennemsnit kanter. Toppunktsgradfordelingen er binomial [4] : $G(n,p)$ ${\tbinom {n}{2}}p$

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

hvor n er det samlede antal hjørner i grafen. Fordi

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

kl og

n\til\infty

np={\text{konstant)),

denne fordeling er Poisson-fordelingen for stor n og np = konstant.

I et papir fra 1960 beskrev Erdős og Rényi [5] adfærden meget nøjagtigt for forskellige p -værdier . Deres resultater omfatter: $G(n,p)$

Hvis np < 1, så vil grafen i næsten helt sikkert ikke have forbundne komponenter af størrelse større end O(log( n )). $G(n,p)$
Hvis np =1, så vil grafen i næsten helt sikkert have store komponenter, hvis størrelse er af størrelsesordenen n 2/3 . $G(n,p)$
Hvis , hvor c er en konstant, så vil grafen i næsten helt sikkert have en enkelt gigantisk komponent, der indeholder en positiv andel af hjørner. Ingen anden komponent vil have mere end O(log( n )) toppunkter. $np\to c>1$ $G(n,p)$
Hvis , så vil grafen i næsten helt sikkert indeholde isolerede hjørner og derfor være afbrudt. $p<{\tfrac {(1-\varepsilon )\ln n}{n))$ $G(n,p)$
Hvis , så vil grafen i næsten helt sikkert være forbundet. $p>{\tfrac {(1+\varepsilon )\ln n}{n))$ $G(n,p)$

Således er den nøjagtige tærskelsandsynlighed for tilslutning . ${\tfrac {\ln n}{n))$ $G(n,p)$

Yderligere egenskaber ved grafen kan beskrives næsten nøjagtigt, da n har en tendens til uendelig. For eksempel er der k ( n ) (ca. lig med 2log 2 ( n )), sådan at den største klike i næsten helt sikkert enten er af størrelsen k ( n ) eller [6] . $G(n,0,5)$ $k(n)+1$

Så selvom problemet med at finde størrelsen af den største klike i en graf er NP-komplet , er størrelsen af den største klike i en "typisk" graf (ifølge denne model) godt forstået.

Kant-duale grafer af Erdős-Rényi grafer er grafer med næsten samme gradfordelinger, men med gradkorrelation og en meget højere klyngekoefficient [7] .

Relation til perkolation

I perkolationsteori undersøges en endelig eller uendelig graf, og kanter (eller forbindelser) fjernes tilfældigt. Så er Erdős-Rényi-processen i virkeligheden en uvægtet perkolation på hele grafen . Da teorien om perkolation har dybe rødder i fysikken , er der lavet en stor mængde forskning på gitter i euklidiske rum. Overgangen ved np =1 fra den gigantiske komponent til den lille komponent har analoger til disse grafer, men for gitter er overgangspunktet vanskeligt at bestemme. Fysikere taler ofte om at studere hele grafen som en selvkonsistent feltmetode . Så er Erdős-Rényi-processen tilfældet med et gennemsnitligt perkolationsfelt.

En del betydeligt arbejde er også blevet udført med perkolering på tilfældige grafer. Fra et fysisk synspunkt forbliver modellen en middelfeltmodel, hvorfor motivationen for forskning ofte formuleres i form af stabiliteten af en graf, der ses som et kommunikationsnetværk. Lad en tilfældig graf med noder med gennemsnitlig grad < k > blive givet. Vi fjerner andelen af noder og forlader netværkets share p′ . Der er en kritisk perkolationstærskel , under hvilken netværket bliver fragmenteret, mens der over tærsklen er en kæmpe forbundet komponent af orden n . Den relative størrelse af den gigantiske komponent er givet ved formlen [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 })].\,

Advarsler

Hovedantagelserne for begge modeller (at kanterne er uafhængige, og at hver kant er lige sandsynlig) er muligvis ikke egnede til at modellere nogle virkelige fænomener. Især fordelingen af grader af hjørner af Erdős-Rényi grafer har ikke tunge haler af fordelingen, mens fordelingen anses for at have en tung hale i mange rigtige netværk . Desuden har Erdős-Rényi grafer lav clustering, hvilket ikke er tilfældet i mange sociale netværk. For populære modelalternativer, se artiklerne The Barabasi-Albert Model og The Watts and Strogats Model . Disse alternative modeller er ikke perkolationsprocesser , men er i stedet henholdsvis vækst- og omledningsmodeller. Erdős-Rényi netværksinteraktionsmodellen blev for nylig udviklet af Buldyrev et al . [9] . $G(n,p)$

Historie

Modellen blev først foreslået af Edgar Hilbert i et papir fra 1959, der studerede forbindelsestærsklen nævnt ovenfor [3] . Modellen blev foreslået af Erdős og Renyi i deres papir fra 1959. Som i Hilberts tilfælde undersøgte de forbindelsen , og en mere detaljeret analyse blev udført i 1960. $G(n,p)$ $G(n,M)$ $G(n,M)$

Variationer og generaliseringer

En grafon (grafteori) er en mere generel model af en tilfældig graf.

Rado-grafen , dannet ved at udvide modellen til grafer med et tælleligt antal hjørner. I modsætning til det sidste tilfælde er resultatet af denne uendelige proces (med sandsynlighed 1 ) den samme graf op til isomorfi. $G(n,p)$

Barabashi-Albert model .

Noter

↑ 1 2 Erdős, Rényi, 1959 , s. 290-297.
↑ 12 Bollobás , 2001 .
↑ 1 2 Gilbert, 1959 , s. 1141-1144.
↑ Newman, Strogatz, Watts, 2001 , s. 026118.
↑ 1 2 ( Erdős, Rényi 1960 , 17–61) Den her anvendte sandsynlighed p refererer til $N(n)={\tbinom {n}{2}}p$
↑ Matula, 1972 , s. A-382.
↑ Ramezanpour, Karimipour, Mashaghi, 2003 , s. 046107.
↑ Bollobás, Erdős, 1976 , s. 419-427.
↑ Buldyrev, Parshani, Paul, Stanley, Havlin, 2010 , s. 1025-8.

Litteratur

Mark EJ Newman, Strogatz SH, Watts DJ Tilfældige grafer med vilkårlige gradfordelinger og deres anvendelser // Physical Review E. - 2001. - T. 64 . - doi : 10.1103/PhysRevE.64.026118 . - . - arXiv : cond-mat/0007235 . , lign. (en)
Erdős P., Rényi A. Om udviklingen af tilfældige grafer // Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publikationer fra Det Matematiske Institut for Det Ungarske Videnskabsakademi]. - 1960. - T. 5 .
David W. Matula. Medarbejderpartiproblemet // Notices of the American Mathematical Society. - 1972. - Februar ( bind 19 ). - S. A-382 .
Ramezanpour A., Karimipour V., Mashaghi A. Generering af korrelerede netværk fra ikke-korrelerede // Physical Review E. - 2003. - April ( vol. 67 , udgave 4 ). - doi : 10.1103/PhysRevE.67.046107 . - . - arXiv : cond-mat/0212469 .
Erdős P., Renyi A. On Random Graphs. I // Publikationer Mathematicae. - 1959. - T. 6 .
Bollobas B. Tilfældige grafer. — 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 , no. 3 . - doi : 10.1017/S0305004100053056 . - .
Buldyrev SV, Parshani R., Paul G., Stanley HE, Havlin S. Katastrofal kaskade af fejl i indbyrdes afhængige netværk // Nature. - 2010. - T. 464 , no. 7291 . - doi : 10.1038/nature08932 . - . - arXiv : 0907.1182 . — PMID 20393559 .
Gilbert EN Random Graphs // Annals of Mathematical Statistics. - 1959. - T. 30 , no. 4 . - doi : 10.1214/aoms/1177706098 .

Læsning for yderligere læsning

Raigorodsky, Andrey Mikhailovich Tilfældige grafmodeller . - M. : MTSNMO, 2011. - ISBN 978-5-94057-840-6 .
Douglas B. West. Introduktion til grafteori. - 2001. - ISBN 0-13-014400-2 .
Newman MEJ Networks: En introduktion. – 2010.
Komplekse netværk: struktur, robusthed og funktion . – 2010.