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. A gráf lehet:
  • Egyszerű gráf (két pont között csak 1 él, nincs hurok egy csúcsra); Multi gráf (két pont között lehet több él, nincs hurok egy csúcsra); Pszeudo gráf (két pont között lehet több él és lehet egy csúcson hurok)
  • Irányított/Irányítatlan
  • Súlyozott/Súlyozatlan
  • Címkézett gráf: csúcs- és/vagy él-címkézett (élek/csúcsok egyéni azonosítóval rendelkeznek)
  • Biparit gráf: két fajta csúcs van és élek csak a különböző fajtájú csúcsok közt vannak (pl.: filmszínészek hálózata)
• Gráf reprezentációja: mutatókkal, él-listákkal, vagy összekötöttségi mátrixokkal.
• Csúcs fokszáma: a csúcs kapcsolatainak száma (irányított gráfnál lehet beszélni bejövő és kimenő fokszámról).
  • Fokszám-eloszlás: egy gráf teljes fokszám-gyakoriság diagramja. $p<k> = N_k / N$ (ahol $N_k$ a k fokszámú csúcsok száma, N pedig a csúcsok száma
• Csúcs klaszterezettségi együtthatója: (csoporterősségi együttható)

$c_i = \frac{2e_i}{k_i(k_i-1)}$, ahol $e_i$ az i-edik csúcs szomszédai közti élek száma. Átlagos klaszterezettség: $<c> = \frac{1}{N}\sum(c_i)$

Szemléletes jelentés: Ha $c_i = 0$, akkor "csillag" - ha $c_i = 1$, akkor "klikk"

csillag és klikk

• Távolság: ($l_{ij}$) az a minimális lépésszám i és j csúcsok között, ami alatt el lehet jutni i-ből j-be az éleket követve. (irányítatlan gráfon $l_{ij} = l_{ji}$, irányított gráfon ez nem feltétlen teljesül.)

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

N=12 random gráfok: p=0.758 és p=0.3788-ra

Tulajdonságok

• Csúcsok növelésével exponenciálisan nő a kapcsolatszám
• A fokszámeloszlás Poisson-eloszlás lesz (analitikusan is levezethető)

N=1000 random gráf fokszámeloszlása (p kicsi)

• 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

Óriás komponens mérete [%] p ill. az átlagos fokszám függvényében (utóbbi esetben p=1/N, több futásra átlagolva)

• Klaszterezettsége: $C=\frac{z}{N-1}$, ahol z az átlagos fokszám, N pedig az összes csúcs száma

A klaszterek méreteloszlása hatványfüggvény szerint csökken:

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

Barabási-Albert gráf

Preferenciális csatolás (preferential attachment) modell.

• M db kezdőcsúcs tetszőlegesen összekötve
• Minden lépésben egy új csúcs, E db éllel
• Véletlenszerű, hogy melyik csúcshoz csatlakoznak az új élek, de a meglévő csúcsok fokszáma alapján preferencia: $p(n) = \frac{d(n)}{\sum_{i=1}^N d(i)}$, ahol $d(n)$ az n-edik csúcs fokszáma

Ha E = 1, akkor $c_i = 0$ - fa gráfot fogunk kapni:

baloldal: N0=2, E=1; jobb oldal: N0=3; E=2

Tulajdonságai

• A fokszámeloszlás hatványfüggvényt követ
• Kisvilág
• NEM klaszterezett

Robosztusság

Más néven ellenállóság véletlen hibákkal, vagy támadásokkal szemben.

Miért fontos? Robosztus számítógép-hálózatok, fajok védelme, járvány-védelem, információ-terjedés elleni "védelem" stb.