Véletlen gráfok generálása, tulajdonságai '12 - Laptörténet

CzGabe, 2012. június 17., 13:05-n

2012-06-17T13:05:18Z

Tama13s, 2012. június 12., 10:20-n

2012-06-12T10:20:30Z

Tama13s, 2012. június 8., 12:25-n

2012-06-08T12:25:44Z

Tama13s, 2012. június 8., 12:24-n

2012-06-08T12:24:54Z

CzGabe: Új oldal, tartalma: „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 f…”

2012-06-05T21:34:17Z

Új oldal, tartalma: „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 f…”

Új lap

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. <math>p<k> = N_k / N</math> (ahol <math>N_k</math> 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ó)
<math>c_i = \frac{2e_i}{k_i(k_i-1)}</math>, ahol <math>e_i</math> az i-edik csúcs szomszédai közti élek száma. Átlagos klaszterezettség: <math><c> = \frac{1}{N}\sum(c_i)</math>

Szemléletes jelentés: Ha <math>c_i = 0</math>, akkor "csillag" - ha <math>c_i = 1</math>, akkor "klikk"
[[Kép:csillag-klikk.jpg|center|thumb|csillag és klikk]]
*Alternatív Klaszterezettség definíció I: <math>C_I=\frac{<k>}{N-1}</math>, ahol <k> az átlagos fokszám, N pedig az összes csúcs száma
*Alternatív Klaszterezettség definíció II: <math>C_{II}=\frac{\Delta}{\Lambda}</math>, ahol <math>\Delta</math> a redszerben előforduló 3 teljesen összekötött csúcs számossága, <math>\Lambda</math> pedig 3 pont 2 éllel összekötött részek számossága (ahogy a szimbólumok alakja is utal ezekre)
* Távolság: (<math>l_{ij}</math>) 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 <math>l_{ij} = l_{ji}</math>, 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: <math>l \approx log(N)</math>

==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
[[Kép:RandomGraph.png|center|350px|thumb|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 Poisson-eloszlás lesz (analitikusan is levezethető)
[[Kép:RandomGraph_DD.png|center|250px|thumb|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, <math>p \sim \frac{1}{N} + \epsilon</math>, ahol p az összekötési valószínűség, N a csúcsok száma és <math>\epsilon</math> egy kicsi szám. Az egyes komponenseken belül is kisvilág tulajdonság
[[Kép:GiantComponent.png|center|500px|thumb|Ó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:
[[Kép:Cluster_distr.png|center|500px|thumb|]]

==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
[[Kép:WS.png|center|300px|thumb|]]
*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: <math>p(n) = \frac{d(n)}{\sum_{i=1}^N d(i)}</math>, ahol <math>d(n)</math> az n-edik csúcs fokszáma
Ha E = 1, akkor <math>c_i = 0</math> - fa gráfot fogunk kapni:
[[Kép:BA.png|center|300px|thumb|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éső csúcsai pedig az eredeti maggal összekötöttek
* első lépéstől ismétlés...
[[Kép:Ravasz_Barabasi.png|center|200px|thumb|]]
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: <math>d_i</math> - a csúcs fokszáma. ("Népszerűség")
* Közelség-centralitás: <math>\sum(l_{ij})</math> - a többi csúcshoz vezető min. utak összege
* Köztesség-centralitás: <math>\sum\frac{\mathbf{p}_{jik}}{\mathbf{p}_{jk}}</math> - 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.
[[Kép:Robost.png|center|300px|thumb|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 2012 záróvizsga}}

@@ 43. sor: / 43. sor: @@
 A klaszterek méreteloszlása hatványfüggvény szerint csökken:
 [[Kép:Cluster_distr.png|center|500px|thumb|]]
 ==Watts-Strogratz gráf==

@@ 36. sor: / 36. sor: @@
 *Csúcsok növelésével exponenciálisan nő a kapcsolatszám
-*A fokszámeloszlás Poisson-eloszlás lesz (analitikusan is levezethető)
+*A fokszámeloszlás Binomiális-eloszlás lesz (analitikusan is levezethető)
 [[Kép:RandomGraph_DD.png|center|250px|thumb|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, <math>p \sim \frac{1}{N} + \epsilon</math>, ahol p az összekötési valószínűség, N a csúcsok száma és <math>\epsilon</math> egy kicsi szám. Az egyes komponenseken belül is kisvilág tulajdonság

@@ 70. sor: / 70. sor: @@
 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éső csúcsai pedig az eredeti maggal összekötöttek
+* 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...
 [[Kép:Ravasz_Barabasi.png|center|200px|thumb|]]

@@ 11. sor: / 11. sor: @@
 *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. <math>p<k> = N_k / N</math> (ahol <math>N_k</math> 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ó)
+* 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)
 <math>c_i = \frac{2e_i}{k_i(k_i-1)}</math>, ahol <math>e_i</math> az i-edik csúcs szomszédai közti élek száma. Átlagos klaszterezettség: <math><c> = \frac{1}{N}\sum(c_i)</math>