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

Innen: TételWiki

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ó, a szomszédok közti lehetséges élek hányad része létezik)

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
  • Alternatív Klaszterezettség definíció I: C_I=\frac{<k>}{N-1}, ahol <k> az átlagos fokszám, N pedig az összes csúcs száma
  • Alternatív Klaszterezettség definíció II: C_{II}=\frac{\Delta}{\Lambda}, ahol \Delta a redszerben előforduló 3 teljesen összekötött csúcs számossága, \Lambda pedig 3 pont 2 éllel összekötött részek számossága (ahogy a szimbólumok alakja is utal ezekre)
  • 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.3788 és p=0.758-ra

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ő)
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 (a csúcsok legnagyobb részét tartalmazó algráf, más szóval klaszter) gyorsan kialakul, p \sim \frac{1}{N} + \epsilon, ahol p az összekötési valószínűség, N a csúcsok száma és \epsilon egy kicsi szám. 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)

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

Cluster distr.png

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
WS.png
  • 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

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...
Ravasz Barabasi.png

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: d_i - a csúcs fokszáma. ("Népszerűség")
  • Közelség-centralitás: \sum(l_{ij}) - a többi csúcshoz vezető min. utak összege
  • Köztesség-centralitás: \sum\frac{\mathbf{p}_{jik}}{\mathbf{p}_{jk}} - 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.
ER (E) és BA (Sf) gráfok támadása
  • 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

MSc záróvizsga tételek 2012
Tételek Soktest rendszerek '12 | Transzportfolyamatok '12 | Véletlen gráfok generálása, tulajdonságai '12 | Elsőrendű és folytonos fázisátalakulások '12 | Válasz- és korrelációs függvények, fluktuáció-disszipáció tétel '12 | Sztochasztikus folyamatok '12 | A statisztikus fizikai szimulációk alapjai és a Monte Carlo módszer '12 | Dinamikai rendszerek, kaotikus viselkedés '12 | Adatelemzés: lineáris és nem lineáris regresszió egy modellen bemutatva '12 | Adatelemzés: bootstrap modellek '12 | TCP hálózat működése '12 | Adatelemzés: ARCH, GARCH folyamatok '12 | Numerikus módszerek '12 | Vizualizációs módszerek '12