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

Közösségek hálózatban

Homofília, asszortatívitás

Newman modularitás

Közösségkeres® algoritmusok

Társadalmi és gazdasági hálózatok modellezése 5. el®adás Közösségszerkezet

El®adó: London András

2017. október 16.



Newman modularitás


ábra 1:

Facebook kapcsolati háló




Newman modularitás


Közösségek hálózatban Egyszer¶ mértékek: átlagos fokszám, fokszámeloszlás, klaszterezettség, átlagos úthossz

−→

sok információ a

hálózatról DE elrejthetik az eloszlás heterogenitását

ábra 2:

Háromszögek száma nagy, de azok csak a hálózat egy részén

találhatók Mi a magas szint¶ szervez®dés mintázata? Kis méret¶ hálózat: szemmel látható (?); nagy méret¶ hálózat: kvantatív eszközök szükségesek



Newman modularitás


Magas szint¶ szervez®dési mintázatok

ábra 3:

Közösségszerkezet, mag-periféria szerkezet, rendezett (lineáris

hierarchia) szerkezet (forrás: Aaron Clauset, Network analysis and modelling course)



Newman modularitás


Asszortatív kapcsolódás

Bizonyos attribútumok (tulajdonságok, jellemz®k) kapcsolatára az meglév® élek világítanak rá

−→

pl. ismer®seink egy

részének közös jellemz®je a középiskola, ahová jártak Társadalmi hálózatokban jellemz®, hogy olyan ismer®seink vannak akik hasonlítanak ránk. Pl. életkor, nyelv, születési hely, végzettégi szint, anyagi helyzet Fontos kérdés: (1) az él a hasonlóság miatt létezik, vagy (2) az él létezése (ismerettség) miatt hasonlóvá válnak az attribútumok? (ld. pl. politikai beállítottság) (Egy modellezési lehet®seg: Fitness modell (a kés®bbiekben

tárgyaljuk, esetleg projektfeladat) )



Newman modularitás


A modularitás függvény

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= δ

1 1

X

2m

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

i,j

a Dirac-delta függvény (δ(Ci , Cj )

különben),

eij

az

i

és

j

= 1,

ha

i =j

és 0

közti élek számának várható értéke

(általában 0 és 1 között) egy véletlen (null-modell) gráfban

1

Newman,

Physical Review E, 2004



Newman modularitás


De mi legyen a null-model?

A síma véletlen gráf

G (n, p)

átalában nagyon messze van a

valós hálózatktól. Használjuk a konguráció modellt Azaz ha az eredeti gráf fokszámsorozata

eij =

(k1 , k2 , . . . , kn )

akkor

ki kj 2m

így

Q=

X ki kj )δ(Ci , Cj ), (aij − 2m 2m 1

i,j

A cél pedig a pontok osztályozása (szétosztása) osztályokba (klaszterekbe), hogy legyen.

Q

C1 , . . . , Ck (k =?)

minél nagyobb (maximális)



Newman modularitás


Modularitás maximalizálás

Ha

S

a

G

gráf pontjainak összes lehetséges partícionálása

(klaszterezése) akkor egy

P∈S Q

f :S →R

függvény méri egy adott

felosztás jóságát (Mit®l jó?)

egy lehetséges ilyen függvény

−→

minél nagyobb, annál

jobban klaszereztünk

S

mérete exponenciálisan nagy (miért?), továbbá

maximalizálni

NP -nehéz

Léteznek jól m¶köd® heurisztikák

Q -t



Newman modularitás


Egy mohó algoritmus 1

Kezdetben minden pont egy önálló közösség

2

Majd mohó módon olvasztunk össze közösségeket, aszerint, hogy a lépés minel jobban növeli

ábra 4:

Q

értékét

Közösségek és hierarchikus szerkezet

Az eljárás implementálásra számos különböz® technika létezik (ld. pl. single linkage, average linkage, etc.)



Newman modularitás


Algoritmusok sokasága

Modularitás optimizálás számos változata

Más kiértékel® függvények használata (Mit tartunk fontosnak közösségkeresés esetén?)

Sztochasztikus blokk modell (tárgyaljuk részletesebben)

Átfed® közösségek keresése

Spektrális módszerek, dinamikus közösségkeresés

...



Newman modularitás


Jegyzet, további olvasnivaló: Véletlen gráfok: Jackson könyv IV. fejezet, Newman cikk IV. szakasz Közösségek: Newman III. szakasz Közösségkeresés összefoglaló cikk: Santo Fortunato (2010): Community detection in graphs, Physics Reports

Feladat: Próbáljunk ki különböz® közösségkeres® algoritmusokat egy valós gráfon, nézzük meg a különbségeket

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

Recommend Documents