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.

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

• 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 ${\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 ${\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 ${\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 ${\displaystyle G(n,{\tfrac {2\ln n}{n}})}$ gráf összefüggő, tart az 1-hez, ha n tart a végtelenhez.

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 ${\displaystyle G(n,{\tbinom {n}{2}}p)}$ gráfra teljesül (ahol ${\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 ${\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 ${\displaystyle pn^{2}}$ tart a végtelenhez, akkor G(n,p) és ${\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)-nek átlagosan ${\displaystyle {\tbinom {n}{2}}p}$ éle van. Az egyes csúcsok fokszámeloszlása binomiális:

${\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 ${\displaystyle np<1}$, akkor egy G(n,p) gráfnak majdnem biztosan nem lesz ${\displaystyle O(\log n)}$-nél nagyobb összefüggő komponense.
• Ha ${\displaystyle np=1}$, akkor egy G(n,p) gráf legnagyobb összefüggő komponense majdnem biztosan konstansszor ${\displaystyle n^{2/3}}$ nagyságrendű lesz.
• Ha ${\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 ${\displaystyle O(\log n)}$ csúcsot tartalmaz.

Továbbá:

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

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

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]

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

• 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