Véletlen gráfok generálása, tulajdonságai

Rengeteg mindent fel lehet írni gráf alakban: internetes honlapok, szociális hálók, metabolikus folyamatok, szerzőségi hálók, tápláléklánc, körfolyamatok a fizikában és a biológiában, linux kernel stb.

Alapfogalmak

• Egy gráf csúcsokból és élekből áll (lehet egy vagy több él két csúcs között, lehet a gráf irányított/irányítatlan, súlyozott/súlyozatlan).
• Gráf reprezentációja: mutatókkal, él-listákkal, vagy összekötöttségi mátrixokkal.
• Csúcs fokszáma: ahány él csatlakozik (fut be, vagy megy ki) a csúcshoz.
• Fokszám-eloszlás: egy gráf teljes fokszám-gyakoriság diagramja.

Kisvilág tulajdonság

Legyen a gráf összes csúcsának száma N. Két tetszőleges csúcs közötti legrövidebb út: legkevesebb csúcs érintésével. Legrövidebb utak átlagos hossza: l.

Kisvilág tulajdonság: $l \approx log(N)$

Erdős-Rényi gráf

• N csúcsból áll
• Minden két csúcs között p valószínűséggel él
• Csúcsok növelésével exponenciálisan nő a kapcsolatszám
• Kisvilág tulajdonság, ha összefüggő. Szinte mindig összefüggő, mivel az óriáskomponens gyorsan kialakul, $p \sim \frac{1}{N} + \epsilon$. Az egyes komponenseken belül is kisvilág tulajdonság.

Watts-Strogratz gráf

A "kisvilág" modell, tetszőleges D dimenzióban megvalósítható.

• N csúcs, kiinduláskor rendezett rács, szabályos k-szomszédság
• Két módszer: "átdrótozás" (rewiring), vagy "levágások" (shortcuts). Előbbinél a meglévő éleket helyezzük át, utóbbinál új éleket vezetünk be két csúcs között - mindkét esetben p valószínűséggel tesszük ezt minden csúcspárra
• Az átlagos legrövidebb út hamarabb csökken, mint a klaszterezettség, egyszerre kisvilág és klaszterezett