Erdős–Rényi-modell

Az Erdős–Ré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ó

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{)}^{(\genfrac{}{}{0ex}{}{n}{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^{(\genfrac{}{}{0ex}{}{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,\frac{2\ln n}{n})$ gráf összefüggő” állítás azt jelenti, hogy annak valószínűsége, hogy egy $G(n,\frac{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

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,(\genfrac{}{}{0ex}{}{n}{2})p)$ gráfra teljesül (ahol $n{p}^2$ tart a végtelenhez).

(Az összefüggés azon alapszik, hogy egy G(n,p) gráf éleinek várható száma $(\genfrac{}{}{0ex}{}{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 $p{n}^2$ tart a végtelenhez, akkor G(n,p) és $G(n,(\genfrac{}{}{0ex}{}{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

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

$P(\mathrm{deg}(v)=k)=(\genfrac{}{}{0ex}{}{n}{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. 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 összefü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<\frac{(1-\epsilon )\ln n}{n}$, akkor egy G(n, p) gráf majdnem biztosan nem összefüggő.
• Ha $p>\frac{(1+\epsilon )\ln n}{n}$, akkor egy G(n, p) gráf majdnem biztosan összefüggő.

Más szóval az $\frac{\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.

A majdnem biztosan összefüggő G(n, p) gráfok majdnem biztosan kis-világ tulajdonságúak is.Sablon:Forr

A modell korlátai

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énete

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. 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;

Lásd még

• Watts–Strogatz-modell
• Barabási–Albert-modell

Források

• Sablon:Cite book
• Sablon:Cite book