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]

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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): {\displaystyle 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 gráf összefüggő, tart az 1-hez, ha n tart a végtelenhez.

A két modell összehasonlítása[szerkesztés]

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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle G(n, \tbinom{n}{2} p) } gráfra teljesül (ahol Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle np^2} tart a végtelenhez).

(Az összefüggés azon alapszik, hogy egy G(n,p) gráf éleinek várható száma Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle \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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle pn^2} tart a végtelenhez, akkor G(n,p) és Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): {\displaystyle 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]

G(n, p)-nek átlagosan Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): {\displaystyle {\tbinom {n}{2}}p} éle van. Az egyes csúcsok fokszámeloszlása binomiális:

Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle np < 1 } , akkor egy G(n,p) gráfnak majdnem biztosan nem lesz -nél nagyobb összefüggő komponense.
  • Ha Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle np=1 } , akkor egy G(n,p) gráf legnagyobb összefüggő komponense majdnem biztosan konstansszor Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle n^{2/3}} nagyságrendű lesz.
  • Ha Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle O(\log n)} csúcsot tartalmaz.

Továbbá:

  • Ha Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle p<\tfrac{(1-\varepsilon)\ln n}{n}} , akkor egy G(n, p) gráf majdnem biztosan nem összefüggő.
  • Ha Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle p>\tfrac{(1+\varepsilon) \ln n}{n}} , akkor egy G(n, p) gráf majdnem biztosan összefüggő.

Más szóval az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle \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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle 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]

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. Emellett 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]

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ások[szerkesztés]

  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