Modelul Erdős-Renyi

Modelul Erdős-Rényi este unul dintre cele două modele aleatoare de generare de grafice strâns legate . Modelele poartă numele matematicienilor Pal Erdős și Alfred Rényi , care au introdus pentru prima dată unul dintre modele în 1959 [1] [2] , în timp ce Edgar Hilbert a propus un alt model simultan și independent de Erdős și Rényi [3] . În modelul lui Erdős și Rényi, toate graficele cu un set fix de vârfuri și un set fix de muchii sunt la fel de probabile. În modelul lui Hilbert, fiecare muchie are o probabilitate fixă de prezență sau absență independentă de celelalte muchii. Aceste modele pot fi utilizate într-o metodă probabilistică pentru a demonstra existența graficelor care satisfac diverse proprietăți sau pentru a oferi o definiție precisă a faptului dacă o proprietate este înțeleasă că este valabilă pentru aproape toate graficele.

Definiție

Există două versiuni strâns legate ale modelului Erdős-Rényi al unui grafic aleatoriu.

În modelul , un grafic este ales uniform și aleatoriu din mulțimea tuturor graficelor care au n vârfuri și M muchii. De exemplu, în model, fiecare dintre cele trei grafice posibile cu trei vârfuri și două muchii este selectat cu o probabilitate de 1/3. $G(n,M)$ $G(3,2)$
În model, un grafic este construit prin adăugarea aleatorie de muchii. Fiecare muchie este inclusă în grafic cu probabilitatea p , indiferent de celelalte muchii. În mod echivalent, toate graficele cu n noduri și M muchii au aceeași probabilitate. $G(n,p)$

p^{M}(1-p)^{{n \alegeți 2}-M}.

Parametrul p în acest model poate fi considerat în funcție de greutate. Pe măsură ce p crește de la 0 la 1, este mai probabil ca modelul să includă grafice cu mai multe muchii. În special, cazul p = 0,5 corespunde cazului în care toate graficele cu n vârfuri vor fi alese cu probabilitate egală.

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

Comportamentul graficelor aleatoare este adesea studiat atunci când n , numărul de vârfuri din grafic, tinde spre infinit. Deși p și M pot fi fixate în acest caz, ele pot depinde și de o funcție a lui n . De exemplu, afirmația

Aproape toate graficele sunt conectate

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

mijloace

Deoarece n tinde spre infinit, probabilitatea ca un grafic cu n vârfuri și o probabilitate de includere a muchiei 2ln( n )/ n să fie conectat tinde spre 1.

Comparația celor două modele

Așteptările matematice ale numărului de muchii din este egală cu , iar prin legea numerelor mari, orice grafic din B va avea aproape sigur acest număr de muchii. Prin urmare, aproximativ vorbind, dacă , atunci G ( n , p ) ar trebui să se comporte ca G ( n , M ) s pe măsură ce n crește . $G(n,p)$ ${\tbinom {n}{2}}p$ $G(n,p)$ $pn^{2}\to \infty$ $M={\tbinom {n}{2}}p$

Acesta este cazul multor proprietăți grafice. Dacă P este orice proprietate a unui graf care este monotonă în ceea ce privește ordonarea subgrafului (adică dacă A este un subgraf al lui B și A satisface P , atunci B va satisface și P ), atunci afirmațiile " P sunt valabile pentru aproape toate graficele în " și " P este valabil pentru aproape toate graficele din " sunt echivalente (pentru ). De exemplu, acest lucru este valabil dacă P are proprietatea de a fi conectat sau dacă P are proprietatea de a avea un ciclu hamiltonian . Cu toate acestea, acest lucru nu va fi neapărat valabil pentru proprietățile nemonotone (de exemplu, proprietatea de a avea un număr par de margini). $G(n,p)$ $G(n,{\tbinom {n}{2}}p)$ $pn^{2}\to \infty$

În practică, modelul este unul dintre cele mai utilizate astăzi, parțial din cauza ușurinței de analiză oferită de independența marginilor. $G(n,p)$

Proprietăți grafice $G(n,p)$

Cu notația de mai sus, graficul în are, în medie, muchii. Distribuția gradelor de vârf este binomială [4] : $G(n,p)$ ${\tbinom {n}{2}}p$

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

unde n este numărul total de vârfuri din grafic. Pentru că

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

la şi

n\la\infty

np={\text{constant}),

această distribuție este distribuția Poisson pentru n mare și np = constant.

Într-o lucrare din 1960, Erdős și Rényi [5] au descris comportamentul foarte precis pentru diferite valori p . Rezultatele lor includ: $G(n,p)$

Dacă np < 1, atunci graficul în aproape sigur nu va avea componente conectate de dimensiune mai mare decât O(log( n )). $G(n,p)$
Dacă np =1, atunci graficul în va avea aproape sigur componente mari, a căror dimensiune este de ordinul lui n 2/3 . $G(n,p)$
Dacă , unde c este o constantă, atunci graficul din va avea aproape sigur o singură componentă gigantică care conține o proporție pozitivă de vârfuri. Nicio altă componentă nu va avea mai mult de O(log( n )) vârfuri. $np\to c>1$ $G(n,p)$
Dacă , atunci graficul din va conține aproape sigur vârfuri izolate și, prin urmare, va fi deconectat. $p<{\tfrac {(1-\varepsilon )\ln n}{n)}$ $G(n,p)$
Dacă , atunci graficul în va fi aproape sigur conectat. $p>{\tfrac {(1+\varepsilon )\ln n}{n)}$ $G(n,p)$

Astfel, este probabilitatea pragului exact pentru conectivitate . ${\tfrac {\ln n}{n})$ $G(n,p)$

Alte proprietăți ale graficului pot fi descrise aproape exact deoarece n tinde spre infinit. De exemplu, există k ( n ) (aproximativ egal cu 2log 2 ( n )), astfel încât cea mai mare clică din este aproape sigur de dimensiunea k ( n ) sau [6] . $G(n,0,5)$ $k(n)+1$

Apoi, deși problema găsirii mărimii celei mai mari clicuri într-un grafic este NP-complet , dimensiunea celei mai mari clicuri într-un grafic „tipic” (conform acestui model) este bine înțeleasă.

Graficele muchii-duale ale graficelor Erdős-Rényi sunt grafice cu aproape aceleași distribuții de grade, dar cu corelație de grade și un coeficient de clustering mult mai mare [7] .

Relația cu percolarea

În teoria percolației , un grafic finit sau infinit este examinat și marginile (sau conexiunile) sunt îndepărtate aleatoriu. Apoi, procesul Erdős-Rényi este, de fapt, o percolare neponderată pe graficul complet . Deoarece teoria percolării are rădăcini adânci în fizică , s-au făcut o mare cantitate de cercetări asupra rețelelor din spațiile euclidiene. Tranziția la np =1 de la componenta gigantică la componenta mică are analogi pentru aceste grafice, dar pentru rețele punctul de tranziție este dificil de determinat. Fizicienii vorbesc adesea despre studierea graficului complet ca pe o metodă de câmp autonomă . Apoi procesul Erdős-Rényi este cazul unui câmp de percolare mediu.

S-au făcut, de asemenea, unele lucrări semnificative privind percolarea pe grafice aleatorii. Din punct de vedere fizic, modelul rămâne un model de câmp mediu, astfel încât motivația pentru cercetare este adesea formulată în termeni de stabilitate a unui grafic privit ca o rețea de comunicații. Să fie dat un grafic aleatoriu cu noduri cu grad mediu < k >. Înlăturăm cota de noduri și lăsăm cota p′ a rețelei. Există un prag critic de percolare , sub care rețeaua devine fragmentată, în timp ce deasupra pragului există o componentă gigantică conectată de ordinul n . Mărimea relativă a componentei gigant este dată de formula [5] [1] [2] [8] . $n\gg 1$ $1-p'$ $p'_{c}={\tfrac {1}{\langle k\rangle ))$ $p'_{c)$ $P_{\infty )$

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

Avertismente

Principalele ipoteze ale ambelor modele (că muchiile sunt independente și că fiecare muchie este la fel de probabilă) ar putea să nu fie potrivite pentru modelarea unor fenomene din viața reală. În special, distribuția gradelor de vârfuri ale graficelor Erdős-Rényi nu are cozi grele ale distribuției, în timp ce distribuția este considerată a avea o coadă grea în multe rețele reale . Mai mult, graficele Erdős-Rényi au clustering scăzut, ceea ce nu este cazul în multe rețele sociale. Pentru alternative de model populare, consultați articolele The Barabasi-Albert Model și The Watts and Strogats Model . Aceste modele alternative nu sunt procese de percolare , ci sunt modele de creștere și, respectiv, de reconectare. Modelul de interacțiune a rețelei Erdős-Rényi a fost dezvoltat recent de Buldyrev și colab .[9] . $G(n,p)$

Istorie

Modelul a fost propus pentru prima dată de Edgar Hilbert într-o lucrare din 1959 care studia pragul de conectivitate menționat mai sus [3] . Modelul a fost propus de Erdős și Renyi în lucrarea lor din 1959. Ca și în cazul lui Hilbert, au investigat conectivitatea , iar o analiză mai detaliată a fost efectuată în 1960. $G(n,p)$ $G(n,M)$ $G(n,M)$

Variații și generalizări

Un graphon (teoria grafurilor) este un model mai general al unui graf aleator.

Graficul Rado , format prin extinderea modelului la grafice cu un număr numărabil de vârfuri. Spre deosebire de cazul final, rezultatul acestui proces infinit este (cu probabilitate 1 ) același grafic până la izomorfism. $G(n,p)$

Modelul Barabashi-Albert .

Note

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

Literatură

Mark EJ Newman, Strogatz SH, Watts DJ Grafice aleatorii cu distribuții de grade arbitrare și aplicațiile lor // Physical Review E. - 2001. - T. 64 . - doi : 10.1103/PhysRevE.64.026118 . - Cod . - arXiv : cond-mat/0007235 . , Equ. (unu)
Erdős P., Rényi A. Despre evoluția graficelor aleatorii // Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publicațiile Institutului de Matematică al Academiei Maghiare de Științe]. - 1960. - T. 5 .
David W. Matula. Problema partidului angajaților // Notices of the American Mathematical Society. - 1972. - Februarie ( vol. 19 ). - S. A-382 .
Ramezanpour A., Karimipour V., Mashaghi A. Generarea de rețele corelate din necorelate // Physical Review E. - 2003. - aprilie ( vol. 67 , numărul 4 ). - doi : 10.1103/PhysRevE.67.046107 . - Cod . - arXiv : cond-mat/0212469 .
Erdős P., Renyi A. On Random Graphs. I // Publications Mathematicae. - 1959. - T. 6 .
Bollobas B. Grafice aleatorii. — al 2-lea. - 2001. - ISBN 0-521-79722-5 .
Bollobás B., Erdős P. Cliques în grafice aleatorii // Mathematical Proceedings of the Cambridge Philosophical Society. - 1976. - T. 80 , nr. 3 . - doi : 10.1017/S0305004100053056 . - Cod .
Buldyrev SV, Parshani R., Paul G., Stanley HE, Havlin S. Catastrophic cascade of failures in interdependent networks // Nature. - 2010. - T. 464 , nr. 7291 . - doi : 10.1038/nature08932 . - . - arXiv : 0907.1182 . — PMID 20393559 .
Gilbert EN Random Graphs // Analele statisticii matematice. - 1959. - T. 30 , nr. 4 . - doi : 10.1214/aoms/1177706098 .

Lectură pentru lecturi suplimentare

Raigorodsky, Andrei Mihailovici Modele aleatorii grafice . - M. : MTSNMO, 2011. - ISBN 978-5-94057-840-6 .
Douglas B. West. Introducere în teoria grafurilor. - 2001. - ISBN 0-13-014400-2 .
Newman MEJ Networks: o introducere. — 2010.
Rețele complexe: structură, robustețe și funcție . — 2010.