Összetett hálózatok vizsgálata az Internet és a csomagfügg®ségi hálózat példáján Horváth Árpád 2013. április 18.
Összetett hálózatok
Nagyobb gráfok összetett tulajdonságokkal. csúcs
él 5 fokszámú csúcs
csomópont (nagy fokszám)
Összetett hálózatok (complex networks)
Hálózatok ≈ gráfok, vagy azok id®ben változó sorozata Összetett hálózatok: szerkezetük nem írható le egyszer¶en.
Átmér® 1
Útvonal hossza, a benne szerepl® élek száma. Az 1204 53 út hossza . Két csúcs távolsága: a közöttük vezet® legrövidebb út hossza. d(1, 3) = mert van közöttük három hosszúságú út, de rövidebb nincsen.
2 0 3
4 5
De níció Hálózat átmér®je Példák hálózatokra
hálózat ismeretségi h. Világháló Internet cikkek h. fehérjeh. szavak h.
csúcsok személyek weboldalak routerek cikkek fehérjék szavak
színészek h.
színészek
él van ha. . . találkoztak van köztük link van vezeték közöttük hivatkozik a másikra közös kölcsönhatásban részt vesznek ha szerepelnek együtt a szinonímaszótárban szerepeltek közös lmben 1
ir. ↔ → ↔ → ↔ ↔
↔
Határozzuk meg az összes csúcspár esetén a köztük lév® távolságot. Ezeknek a távolságoknak a maximuma a hálózat átmér®je. D = max d(i, j) i6=j
Átmér®
D2 = . Bármelyik kett® között mehetünk a középen lév®n keresztül kett® hosszúságún, de egy hosszúságú út nincsen például az alsó és a fels® között.
D1 = . Bármelyik kett® távolsága legfeljebb 4, és az alsó és fels® között pontosan annyi.
1. A fokszámeloszlás A fokszám 1. de níció.
A hálózat egy csúcsának fokszáma (degree) alatt a hozzá csatlakozó élek számát értem. Ha nem engedek meg többszörös éleket és a kiinduló csúcsba visszatér® hurokéleket, akkor ez a szomszédok számát is megadja. Irányított hálózatok esetén külön értelmezhetünk befokszámot (a nyilak hegyét számoljuk meg), és kifokszámot a nyilak kezd®pontját számoljuk meg.
5 1
3
6 2
7
8 4
5 1
6 2
7 3
Kapcsolat a hálózatok alapvet® tulajdonságai között
8 4
kbe,7
=
kki,7
=
k7
=
Az éleknek kép végpontja van, tehát minden egyes él kett® csúcs fokszámát növeli meg. Az átlagos fokszám: 2M hki = N Be-fokszám esetén az átlagos fokszám: M hkbe i = N Ki-fokszám esetén szintén.
Példák
2
5 1
3
Mekkora az ábrán látható hálózatban
6
• az átlagfokszám, az átlagos kifokszám és az átlagos befokszám,
2 7
8
• a maximális és minimális fokszám, • a maximális befokszám és maximális kifokszám?
4
1.1. Hálózatmodellek és fokszámeloszlásuk
Erd®s Pál és Rényi Alfréd Véletlen hálózatok
Véletlen hálózatok • Erd®s Pál és Rényi Alfréd vizsgálta 1959-t®l. • Véletlen hálózatoknál adott egy N csúcsszám és egy p valószín¶ség. • Végigmegyek az összes csúcspáron és p valószín¶séggel élt húzok közéjük.
Élek száma és átlagfokszám a véletlen hálózatokban • Ha a hálózat teljes hálózat lenne, benne Mteljes =
N (N − 1) 2
él lenne. (Minden csúcsból N − 1 él, de akkor mindet kétszer számoltam.)
• Élek várható száma a véletlen hálózatban: E(Mv ) = p ·
N (N − 1) p · N2 ≈ 2 2
3
ha N nagy
• Az átlagfokszám várható értéke: E(hki) = p(N − 1) ≈ p · N
ha N nagy
Az utóbbi összefüggés kétféleképpen is származtatható. Az egyszer¶bb módszer, hogy megnézzük hány él futhatna ki maximálisan egy csúcsból: ha teljes lenne a hálózat, akkor egy csúcs az összes többi N − 1 csúccsal össze lenne kötve. Ha p valószín¶séggel választjuk ki az éleket, akkor nyilván p(N − 1) fog ezek közül létezni átlagosan, így az átlagfokszám ennyi lesz. A másik lehet®ség, ha az átlagfokszám kiszámításának hki = 2M/N képletébe behelyettesítem a várható értékét az élek számának a véletlen hálózatban.
A fokszámeloszlás 2. de níció.
A p(k) fokszámeloszlás (degree distribution) egy olyan függvény, amely az egyes k fokszámokhoz hozzárendeli annak a valószín¶ségét, hogy egy véletlenszer¶en kiválasztott csúcs k fokszámú, azaz
p(k) = P rob(véletlen csúcs fokszáma = k)
Példák 5 9
1
10
Az ábrán látható hálózat fokszámeloszlása: k Nk p(k) 0 1 2 3 4 5 6 7
6 2
7
3
8 4
Megoldás a végén.
Két hálózatmodell eloszlása
(darabszám)
Két eltérő modellből származó hálózat fokszámeloszlása Barabási-Albert modell (m=3) Erdős-Rényi modell (p=0,006)
p(k)
valószínűség
10-1
csúcsok száma 10000 átlagos fokszám kb. 6
10-2
10-3
10-4
100
101
k 4
fokszám
102
103
• A valódi hálózatoknál általában nem az Erd®sRényi modell fokszámeloszlását tapasztalták. • Az eloszlás fontos lehet a hálózaton történ® folyamatok (vírusterjedés, meghibásodás, célzott támadás, hírek terjedése) és hatásaik szempontjából. • Vajon hogyan jön létre egy hálózat?
A hálózatok kialakulása •
1. A hálózat növekszik. 2. Népszer¶ségi csatlakozás: a nagyobb fokszámú csúcshoz nagyobb valószín¶séggel csatlakoznak.
• A BarabásiAlbert modell szerint egy tetsz®leges kezd® hálózatból indulunk ki. Minden lépésben egy új csúcs keletkezik, és adott m számú éllel kapcsolódik a régi csúcsokhoz. A kapcsolódás valószín¶sége arányos a fokszámmal. Barabási Albert-László, a Behálózva cím¶ könyve és Albert Réka
Az élek száma a BA-modellben • A BarabásiAlbert-modellben az élek száma minden lépésben m-mel növekszik. • Ha kezdetben N0 csúcs volt, és M0 él, akkor N − N0 lépést kellett végrehajtani, amiben (N − N0 )m él jött létre, tehát az élek száma • M = M0 + (N − N0 )m • Ha a végén a csúcsok száma jóval nagyobb, mint kezdetben, akkor jó közelít® értéket kaphatunk az M ≈m·N képletb®l.
• Tehát az átlagos fokszám hki =
2M ≈2·m N
• Ez nem meglep®, hiszen minden lépésben 2 · m élvég jön létre. 5
1.2. Az összegzett fokszámeloszlás
Az összegzett fokszámeloszlás 3. de níció.
A P (k) összegzett fokszámeloszlás (cumulative degree distribution) egy olyan függvény, amely az egyes k fokszámokhoz hozzárendeli annak a valószín¶ségét, hogy egy véletlenszer¶en kiválasztott csúcs fokszáma nagyobb vagy egyenl® mint k , azaz
P (k) = P rob(véletlen csúcs fokszáma ≥ k) • Kevésbé ugrál nagy fokszámoknál. • Ha az eredeti p(k) hatványfüggvény, akkor a P (k) is az lesz. • A kitev® eggyel kisebb abszolútérték¶ lesz. • A hatványfüggvény kétszer logaritmikus skálán egyenes.
Néhány hálózat összegzett fokszámeloszlása 0
0
10
10
10 10
-2
-2
0
-2
10
10
10 -4
-4
10
10
(a) matematikai együttmûködések
10
(b) hivatkozások
-4
-6
(c) World Wide Web -8
1
10
100
1
10
100
10
1000
0
0
10
10
-1
10
10
-2
10
0
10
10
-1
4
0
-1
-2
10
-2
-3
(f) fehérje kölcsönhatások
-3
10
(d) Internet
10
10
10
10
2
10
-3
(e) elektromos hálózat
10
-4
10 1
10
100
1000
0
10
20
1
10
Az el®z® oldalon a következ®k szerepelnek. Matematikusok együttm¶ködkése (közös cikkek), cikkek hivatkozásai, Világháló, Internet, elektromos hálózat, fehérjekölcsönhatások. A fentiek közül csak az elektromos hálózat nem skálafüggetlen. (Lineáris skála a vizszintes tengelyen.)
Skálafüggetlen hálózatok 4. de níció. Skálafüggetlen hálózatoknak nevezzük azokat a hálózatokat, melyeknek a fokszámeloszlása hatványfüggvényt követ nagy fokszámok esetén: p(k) ∼
k −γ
P (k) ∼
k −(γ−1)
A hatványfüggvényre igaz egyedül:
f (c1 · x) = c2 · f (x) c1 , c2 ∈ R
6
6
10
Ellenállóképesség 1. Véletlen meghibásodás: Ha véletlenszer¶en veszek el csúcsokat (pl. az Internet routereinek véletlen meghibásodása)
• a skálafüggetlen hálózatok sokáig egyben maradnak, nem esnek szét komponensekere, • például az Internet érzéketlen a véletlen routermeghibásodásokkal szemben. • A véletlen hálózatok hamarabb esnek szét. 2. Célzott támadás: Ha célzottan a legnagyobb fokszámú csúcsokat törlöm ki
• a skálafüggetlen hálózat hamar és rövid id® alatt esik szét nagyon kicsi darabokra. • A véletlen hálózatok tovább egyben maradnak. Egyik hatással szemben az egyik, másikkal szemben a másik ellenállóbb. Egyik sem tökéletes.
2. Ubuntu szoftvercsomagjai komponensek Az Ubuntu szoftvercsomagjai
• Az Ubuntu a GNU/Linux operációs rendszer egyik disztribúciója • A Debianból származó deb szoftvercsomagokat használ • A deb fájlok optikai diszkr®l vagy Internetes tárolókból érhet®ek el. • Legtöbb csomag másikaktól függ, • tehát irányított hálózatot alkotnak. • apt csomagkezel® rendszer: telepítés függ®ségekkel együtt, eltávolítás, frissítés, keresés
A csomagfügg®ségi hálózat egy részlete
vim-latexsuite
vim-vimoutliner
vim
vim-common
python2.5
vim-runtime
libc6
7
libgpmg1
libncurses5
Csomagok, amit®l sok másik függ (nagy be-fokszám kin ) Átlagos be-fokszám: élek száma/csúcsok száma = 5,077. kin csomagnév megjegyzés 11113 libc6 C standard könyvtár 3230 libgcc1 C-fordító könyvtárai 3109 libstdc++6 C++ standard könyvtár 2696 libx11-6 A gra kus felület könyvtára 1985 libglib2.0-0 A GLIB könyvtár 1940 zlib1g Tömörít® könyvtár 1929 perl Perl programnyelv 1865 libxext6 A gra kus felület kiterjesztései 1381 libgtk2.0-0 A GTK gra kus felület könyvtárai 1296 python A Python nyelv :-)
Er®sen összefügg® komponensek (a második legnagyobb) libmono-posix2.0-cil libmono-system2.0-cil
Legtöbb valódi hálózatban egy csúcs szomszédjai nagyobb valószín¶séggel össze vannak kötve, mint tetsz®leges kett®. Szociológiai példa: két ismer®söm nagyobb valószín¶séggel ismeri egymást, mint tesz®leges két ember. Hogyan számszer¶síthet® ez?
Állítás
Ha egy irányítatlan egyszer¶ hálózatban az i. csúcs ki szomszédja között legfeljebb futhat. Egyszer¶ hálózat: nincs többszörös él, és a csúcsot önmagával összeköt® hurokél.
Csoporter®sségi együttható: példa
Z-nek 5 ismer®se van. Folytonos vonal (él): ismerik egymást.
9
él
Bob Cili Z
Alice
Dani Egon Z ismer®sei között
lehetséges élb®l
létezik. ⇒
Z csoporter®sségi együtthatója
.
Csoporter®sségi együttható De níció
Egy 1-nél nagyobb fokszámú csúcs Ci csoporter®sségi együtthatója (angolul clustering coe cient)
Ci =
2Ei , ki (ki − 1)
ahol Ei a csúcs szomszédjai közötti élek tényleges száma. A hálózat C csoporter®sségi együtthatója ezek átlaga. (Csak az 1-nél nagyobb fokszámú csúcsok együtthatóját átlagoljuk.)
Példa
5
6
C1 =
2
1
C3 =
7
8
3
C2 = C7 = C =? (otthon)
4
Valódi hálózatok csoporter®ssége
A szaggatott vonal mindenhol a −1-es kitev®nek felel meg. 10
10
0
0
(b)
10
C(k)
C(k)
(a)
−1
10
10
−1
−2
10
0
10
1
10
2
10
3
10
4
k
1
10
100
k
a) Színészek, www.IMDB.com szerint szerepeltek közös lmben (N = 392 340) b) angol szavak, Merriam Webster szótár szerint szinonímák (N = 182 853) 10
Hierarchikus hálózatok 5. de níció.
Egy hálózatot hierarchikusnak nevezünk, ha benne a csúcsok csoporter®sségi együtthatója a fokszámmal nagyjából fordítottan arányos.
