Erdős–Rényi modell

A Wikipédiából, a szabad enciklopédiából

Az ErdősRényi modell a gráfelméletben két rokon, véletlen gráfok előállítására szolgáló modell neve. Az egyik változata egyenlő valószínűséggel választ az összes adott élszámú gráf közül, a másiknál minden él egymástól függetlenül egy adott valószínűséggel van behúzva.

Definíció[szerkesztés | forrásszöveg szerkesztése]

Az Erdős–Rényi modellnek két, szorosan összefüggő változata van.

Erdős–Rényi binomiális modellel, p=0.01 paraméterrel generált gráf.
  • A G(n, M) modellben egyenletes eloszlás szerint választunk egyet az összes n csúcsú, M élű gráf közül. Például a G(3,2) modellben a három, két vonal behúzásával kapható gráf mindegyikét 1/3 valószínűséggel választjuk.
  • A G(n, p) modellben a gráfot az élek véletlen behúzásával kapjuk: minden élt, egymástól függetlenül, p valószínűséggel húzunk be. Más megközelítésben, először a p^M (1-p)^{{n \choose 2}-M} eloszlás szerint választunk egy M-et, majd generálunk egy G(n, M) gráfot. A p egyfajta súlyfüggvényként fogható fel: nagyobb p értékekre nagyobb valószínűséggel kapunk sok élt tartalmazó gráfot. Speciálisan p = 0,5-re egyforma valószínűséggel választjuk mind a 2^\tbinom{n}{2} lehetséges gráfot.

A p és M paramétereket gyakran n függvényeként adják meg, és azt vizsgálják, mit lehet mondani valamilyen tulajdonság előfordulásának valószínűségéről, ha n tart a végtelenbe. Például a „majdnem minden G(n, \tfrac{2 \ln n}{n}) gráf összefüggő” állítás azt jelenti, hogy annak valószínűsége, hogy egy G(n, \tfrac{2 \ln n}{n}) gráf összefüggő, tart az 1-hez, ha n tart a végtelenhez.

A két modell összehasonlítása[szerkesztés | forrásszöveg szerkesztése]

Ha T egy monoton tulajdonság (azaz ha egy részgráfra teljesül, akkor a teljes gráfra is), akkor T akkor és csak akkor teljesül majdnem minden G(n,p) gráfra, ha majdnem minden  G(n, \tbinom{n}{2} p) gráfra teljesül (ahol np^2 tart a végtelenhez).

(Az összefüggés azon alapszik, hogy egy G(n,p) gráf éleinek várható száma \tbinom{n}{2}p, és a nagy számok törvénye szerint minden G(n,p)-gráfnak majdnem biztosan körülbelül ennyi éle lesz, ha n tart végtelenhez. így ha pn^2 tart a végtelenhez, akkor G(n,p) és  G(n, \tbinom{n}{2} p) között nincs olyan nagy különbség.)

A gyakorlatban inkább a G(n, p) modellt használják, többek között azért, mert az élek függetlensége gyakran megkönnyíti az elemzést.

G(n, p) tulajdonságai[szerkesztés | forrásszöveg szerkesztése]

G(n, p)-nek átlagosan \tbinom{n}{2} p éle van. Az egyes csúcsok fokszámeloszlása binomiális:

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

Erdős és Rényi p és n arányával nagyon pontosan jellemezni tudta egy G(n,p) gráf összefüggőségét.[1] Többek között bebizonyították, hogy

  • ha np < 1 , akkor egy G(n,p) gráfnak majdnem biztosan nem lesz O(\log n)-nél nagyobb összefüggő komponense.
  • Ha np=1 , akkor egy G(n,p) gráf legnagyobb összafüggő komponense majdnem biztosan konstansszor n^{2/3} nagyságrendű lesz.
  • Ha np egy 1-nél nagyobb konstanshoz tart, akkor egy G(n,p) gráfnak majdnem biztosan lesz egy „óriás” összefüggő komponense, ami konstansszor n nagyságrendű lesz, és az összes többi komponens legfeljebb O(\log n) csúcsot tartalmaz.

Továbbá:

  • Ha p<\tfrac{(1-\varepsilon)\ln n}{n}, akkor egy G(n, p) gráf majdnem biztosan nem összefüggő.
  • Ha p>\tfrac{(1+\varepsilon) \ln n}{n}, akkor egy G(n, p) gráf majdnem biztosan összefüggő.

Más szóval az  \tfrac{\ln n}{n} éles küszöb G(n, p) összefüggőségére. Ezt a jelenséget, amikor egy gráfra egy adott tulajdonság egy bizonyos küszöb alatt majdnem biztosan nem teljesül, a küszöb fölött pedig majdnem biztosan teljesül, fázisátmenetnek nevezik.

Más tulajdonságok is nagy pontossággal leírhatók végtelenhez tartó 'n mellett. Például van olyan k(n) függvény (ami körülbelül megegyezik 2 \log_2 n-nel), hogy a legnagyobb G(n, 0,5)-beli klikk mérete majdnem biztosan vagy k(n) vagy k(n) + 1.[2]

A majdnem biztosan összefüggő G(n, p) gráfok majdnem biztosan kis-világ tulajdonságúak is.[forrás?]

A modell korlátai[szerkesztés | forrásszöveg szerkesztése]

A G(n, p) modell két fő feltevése (hogy az élek függetlenek, és minden él megléte egyformán valószínű) a gyakorlatban ritkán teljesül. Az érdekes hálózatok nagy része például skálafüggetlen, egy Erdős–Rényi gráf viszont nem az. Emelett az Erdős–Rényi gráfok klaszterezettsége 1/n körül van, a vizsgált hálózatoké pedig gyakran konstans.

Történet[szerkesztés | forrásszöveg szerkesztése]

A G(n, p) modellt először Edgar Gilbert vezette be egy 1959-es cikkében, amiben gráfok összefüggőségének a feltételeit vizsgálta.[3] A G(n, M) modellt Erdős Pál és Rényi Alfréd vezette be, szintén 1959-ben, és szintén az összefüggőséget vizsgálva;[4]

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Erdős, P., Rényi, A. (1960.). „On The Evolution of Random Graphs”. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5, 17-61. o.  
  2. Bollobás, B., Erdős, P. (1976.). „Cliques in Random Graphs”. Math. Proc. Cambridge Phil. Soc. 80 (3), 419-427. o.  
  3. Gilbert, E.N. (1959.). „Random Graphs”. Annals of Mathematical Statistics 30, 1141-1144. o.  
  4. Erdős, P., Rényi, A. (1959.). „On Random Graphs. I.”. Publicationes Mathematicae 6, 290-297. o.  
  • Bollobás, B.. Random Graphs, 2nd, Cambridge University Press (2001). ISBN 0521797225 
  • West, Douglas B.. Introduction to Graph Theory, 2nd, Prentice Hall (2001). ISBN 0-13-014400-2