Társadalmi és gazdasági hálózatok modellezése

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Társadalmi és gazdasági hálózatok modellezése 2. el®adás  A hálózatkutatás néhány fontos fogalma

El®adó: London András 2015. szeptember 15.

Szoftverek

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Szoftverek

Átmér®

`ij

 a legrövidebb út a hálózatban

∆ = maxi,j `ij

i

és

j

pont között

 átmér®: az összes legrövidebb út közül a

legnagyobb

ábra 1:

mennyi egy

N

pontú kör és egy

N

pontú bináris fa átmér®je?

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Átlagos úthossz

A legrövidebb úthosszak átlaga

h`i =

1

X


n 2

`ij

i,j

Valós hálózatokban miért érdekes, milyen információt ad?

Szoftverek

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Szoftverek

Fokszámeloszlás

A = [aij ] ∈ Rn×n i

pont foka:

ki =

Fokszámeloszlás:

G Pn



szomszédsági mátrixa:

j=1 aij

P(egy

véletlenül választott pont foka

k)

Miért érdekes egy hálózat fokszámeloszlása? Milyen fokszámeloszlást követnek a valós hálózatok?

−→

kulcsfontosságú fogalom, a kés®bbiekben részeltesen tárgyaljuk

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Szoftverek

Melyek a hálózat fontos 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 De hogyan mérjük a centralitást?

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Szoftverek

Fokszám centralitás

Nagyobb fokszám

ki =

→

Pn

fontosabb pont

j=1 aij ; irányított:

ábra 2:

kibe =

Pn

j=1 aji ,

kiki =

Be- és kifok centralitás.

Pn

j=1 aij

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Szoftverek

Betweenness (köztiség) centralitás 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 3:

Mennyi X és Y betweennes értéte?

pedig azon

BC

számító

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Closeness (közelség) centralitás

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 4:

Mennyi X és Y closeness értéte?

Szoftverek

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Szoftverek

Harmonikus centralitás

Két probléma a closeness-szel: a valós hálózatok átmér®je átalában kicsi

→

a

C (i)

sz¶k tartományban változnak nem összefügg® hálózat esetén nem számolható Harmonikus centralitás

C h (i) = ahol

`ij = ∞,

ha nincs

i −j

út.

1

n−1

X j6=i

1

`ij

,

értékek

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Sajátérték centralitás

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:

Ax = λ1 x, ahol

λ1

az

A

mátrixhoz tartozó legnagyobb sajátérték (ld.

Perron-Frobenius tétel)

Szoftverek

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Szoftverek

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

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

HITS (Hyperlink Induced Topic Search) 2

Kleinberg fejlesztette ki , az eredeti PageRank "nomított" változata A gráf pontjainak rangsorolásánál megkülönböztet ún. Hub, illetve Authority pontokat Jó Authority pont, amibe sok link mutat Jó Hub az, amib®l sok link megy jó Authority pont felé

2

Kleiberg, Journal of the ACM ,1999

Szoftverek

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Szoftverek

HITS algoritmus

Input

G

irányított gráf

Output a pontok hub és authority értékei

1: 2: 3: 4: 5: 6: 7: 8: 9: 10:

Kezdetben minden pont értéke 1 repeat

i ∈ H do j∈F (i) aj {F (i):

for all hub

hi =

P

azon pontok, melyekb®l megy él

i -be}

end for

i ∈ A do j∈B(i) hj {B(i): azon pontok, melyekbe megy él i -b®l}

for all authority

ai =

P

end for until konvergál

Normálás

Átmér®, átlagos úthossz

Fokszámeloszlás

Centralitási mértékek

Néhány ingyenes program

Hálózat vizualizácó és elemzés Cytoscape (GUI) Gephi (GUI) iGraph (R, C++, Python)

Feladat : egy hálózat (pl. a Zachary-féle karate klub) pontjainak centralitásvizsgálata és vizualizáció. gondoljuk át mátrix egyenlet formában a PageRanket és HITS-et.

További olvasnivaló Jackson könyv 2. fejezet

Szoftverek