Véletlen gráfok generálása, tulajdonságai '12
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.
Tartalomjegyzék
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. (ahol 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ó, a szomszédok közti lehetséges élek hányad része létezik)
, ahol az i-edik csúcs szomszédai közti élek száma. Átlagos klaszterezettség:
Szemléletes jelentés: Ha , akkor "csillag" - ha , akkor "klikk"
- Alternatív Klaszterezettség definíció I: , ahol <k> az átlagos fokszám, N pedig az összes csúcs száma
- Alternatív Klaszterezettség definíció II: , ahol a redszerben előforduló 3 teljesen összekötött csúcs számossága, pedig 3 pont 2 éllel összekötött részek számossága (ahogy a szimbólumok alakja is utal ezekre)
- Távolság: () 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 , 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:
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
Tulajdonságok
- Csúcsok növelésével exponenciálisan nő a kapcsolatszám
- A fokszámeloszlás Binomiális-eloszlás lesz (analitikusan is levezethető)
- Kisvilág tulajdonság, ha összefüggő. Szinte mindig összefüggő, mivel az óriáskomponens (a csúcsok legnagyobb részét tartalmazó algráf, más szóval klaszter) gyorsan kialakul, , ahol p az összekötési valószínűség, N a csúcsok száma és egy kicsi szám. Az egyes komponenseken belül is kisvilág tulajdonság
A klaszterek méreteloszlása hatványfüggvény szerint csökken:
Konfigurációs modell
- Feladat: adott fokszám-eloszlású véletlen gráf generálása.
- "Recept": húzzunk N-szer p(k)-ból (csúcsokat fél élekkel), majd kössük őket össze egymással.
- könnyen előfordulhatnak hurkok, ezért a nagy fokszámú csúcstól induljunk.
- Ez még nem tekinthető véletlennek, randomizálás szükséges: ennek egyik lehetséges módja az élek átkötése a fokszámok megőrzésével (Link Randomization).
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: , ahol az n-edik csúcs fokszáma
Ha E = 1, akkor - fa gráfot fogunk kapni:
Tulajdonságai
- A fokszámeloszlás hatványfüggvényt követ
- Kisvilág
- NEM klaszterezett
Egy modell a három tulajdonsággal
Ravasz és Barabási hierarchikus modelljének lépései:
- Öt csúcs - teljesen összekötve
- 4 másolat a teljes gráfról, melynek magjai összekötöttek, szélső csúcsai pedig az eredeti maggal összekötöttek
- első lépéstől ismétlés...
Ez a modell: kisvilág, klaszterezett és skálafüggetlen, DE! determinisztikus (nem véletlen).
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.
Fontos az adott csúcs/él centralitása ("központi szerepének" jellemzése) - ezeket lehet érdemes "támadni"
- Fok-centralitás: - a csúcs fokszáma. ("Népszerűség")
- Közelség-centralitás: - a többi csúcshoz vezető min. utak összege
- Köztesség-centralitás: - az áthaladó utak száma
Erdős-Rényi gráf:
- Gyakorlatilag mindegy, hogy irányított vagy véletlen támadást hajtunk végre, mert nincsenek kitüntetett csúcsok
Barabási-Albert gráf:
- A véletlen támadással szemben ellenállóbb (kicsi a valószínűsége, hogy fontos csúcs hibásodik meg), viszont az irányított támadásra sokkal érzékenyebb.
- A WS gráf véletlen támadással és célzottal szemben is ellenálló, bár célzott támadás esetén hamar elveszti a kisvilág tulajdonságát. (És ilyet építeni a k-szomszédság miatt a gyakorlatban nem érdemes.)
Források: Claudius Gros - Complex and Adaptive Dynamcial Systems; Gulyás László - Társadalmi hálózatok és modelljeik előadás diák