Komplex hálózatok: alapfogalmak, modellek, módszerek

Motiváció

Alapfogalmak

Centralitás mértékek

Néhány gráfmodell

Komplex hálózatok: alapfogalmak, modellek, módszerek

London András, Németh Tamás

2015. április 13.

Közösségek

Motiváció

Alapfogalmak



Hálózatok mindenhol!

ábra 1:

Facebook kapcsolati háló

Közösségek

Motiváció

Alapfogalmak



Közösségek


ábra 2:

9/11 terrorista hálózat (kapcsolatok, pénzáramlás). Bármely két

pont legfeljebb 2 távolságra van egymástól. Forrás: Paul Sperry, NY Post

Motiváció

Alapfogalmak




ábra 3:

Európai légi közlekedési hálózat dinamikusan.

Közösségek

Motiváció

Alapfogalmak




ábra 4:

Az USA elektromos ellátó rendszere. 2003.08.14-én az

észak-keleti áramellátás teljesen leállt.

Közösségek

Motiváció

Alapfogalmak




ábra 5:

A Trónok harca szerepl®inek interakciói (1-2. évad). Az élek

vastagsága a találkozások számával arányos.

Közösségek

Motiváció

Alapfogalmak



Mit®l komplex?

Sok egymással kapcsolatban álló és egymásra ható szerepl® Adaptivitás: visszajelzés, kooperáció Növekedés, evolúció Nincs linearitás: Az egész több, mint a részek összessége!

Közösségek

Motiváció

Alapfogalmak



Közösségek

Gráfok

Deníció (Gráf )

G := (V , E ) gráf, ahol V = (1, 2 . . . , N) a gráf csúcsai

ábra 6:

és

E ⊆V ×V

a gráf élei.

Gráfok, alapfogalmak. (Forrás: Aaron Clauset, Network Analysis

and Modelling course)

Motiváció

Alapfogalmak



Közösségek

Gráfreprezentációk

ábra 7:

Gráfreprezentációk: Szomszédsági mátrix, szomszéd lista, éllista

(Forrás: Aaron Clauset, Network Analysis and Modelling course)

Motiváció

Alapfogalmak



Közösségek

Fokszámok, utak, komponensek

A = [aij ] ∈ Rn×n i

pont foka:

ki =

Fokszámeloszlás:

G Pn

szomszédsági mátrixa:

j=1 aij

P(egy

Út: csúcsok sorozata,

véletlenül választott pont foka

(i, j, k, . . . , m, n),

k)

ahol az egymást

követ® csúcsok között van él; legrövidebb út két pont között: az összes lehetséges út közül a legrövidebb. Komponens, er®sen összefügg® komponens, stb.

Motiváció

Alapfogalmak



Közösségek

Mennyire fontosak a hálózat pontjai?

struktúrális tulajdonság szempontjából, például magas fokszámú a központban van valamilyen dinamikus folyamat szempontjából fontos (pl. fert®zés terjedés, véletlen bolyongás)

=⇒

Centralitás

Minél centrálisabb annál fontosabb, minél kevésbé centrális annál kevésbé fontos

Motiváció

Alapfogalmak



Fokszám

Nagyobb fokszám

ki =

→

Pn

fontosabb pont

j=1 aij ; irányított:

ábra 8:

kibe =

Pn

j=1 aji ,

kiki =

Be- és kifok centralitás.

Pn

j=1 aij

Közösségek

Motiváció

Alapfogalmak



Közösségek

Közelség (closenes), köztiség (betweennes)

Closeness: mennyire van a központban a pont

→

átlagosan

milyen hosszúak a pontból induló legröviebb utak a hálózat többi pontjába

n−1 C (i) = P , i6=j `ij ahol

`ij

=⇒

Számolás: Floyd-Warshall algoritmus

az

i

és

j

közti legrövidebb út hossza.

ábra 9:

Mennyi X és Y closeness értéte?

Motiváció

Alapfogalmak



Közösségek

Közelség (closenes), köztiség (betweennes) Betweenness: Két pont milyen messze van egymástól, ha át kell menni egy kijelölt harmadik ponton

BC (k) =

X σij (k) , σij

i6=k6=j ahol

σij

a

i

legrövidebb

=⇒

j közötti legrövidebb utak száma, σij (k) i − j utak száma, melyek átmennek k -n

és

Szorgalmi: gondolkozzunk egy

O(nm)

futási idej¶

algoritmuson (m a gráf éleinek száma)

ábra 10:

Mennyi X és Y betweennes értéte?

pedig azon

BC

számító

Motiváció

Alapfogalmak



Sajátérték, PageRank

Alapötlet: nem minden szomszéd egyforma súllyal számít a centralitás kiszámításánal Rekurzív formula:

(t+1)

xi

=

n X

(t)

wij xj

j=1 Minél fontosabb a szomszéd, annál jobban járul hozzá az adott pont fontosságához Mátrix formában:

x

x

A = λ1 , ahol

λ1

az

A

mátrixhoz tartozó legnagyobb sajátérték

Közösségek

Motiváció

Alapfogalmak



Sajátérték, PageRank Mi a helyzet ha a gráf nem összefügg®?

=⇒

Véletlen

1 szörföz®, ld. Google keres®motor Rekurzió:

PR(i)

1

X PR(j) −λ +λ , n k ki (j) + j∈N (i)

ahol

λ ∈ [0, 1]

paraméter (ugró faktor),

N + (i)

az

be-szomszédsága

1

Brin & Page, Computer networks and ISDN systems ,1998

i

pont

Közösségek

Motiváció

Alapfogalmak



Gráfmodellek

Milyen általános közös tulajdonságai vannak tipikus gráfoknak? Tudjuk-e valamilyen modellel közelíteni a valóságban megjelen® hálózatokat? A különböz® területeken (társadalom, gazdaság, biológia, technológia) megjelen® hálózatok modelljei között mik a legfontosabb különbségek/hasonlóságok?

Közösségek

Motiváció

Alapfogalmak

Erd®s-Rényi modell

G (n, p)



Közösségek

2

minden élt

p ∈ [0, 1]

valószín¶séggel húzunk be,

egymástól függetlenül élek száma várhatóan: átlagos fokszám:

n

2

p

k = (n − 1)p

fokszámeloszlás:

n−1 k P(ki = k) = p (1 − p)n−1−k , k azaz binomiális. Fontos és rendkívül sokat vizsgált matematikai modell A valóságban megjelen® hálózatok jellemz®en nem ilyen típusúak! 2

Erd®s & Rényi, 1959

Motiváció

Alapfogalmak



Közösségek

Kisvilág gráfok

Stanley Milgram (1933-84) kísérlete: véletlenül kiválasztott emberek küldjenek egy levelet egy közeli ismer®snek, hogy az szintén továbbküldje így, azzal a céllal, hogy egy általuk valószín¶leg ismeretlen bostoni orvoshoz eljusson végül a levél A 64 levél az USA 64 különböz® pontjáról átlagosan 5.5 levélváltás után célba ért

=⇒

Kicsi átmér®: A legtávolabbi pontok sincsenek túl messzire

egymstól... További fontos jellemz®: háromszögek száma nagy

Motiváció

Alapfogalmak


Watts-Strogatz modell


3

Kiindul egy 4-reguláris gráfból (minden pont foka 4) Minden élt

p

valószín¶séggel átdrótoz ( azaz

választunk véletlenül egy töröljük

=⇒ ∼ log n

(i, j)-t

3

és behúzzuk

az átmér®; Ha

valószín¶séggel

k

(j, k)

(i, j)

pontot, és

p

(i, j)

él esetén

valószín¶séggel

(i, k)-t)

és

(i, k)

is él, akkor nagy

is az (azaz háromszövek száma nagy)

Watts & Strogatz, Nature, 1998

Közösségek

Motiváció

Alapfogalmak


Barabási-Albert modell


Közösségek

4

Genaratív modell hogyan fejl®dhet ki egy hálózat? A

preferential attachment modell : kezetben egy összefügg® G0 gráf n0 ponton 2 t id®pontban hozzáadunk Gt -hez egy új v pontot 1

P(v -t

összekötjük egy meglév®

ki i -vel) = P j

4

Barabási & Albert, Science, 1999

kj

Motiváció

Alapfogalmak



Barabási-Albert modell

Úgynevezett skálafüggetlen hálózatot kapunk:

P(ki = k) ∼ k −α Hatványtörvény szerinti fokszámeloszlás: néhány pont foka nagy, viszont a legtöbb pontnak csak kevés szomszédja van Átlagos úthossz:

` ∼ ln n/ ln ln n

A valóságban számos hálózat ilyen tulajdonságot mutat: szociális hálók, pénzügyi hálózatok, WWW, biológiai hálózatok, közlekedési hálózatok, stb.

Közösségek

Motiváció

Alapfogalmak



Közösségek

Közösségek Nagyméret¶ szervez®dési mintázatok keresése Bizonyos pontok hasonlóbbak/ közelebb vannak egymáshoz, míg más pontoktól távol helyezkednek el

ábra 11:

Hálózat három közösséggel.

Motiváció

Alapfogalmak



Közösségek

Közösségek - modularitás

Az adott gráf mennyire tér el egy ugyanolyan fokszámeloszlású véletlen gráftól?

Modulartás

= #{közösségen belüli élek}

E[#{közösségen

belüli élek}) egy azonos fokszámeloszlású véletlen gráfban] Newman-modularitás

Q= δ

5 1

X

2M

a Dirac-delta függvény,

hogy

i

és

j

(aij − pij )δ(Ci , Cj ),

i,j

pij

pedig annak a valoszín¶sége,

össze van kötve egy véletlen (null-modell) gráfban

Szorgalmi: gondolkozzunk közösség keres® algorimusban, melynek lényege a modularitás függvény maximalizálása

5

Newman, Physical Review E, 2004

Motiváció

Alapfogalmak



Néhány további fontos hálózati szerkezet Mag-periféria Hagymaszerkezet Nestedness (egymásba ágyazottság) Rich club

ábra 12:

További tipikus hálózat szerkezetek

Közösségek

Komplex hálózatok: alapfogalmak, modellek, módszerek

Recommend Documents