Átfed® modularitás optimalizálása hálózatokban Diplomamunka
írta: Tóth Bálint MSc zikushallgató Témavezet®: Dr. Palla Gergely ELTE TTK, Biológiai Fizika Tanszék
Budapest, 2012
Az egész több, mint a részek összessége. Arisztotelész
Tartalomjegyzék
1. Bevezetés
5
1.1.
A hálózatkutatás kezdetei
. . . . . . . . . . . . . . . . . . . . . . . .
7
1.2.
A valós hálózatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.3.
Véletlen gráf modellek
. . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.3.1.
Erd®sRényi modell (1959) . . . . . . . . . . . . . . . . . . . .
11
1.3.2.
A WattsStrogatz modell (1998) . . . . . . . . . . . . . . . . .
12
1.3.3.
A BarabásiAlbert modell (1999)
13
. . . . . . . . . . . . . . . .
2. Csoportkeresési eljárások
15
2.1.
Lokális csoport de níciók . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2.
Elterjedt algoritmusok nem-átfed® csoportok keresésére . . . . . . . .
19
2.2.1.
Particionálás
. . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.2.2.
Hierarchikus klaszterezés . . . . . . . . . . . . . . . . . . . . .
20
2.3.
A modularitás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.4.
A klikk-perkolációs módszer
. . . . . . . . . . . . . . . . . . . . . . .
24
2.5.
Átfed® modularitás fogalmak . . . . . . . . . . . . . . . . . . . . . . .
25
2.5.1.
A Newman-féle modularitás általánosításai . . . . . . . . . . .
25
2.5.2.
A Lázár-féle modularitás . . . . . . . . . . . . . . . . . . . . .
26
3. A k-klikk perkoláció kritikus pontjának vizsgálata
3.1.
28
Vizsgálati módszerek . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.1.1.
A kritikus pont meghatározása
. . . . . . . . . . . . . . . . .
29
3.1.2.
A Lázár-féle modularitás vizsgálata . . . . . . . . . . . . . . .
29
2
3.2.
3.1.3.
A Shen- és Chen-féle modularitás mérése . . . . . . . . . . . .
31
3.1.4.
A Pearson-korreláció, mint mérték . . . . . . . . . . . . . . . .
31
3.1.5.
A Kendall-féle rang-korreláció, mint mérték
. . . . . . . . . .
33
3.1.6.
Az adatfeldolgozás
. . . . . . . . . . . . . . . . . . . . . . . .
34
Eredmények . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.2.1.
Mobiltelefon hívások hálózata
. . . . . . . . . . . . . . . . . .
36
3.2.2.
Kollaborációs hálózatok
. . . . . . . . . . . . . . . . . . . . .
36
3.2.3.
Szóasszociációs hálózat . . . . . . . . . . . . . . . . . . . . . .
43
3.2.4.
Egyetemisták online szociális hálózata
. . . . . . . . . . . . .
46
3.2.5.
Összefoglalás
. . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4. Az átfed® modularitás optimalizáció ja
4.1.
A szimulált h®kezelésr®l
4.2.
Az algoritmus elemei
4.3.
4.4.
49
. . . . . . . . . . . . . . . . . . . . . . . . .
50
. . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.2.1.
A Lázár-féle átfed® modularitás pontosítása
. . . . . . . . . .
51
4.2.2.
A szomszédos megoldások hálózata
. . . . . . . . . . . . . . .
52
4.2.3.
Könyvelés
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
4.2.4.
Az összes szomszédos megoldás meglátogatásához szükséges id® 55
4.2.5.
Egyéb részletek
. . . . . . . . . . . . . . . . . . . . . . . . . .
56
Eredmények . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
4.3.1.
A vizsgált hálózatok
. . . . . . . . . . . . . . . . . . . . . . .
56
4.3.2.
Teljesítmény . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
4.3.3.
Az algoritmus eredményei példahálózatokon
. . . . . . . . . .
57
. . . . . . . . . . . . . . . . . . . . . . . .
58
Az elkészült algoritmusról
5. Összefoglalás
61
5.1.
Célok és motivációk . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
5.2.
A Lázár-féle modularitásról
. . . . . . . . . . . . . . . . . . . . . . .
61
5.3.
Köszönetnyilvánítás . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
3
A Fontos fogalmak, jelölések
63
A.1. Gráfok típusai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
A.2. A fokszám . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
A.3. Legrövidebb út és átmér®
. . . . . . . . . . . . . . . . . . . . . . . .
65
A.4. Gráfok alapvet® metrikái . . . . . . . . . . . . . . . . . . . . . . . . .
66
4
1. fejezet
Bevezetés
astrophysics
Előfordulás
particle physics 1,6% 1,4% 1,2% 1,0% 0,8% 0,6% 0,4% 0,2% 0,0% 1930
1940
1950
graph theory
1960
1970
1980
network theory
1990
2000
Év 1.1. ábra. A Google az ngrams projektje keretében mérte az egyes kifejezések el®fordulását a nyomtatásban megjelent m¶vekben. A fenti ábrán a zika egyes népszer¶ ágai mellett feltüntettem a network theory és a graph theory 2-gramok el®fordulását is az 1930-as évekt®l 2008-ig. (A projektben a 2008-ig megjelent könyveket vizsgálták. A százalékos arány a kifejezést tartalmazó kötetek arányát jelenti. For-
rás : books.google.com/ngrams )
Az elmúlt években jelent®sen megnövekedett a hálózatok iránti érdekl®dés, amit jól érzékeltet a témában megjelent publikációk száma (1.1. ábra). Érdekes a publikáló kutatók eredeti kutatási területeinek gazdagsága is : zikusok, biológusok, szo-
5
ciológusok, villamosmérnökök, vegyészek, informatikusok, hogy csak a legfontosabb területeket soroljam fel. Ennek oka a hálózat, mint fogalom egyetemes mivolta. Ez az egy egyszer¶ fogalom jelenségek széles skáláját képes hatékonyan leírni mint például a perkoláció, vírus terjedés vagy önszervez®dés , ami a sz¶kebb értelemben a statisztikus zika, tágabb értelemben a természet- és társadalomtudományok kikerülhetetlen eszközévé teszik azt. A természetben meg gyelhet®, úgynevezett valós hálózatoknak számos olyan tulajdonságát sikerült meg gyelnünk, amelyek egyre-másra visszaköszönnek. Ez egyik ilyen tulajdonság a csoportstruktúra, vagyis az a tény, hogy a legtöbb valós hálózat csoportokra - más szóhasználatban modulokra, klaszterekre vagy közösségekre - bontható bizonyos szempontok alapján. Persze az ördög a részletekben rejlik, mivel ezek a bizonyos szempontok nagyon különböz®ek tudnak lenni. Gondoljunk csak arra, hogy hányféle szociális vagy gazdasági csoportosulás létezhet az emberek ismertségi hálózatában : családok, iskolai osztályok, munkatársak, focicsapatok, stb. A csoport fogalmára éppen a lehetséges szempontok sokfélesége miatt nem lehet általánosan érvényes de níciót adni. Kés®bb látni fogjuk azonban, hogy mégis léteznek olyan tulajdonságok, amelyek minden hálózaton értelmezett csoporton teljesülni fognak : például egy csoport elemei egymáshoz er®sebben kapcsolódnak, mint a hálózat többi részéhez. A hálózatokon felvett csoportok érdekes tulajdonsága, hogy általában átfednek, vagyis vannak olyan elemek, amelyek több csoportnak is egyszerre tagjai. Ezen tulajdonság fontosságának a felismerése az utóbbi évek egyik fontos tanulsága [1]. Ennek a dolgozatnak a központi témája az átfed® modularitás, vagyis egy olyan mérték, amely segítségével egy valós hálózat egymással átfed® csoportjait lehet kvantitatív módon jellemezni, vagy adott esetben a hálózatban csoportokat megtalálni. A dolgozat két részre bomlik. Az els® két fejezetben bemutatom a hálózatkutatás jelenlegi helyzetét, és röviden összefoglalom a szakirodalomban fellelhet® csoportkeresési eljárásokat. A második részben ismertetem az átfed® modularitással, illetve a klikk-perkolációs módszer kritikus pontjával kapcsolatos, az elmúlt másfél évre visszanyúló vizsgálódásainkat, amelyek egy részét azóta témavezet®mmel, Palla Gerg®vel, és Vicsek Tamás professzor úrral közösen már online publikáltunk [2]. A dolgozatban felmerül® alapfogalmakat és jelöléseket a függelék A. fejezetében foglalom össze.
6
1.1. A hálózatkutatás kezdetei A hálózatkutatás a lehet® legtömörebben megfogalmazva a komplex rendszerek vizsgálata gráfok segítségével. A hálózatkutatás alapjait a gráfelmélet adja. Az els® gráfelmélettel foglalkozó cikk Leonhard Euler az 1736-ban a königsbergi hidakról írt tanulmánya volt
1
, melyben egy összetett problémát miszerint létezik-e
olyan útvonal amely Königsberg mind a hét hídján egyszer, és csak is egyszer megy át a csúcsok és élek, mint absztrakt fogalmak bevezetésével oldott meg. Magát a gráf kifejezést J. J. Sylvester egy 1878-as, a Nature -ben publikált cikkében vezette be, a kémiában a molekulák ábrázolásához használt diagramok analógiájára. Euler cikke után matematikusok serege kezdte el alkalmazni az újonnan létrejött fogalmi rendszert különféle algebrai, topológiai és kombinatorikai problémák megoldásához. A terület fejl®dése a huszadik század elején a kombinatorikai gráfelmélet megjelenésével új lendületet vett, amelyben kiemelked® jelent®sége van a magyar kutatók hozzájárulásának. Ezt jelzi, hogy az els® gráfelméleti kézikönyvet egy magyar tudós, K®nig Dénes írta 1936-ban, de a huszadik század legtermékenyebb matematikusa, Erd®s Pál is kiemelt gyelmet szentelt a területnek. Az ® nevéhez f¶z®dik az els® véletlen gráf modell, (Erd®sRényi modell [3]) ami a mai napig használt és fontos eszköz a hálózatkutatók kezében. Erd®s hagyatéka a gráfelméletben is meghatározó. Ezt jelzi, hogy több tanítványa, munkatársa nevéhez fontos gráfelméleti tételek f¶z®dnek. Szemerédi Endre idén, 2012-ben Lax Péter után második magyarként nyerte el a matematikai Nobel-díjként emlegetett Ábel-díjat, Erd®s Pál és Turán Pál egy kombinatorikai sejtésének bizonyításával. A kezdetekt®l fogva folyamatos volt az igény arra, hogy a természetben, illetve a társadalomban meg gyelhet® nagy (úgynevezett valós ) hálózatok kialakulására és fejl®désére kielégít® modellt alkossunk, meg gyeljük ezek legfontosabb tulajdonságait. Az áttörést a kilencvenes évek informatikai forradalma és az internet, mint a legnagyobb ember-alkotta mesterséges hálózat vizsgálata hozta el. A hálózatkutatás leginkább ekkor vált a gráfelmélet alapjain nyugvó, önálló kutatási területté. A valós hálózatokkal kapcsolatos alapvet® tudnivalókat foglalom össze az 1.2. alfejezetben. A valós hálózatok legfontosabb vizsgálati eszközei a véletlen gráf modellek, ezekr®l az 1.3. alfejezetben írok b®vebben.
1 Solutio
problematis ad geometriam situs pertinentis
7
1.2. A valós hálózatok
1.2. ábra. Az ismer®seim hálózata a myFnetwork Facebook-alkalmazásával megjelenítve. A három, láthatóan jól elkülönül® csoport a családom barátai, az egyetemi, illetve a középiskolai ismer®seim.
Komplex rendszereknek olyan rendszereket nevezünk a zikában, amelyek egymással kölcsönható részekre oszthatók, de a rendszer egésze olyan viselkedést mutat, amely a részek viselkedéséb®l nem triviális módon következik. Talán az egyik legszebb példa a sejt, amit végs® soron leírhatunk egymással kölcsönható vegyületek összességeként, de egyben mégis az élet elemi egysége. Az egymással kölcsönható részek legegyszer¶bb absztrakciója a gráf. A gráf minden egyes csúcsa egy-egy részt jelent : egy atomot a molekulában, egy vegyületet a sejtben, egy neuront az idegrendszerben, vagy egy embert a tömegben. A csúcsokat összeköt® élek jelentik a kölcsönhatást a komplex rendszer részei között. A hálózatok természetesen a biológián túl a természetes és mesterséges környezetünkben rengeteg helyen el®fordulnak. Ugyanilyen komplex rendszer, és így gráfokkal modellezhet® a madarak vonulása [4, 5], vagy a tápláléklánc. A mesterséges környezetünkb®l kézenfekv® példa az internet [6], illetve az interneten jelen lév® virtuális hálózatok, mint a WWW, vagy egy letöltés köré szervez®d® torrent-közösségek. A mérnöki hálózatokra
8
az internethez hasonlóan fontos példa a mikroprocesszorokon a vezetékek és tranzisztorok hálózata, vagy akár a villamos [7], illetve a telefon hálózat[8]. A közlekedésb®l kiváló példa Budapest tömegközlekedési hálózata, vagy Magyarország úthálózata. A 2008-ban indult pénzügyi válság újonnan rámutatott a bankszektorban mutatkozó hálózatok (kölcsönök és derivatívák hálózata) fontosságára. A hálózatok és a gráfelmélet a zikával is szoros kapcsolatban van, a két terület rendszeresen merít egymás eredményeib®l : A kés®bb ismertetend® perkoláció a fázisátalakulások els®, analitikus módon is egyszer¶en vizsgálható elméletét adta, míg az Ising-modell, mint a ferromágneses átalakulások modellje egyes csoportkeres® eljárásokban (pl. [9]) is visszaköszön. A hálózatkutatás egyik leginkább magától értet®d® alkalmazási területe a szociológia, ahol a harmincas évek óta szociogramok segítségével vizsgálják egy-egy közösség szerkezetét, illetve a közösségek fennmaradásának vagy bukásának okait. Az internet elterjedése magával hozta a szociális hálózatok tanulmányozásának min®ségi változását is ; a közösségi oldalakra feltöltött ismertségi kapcsolatokból (1.2. ábra), vagy az e-mail [10] hálózatok vizsgálatával sokat tudhatunk meg az egyén és a társadalom viszonyáról. A fentihez hasonló, valós hálózatoknak általában négy fontos tulajdonsága van (lásd 1.1. táblázat), ezek az alábbiak :
1. A ritkaság, vagyis hogy egy átlagos csúcsnak a hálózat teljes méretéhez képest kevés szomszédja van. Másképpen megfogalmazva a hálózat éls¶r¶sége (vagyis annak a valószín¶sége, hogy két véletlenszer¶en választott csúcs össze van kötve) kicsi, az átlagos fokszám nem függ a hálózat méretét®l. 2. A klaszterezettség, vagyis hogy a csúcsok szomszédai nagy valószín¶séggel egymással is szomszédosak. Ennek a kritériumnak a gráfelméletbeli megfogalmazása, hogy a hálózat klaszterezettségi együtthatója vagyis a csúcsok szomszédait összeköt® élek, és a szomszédok között lehetséges élek hányadosának átlaga jóval magasabb, mint egy megegyez® méret¶ és s¶r¶ség¶ Erd®sRényi gráfban. 3. A kis-világ tulajdonság, vagyis hogy két csúcs közötti út hossza jóval elmarad attól, amit szabályos, rácsszer¶ struktúráktól várnánk. Precízebben ez azt jelenti, hogy a hálózatban az átlagos legrövidebb úthossz a rendszer méretének logaritmusával, vagy annál lassabban növekszik.
9
4. A negyedik tulajdonság a skálafüggetlen viselkedés, vagyis hogy egy átlagos csúcs szomszédjainak számában jelent®s eltérések mutatkoznak, a fokszámeloszlás jellemz®en hatványfüggvény-eloszlást követ.
Hálózat
N
hdi
hli
hlirand
C
Crand
WWW linkek hálózata
153 · 103
35,21
3,1
6,3
0,2
2,3 · 10−4
Internet, domain szint
6209
4,11
3,76
6,18
0,3
1,0 · 10−3
Színészek hálózata
2,25 · 105
61
3,65
2,99
0,79
2,7 · 10−4
Orvosi társszerz®ség
1,52 · 106
16,1
4,6
4,91
0,066
1,8 · 10−4
7 · 104
3,9
9,5
8,2
0,59
5,4 · 10−5
134
8,7
2,43
2,26
0,22
0,06
154
4,75
3,40
3,23
0,15
0,03
Elektromos hálózat
4,941
2,67
18,7
12,4
0,08
5 · 10−3
Szinonimák
2,2 · 104
13,48
4,5
3,84
0,7
6 · 10−4
282
14
2,65
2,25
0,28
0,05
Matematikusok társszerz®sége Ythan torkolat tápláléklánc Silwood park tápláléklánc
C. Elegans gy¶r¶sféreg idegrendszere
1.1. táblázat. Valós példahálózatok tulajdonságai.
hdi
a hálózat koordinációs száma.
zat klaszterezettségi együtthatója.
hli
N
a hálózat csúcsainak száma,
az átlagos legrövidebb úthossz, míg
hlirand
és
Crand
C
a háló-
ugyanezek a mennyiségek azonos
méret¶ és éls¶r¶ség¶ Erd®s-Rényi gráfban. Forrás : [11]
A kis-világ tulajdonságot a feljebb már említett Erd®sRényi gráf is teljesítette. A magas klaszterezettség és a kis világ tulajdonság kapcsolatára mutatott rá Duncan J. Watt és Steven Strogatz, 1998-ban, a Nature-ben publikált cikkükkel [7], míg a skálafüggetlen viselkedésre Albert Réka és Barabási Albert-László 1999ben megjelent cikkükkel [15] adtak egy lehetséges magyarázatot. Watts és Barabási mindamellett, hogy nagyon eredményes, új paradigmákat vezettek be a hálózatkutatásban, ismeretterjeszt® könyveikkel ([12], [13]) segítettek a tágabb társadalom körében is népszer¶síteni a hálózatkutatást, és kiemelni a hálózatok fontosságát, ami nagy mértékben hozzájárult a terület napjainkban tapasztalható, gyors fejl®déséhez.
10
1.3. Véletlen gráf modellek 1.3.1. Erd®sRényi modell (1959) p=0,02
p=0,078
p=0,04
1.3. ábra. Egy Erd®sRényi gráf 50 csúcson, különböz®
p
élbekötési valószín¶ségek
mellett. A legnagyobb, ún. óriás komponenst mindenhol fehér csúcsokkal jelöltük. Az els® ábrán
p = 0,02
a hálózat kritikus pontja.
p = 0,04-nél
már ez a komponens
tartalmazza a házat jelent®s részét, egy-egy izolált pont vagy különálló komponens látható csak.
p = 0,072-nél
a hálózat teljesen összefügg®vé válik.
Az els®, és egyben legismertebb modellt, amellyel a valós hálózatok tulajdonságait próbálták magyarázni, 1960-ban készítette Rényi Alfréd és Erd®s Pál [3], amit azóta Erd®sRényi modellnek, vagy egyszer¶en klasszikus véletlen gráf modellnek nevezünk. A modellben paraméterként adottak
N
és
p,
azaz a gráf mérete, és az él-
bekötési valószín¶ség. A gráfot úgy kapjuk, ha minden egyes lehetséges csúcspárját egymástól független,
p
valószín¶séggel összekötünk.
Erd®s Pál és Rényi Alfréd a perkoláció jelensége miatt vizsgálta ezt a modellt [14]. k azt a fázisátalakulást vizsgálták, ahogyan a véletlen gráf a
p ≈ 0 mellett jel-
lemz®, nem összefügg® elemekb®l álló, úgynevezett erd® szer¶ struktúrából, a
p≈1
értékeire jellemz®, teljes gráf szer¶, összefügg® struktúrává alakul át. Vizsgálódásuk eredménye az volt, hogy az átalakulás
p
függvényében nagyon gyorsan,
pc
kritikus
pontban következik be :
pc = N −1 11
(1.1)
Ekkor ugyanis
N → ∞
határesetben mindig megjelenik az úgynevezett óriás
komponens, vagyis a többi összefügg® komponensnél jóval nagyobb összefügg® részgráf. Az óriás komponens méretének várható értéke
pC -nél N 2/3 . Az óriás komponens
az élbekötési valószín¶séget tovább emelve egészen addig növekedni fog, amíg
=N
−1
ln N
p=
élbekötési valószín¶ségnél már az egész gráfot magába nem foglalja. A
folyamatot egy ötven csúcsból álló gráfon mutatom be az 1.3. ábrán. Ezen gráf a valós hálózatok szempontjából legjelent®sebb tulajdonsága, hogy teljesíti a kis-világ tulajdonságot, mivel a legrövidebb utak átlagos hossza
ln N/ ln pN .
Ez a gráf rendezetlenségének köszönhet®. A csúcsok fokszámeloszlása azonban nem skálafüggetlen, hanem binomiális-eloszlást követ, és az átlagos klaszterezettség megegyezik az éls¶r¶séggel. Egyszerre tehát a magas klaszterezettség és a ritkaság nem teljesülhet. Ez utóbbi két tulajdonság hiánya a bels® struktúra, a hierarchia vagy a csoportok hiányának következménye. Ezen ellentmondás feloldására a kilencvenes évek végéig várni kellett, amikor is az internet vizsgálatának köszönhet®en megjelent két újabb, napjainkig is fontos véletlen gráf modell.
1.3.2. A WattsStrogatz modell (1998) β=0,0
β=0,3
β=1,0
1.4. ábra. Egy WattsStrogatz-féle kisvilág gráf 15 csúcson, szomszéd és különböz®
β
élátkötési valószín¶ségek mellett.
2 dimenziós rácsot látjuk.
β = 0,3
K =4
β=0
kezdeti els®-
esetén a kiinduló
mellett már megjelennek a véletlenszer¶ átköté-
sek, ami miatt jelent®sen lecsökken az átlagos úthossz, míg a klaszterezettség magas marad.
β=1
esetén az eredeti, szabályos struktúra teljesen elt¶nik.
A WattsStrogatz modellben [7] egy olyan
N
méret¶ szabályos, periodikus rács-
ból indulunk ki, amelynek minden csúcsának pontosan
12
K
szomszédja van. A véletlen
gráfot ebb®l úgy kapjuk, hogy minden egyes él egy bizonyos végpontját
β
valószí-
n¶séggel a gráf egy véletlenszer¶en kiválasztott, másik csúcsára cseréljük. Egy ilyen hálózat szerkezetét szemléltetem
β
különböz® értékei mellett az 1.4. ábrán.
β =0
esetén a gráf egy szabályos, rács szer¶ struktúrát alkot, az átlagos legrövidebb út ennek megfelel®en hosszú, zik, és
β =1
N/2K . β
értékét növelve a gráf folytonosan megválto-
esetén egy Erd®sRényi gráfhoz nagyon hasonló struktúrájú hálózat
alakul ki. A numerikus tapasztalatok azt mutatják, hogy kezdetben az átlagos legrövidebb úthossz gyorsan csökken, míg a klaszterezettség sokáig magas marad, és csak a
β = 1-hez
közeledve kezd el lecsökkenni.
Összefoglalva tehát a modell magától teljesíti a ritkaság kritériumát, ezen kívül választhatók a paraméterei úgy, hogy az egyszerre teljesítse a kis-világ eektust és a magas klaszterezettséget. Emiatt a modell nagyon hasonló a természetben és társadalomban meg gyeltekhez. Bizonyos mértékben korlátozza a használhatóságát azonban, hogy a kialakuló hálózat túlságosan homogén struktúrájú, emiatt nem skálafüggetlen a viselkedése.
1.3.3. A BarabásiAlbert modell (1999) Átlagos legrövidebb úthossz 1,59
N=50
N=35
3,25
N=20
1.5. ábra. Egy BarabásiAlbert-féle skálafüggetlen hálózat a növekedés különböz® szakaszaiban. Az ábrán az egyes csúcsokat aszerint színeztem, hogy átlagosan hány lépésben érhet® el bel®le a hálózat többi része.
A BarabásiAlbert modellben [15] egy tetsz®leges, kis méret¶ gráfból, úgyneve-
13
zett magból indulunk ki. Ezután minden lépésben növeljük a gráf méretét úgy, hogy hozzáadunk egy csúcsot, amit
m
éllel (m modellparaméter) hozzákötünk a gráf ko-
rábbi csúcsaihoz úgy, hogy a régi csúcsok közül mindegyiket a fokszámával arányos valószín¶séggel választjuk ki. Ennek az algoritmusnak a legfontosabb tulajdonsága, hogy az általa generált gráf fokszámeloszlása
γ = 3
exponens¶ hatványfüggvény-
eloszlást követ. (Kisebb módosításokkal [16, 17] a csúcshoz kötés valószín¶ségén elérhet® ett®l eltér® paraméter is.) További vizsgálódások azt mutatják, hogy a kialakuló gráf faszer¶, er®sen hierarchikus struktúrát mutat, ahol az öregebb csúcsok hubokként, vagyis magas fokszámú, központi elemekként funkcionálnak. Ezen hierarchikus, fa struktúrának az egyik fontos következménye, hogy az ilyen gráfok rendelkeznek a kis-világ tulajdonsággal. Az átlagos legrövidebb úthossz a modellben :
hli ∝
ln N ln ln N
A fa struktúrának másik fontos következménye azonban az, hogy a Barabási Albert modell klaszterezettsége elmarad a valós hálózatokban meg gyeltekt®l, és pl.
m=2
esetén
N −3/4 -nel
arányos. A fenti modell két szempontból fontos mérföldk®
a hálózatkutatásban. Az egyik, hogy a vizsgált gráf tulajdonságait a kialakulásának leírásával próbálja megmagyarázni, ami egy mer®ben új koncepció a WattsStrogatz, vagy az Erd®sRényi modell után. A másik a preferenciális kapcsolódás elve, ami a skálafüggetlen viselkedés megjelenéséhez vezetett, és egyúttal egy lehetséges magyarázata a természetben oly sok helyen felbukkanó skálafüggetlen eloszlásnak. Hiányossága azonban, hogy nem ad kielégít® magyarázatot a valós hálózatok magas klaszterezettségére.
14
2. fejezet
Csoportkeresési eljárások
A valós hálózatoknak egy fontos tulajdonsága, hogy csoport szerkezettel bírnak. Tulajdonképpen az összes valós hálózatban meg gyelhet®k csoportok : sejtcsoportok, szócsokrok, szociális közösségek, törzsek, országok, protein komplexek, falkák és csordák, és még sorolhatnám. A csoportok annyira gyakoriak, hogy a különböz® típusú hálózatok klasztereire különböz® szavaink vannak. Ha azonban általános de níciót kéne adnunk arra, hogy mi is egy csoport, annyit tudnánk csupán mondani, hogy hasonló tulajdonságú elemek halmaza. A milliónyi csúcs és él feldolgozása komoly számítástechnikai kihívást is jelent. Egy ekkora adathalmaz kezelése, felfogása is közel lehetetlen. Az ilyen jelleg¶ problémákat csak adatredukcióval lehet kezelni. Hálózatok esetén ez úgy lehetséges, ha renormáljuk a hálózatot, vagyis az eredeti hálózat alapján elkészítünk egy új hálózatot, amiben minden egyes csúcs az eredeti hálózatban a hasonló tulajdonságú vagy funkciójú csúcsok egy csoportját jelenti. Az ilyen módon nyert hálózat sok tekintetben tükrözi az eredeti hálózat tulajdonságait, ezen kívül jelent®sen megkönnyítheti bizonyos problémák kezelését. Éppen emiatt hálózatkutatáson belül a csoportkeresés központi jelent®séggel bír. Különösen érdekessé teszi a problémát, hogy a hálózatkutatásban nem létezik a csoportokra adható egyetlen, univerzális de níció. Ennek egyik oka, hogy a különböz® valós hálózatokban alkalmazott mérési és adatgy¶jtési technikák eltér®ek lehetnek, ami sokszor abban nyilvánul meg, hogy két csúcs közötti él jelentése modellr®l modellre változhat. Másrészt a valós hálózatokban kialakuló csoportosulások funkciói, a kialakuló kollektív viselkedés bels® és küls® okai is eltér®k lehetnek.
15
Ezek miatt az okok miatt sok de níció és algoritmus jelent meg, amelyek ezt a problémát igyekeznek megoldani. A csoportok megközelítése is változott az id®k folyamán. Kezdetben a kombinatorikus gráfelmélet alapjain f®leg a gráfok optimális particionálásait keresték, vagyis a csúcsokat igyekeztek úgy csoportokba sorolni, hogy egy csúcs ne lehessen két csoportnak egyszerre tagja. Az ilyen partíciók jellemz®en valamilyen tulajdonságot (legkézenfekv®bb a csoportok közötti élek száma) minimalizáltak. Mint arra többek között Palla Gergely és kollégái [1] is rámutattak, a valós hálózatok csoportjai nem ilyenek, hanem jellegükb®l adódóan is átfed®ek. Ha a csúcsokat nem átfed® csoportokba próbáljuk beleer®ltetni, akkor sokszor alapvet® információkat veszítünk az eredeti hálózat szerkezetér®l. Az alábbi fejezet célja ezen fogalmak az átfed®, és a nem átfed® csoportok áttekintése, és összefoglalása. Ebben nagy segítséget jelentett Santo Fortunato 2010-ben megjelent összefoglaló cikke [18]. Az átfed®- és nem-átfed® csoport de níciók külön-külön is három, többé-kevésbé elkülönül® kategóriába sorolhatók. Az els® kategóriába tartozó módszerek egy egzakt, matematikai de níciót választanak a csoport fogalmának, ezek az úgynevezett lokális de níciók, ilyenekkel találkozhatunk a 2.1 alfejezetben. A második, tágabb kategóriába sorolhatók azok a módszerek, amelyeknél a csoportoknak egy egyértelm¶ de níciót adni nehézkes lenne, emiatt a szerz®k a csoportokat megtaláló algoritmussal de niálják az általuk bevezetni kívánt csoport fogalmát. Ezek közül a fontosabb, mai napig használt módszereket mutatom be a nem átfed® csoportokra, illetve az átfed® csoportokra a a 2.2., illetve a a 2.4. fejezetekben. Bár lokális csoport de níciót ad, metodikája miatt mégis ez utóbbi fejezetben ejtek pár szót a CFinder -r®l, mint az ELTE TTK Biológiai Fizika Tanszéken kifejlesztett, és nagyon elterjedt módszerr®l, melyr®l dolgozatom kés®bbi részeiben b®vebben is szót ejtek. A csoportok keresésének harmadik módszere, hogy egy, a csoportfelbontás min®ségét kvantitatívan jellemz®, mérhet® mennyiség optimalizációjával próbáljuk meg elérni a megfelel® csoportfelbontást. Az ilyen mennyiségeket összefoglaló névvel modularitásnak nevezzük. A modularitás fogalmak ®se a Newman-féle modularitás [19], amelyet nem-átfed® csoportok jellemzésére használunk. A fogalomról részletesebben írok a 2.3. alfejezetben. Átfed® csoportok jellemzésére is találtak ki hasonló fogalmakat, és jelen diplomamunka egyik legfontosabb feladata ezeknek a fogalmak-
16
nak a mélyre ható vizsgálata. A szakirodalomban megjelent átfed® modularitás fogalmakat kívánja összefoglalni a 2.5. alfejezet, különös tekintettel a tanszékünk munkatársainak eredményére [20], amelyre a kés®bbiekben Lázár-féle modularitásként fogok hivatkozni. A diplomamunkám egyik legfontosabb célja az ezen modularitást optimalizáló módszerek megalkotása.
2.1. Lokális csoport de níciók A legáltalánosabban három feltételt támasztunk a csoportokkal szemben, és ezek a nagy éls¶r¶ség, az összefügg®ség, illetve a hálózat többi részét®l való viszonylagos függetlenség, vagy másképpen az alacsony kimen® fokszám. Ez a három tulajdonság szorosan összefügg egymással, bár nem következményei egymásnak. Például egy magas éls¶r¶ség¶ részgráf valószín¶leg összefügg® is. Fontos azt is észrevenni, hogy nem szükséges ismernünk a gráf egészét ahhoz, hogy a három tulajdonság teljesültét ellen®rizhessük egy adott részgráfra és környezetére. Ezt gyakran a vizsgált csoportfogalommal szemben támasztott negyedik elvárásban, a lokalitásban fogalmaznak meg. A hatvanas-hetvenes években a szociológiában kialakult lokális csoport de níciók ezt a gondolatmenetet követve próbálnak egy olyan, könnyen megfogható de níciót adni, amely ha a hálózat egy részgráfjára fennáll, akkor teljesíti a fenti három kritériumot. Ezek a de níciók kis hálózatokon jól használhatók, nagy hálózatokon azonban rendszerint túlságosan szigorú feltételeket támasztanak, bár kétségtelen el®nyük, hogy átfed® csoportokat adnak. Ezeket a de níciókat [18] alapján a 2.1. táblázatban foglaltam össze, itt külön csak a klikkekkel foglalkozom, kiemelked® jelent®ségük miatt. Egy szociális hálózatban kiindulhatunk abból, hogy egy baráti körben mindenki ismer mindenkit. Ha felrajzoljuk az ismertségi hálózatot, akkor ez azt jelenti, hogy a csoportok teljes részgráfokat jelentenek. Ezeket a csoportokat röviden klikknek nevezzük. A maximális klikkek (olyan klikkek, amelyek csúcsait nem tartalmazza egy nagyobb klikk) megtalálása NP-teljes probléma, s gyakorlatban azonban valós hálózatokra a ritkaságuk miatt a BornKerbosh algoritmus [21] általában gyorsan eredményt ad. A klikkek legfontosabb tulajdonsága, hogy az éls¶r¶ségük 1. Mivel mindegyik
17
klikk
Maximális teljes részgráf.
n-klikk
Azon csúcsok halmaza, amelyek egymástól vett távolsága legfeljebb
n.
(Egy n-klikk két csúcsa közötti legrövi-
debb útnak tehát nem kell a csoportban futnia.)
n
n-klán
Legfeljebb
n-klub
N átmér®j¶ maximális részgráf.
k-plex
Olyan n méret¶ részgráf, amelyben bármely csúcs legfeljebb
k-core
másik csúccsal nem szomszédos.
Olyan n méret¶ részgráf, amelyben bármely csúcs legalább
LS-set
k
átmér®j¶ n-klikk.
k
másikkal szomszédos.
Olyan részgráf, amelyben bármely csúcs-csoport fokszáma nagyobb a teljes fokszámának felénél, azaz több éllel köt®dik a halmaz többi részéhez, mint a halmazon kívüli csúcsokhoz.
Gyenge csoport
Olyan részgráf, amelynek a bels® fokszáma nagyobb, mint a küls® fokszáma.
Lambda-set
Olyan részgráf, amelyben bármely két csúcs közötti független utak száma magasabb, mint az egyik csúcs és bármely, a lambda-set-en kívüli csúcs közötti független utak száma.
2.1. táblázat. Lokális csoport de níciók összefoglaló táblázata [18] alapján.
csúcs mindegyik másikkal kapcsolatban áll, így a legrövidebb utak hossza, és a klikk átmér®je is 1. Egy klikkben, mint feszített részgráfban a csúcsok teljesen ekvivalensek. Mindemellett a maximális klikkek természetesen át tudnak fedni egymással. Az egyetlen kritérium, aminek a maximális klikkek nem felelnek meg, az a kis kimen® fokszám. Ennél komolyabb probléma, hogy nem jelentenek túl robusztus csoport de níciót : Amennyiben egy maximális klikkb®l például egy mérési hiba miatt egyetlen él hiányzik, az szétesik két különálló maximális klikkre, amelyek egyetlen csúcsban különböznek egymástól. Célravezet®ek tehát az olyan csoportfogalmak, amelyek a klikkek fogalmát úgy lazítják fel, hogy az eredményképpen létrejöv® csoportok kimen® fokszáma csökken, de a kapott csoport mégis klikkszer¶
18
marad.
2.2. Elterjedt algoritmusok nem-átfed® csoportok keresésére A nem-átfed® csoportok keresése mögötti motiváció többnyire az, hogy megadjuk a csúcsok egy olyan osztályozását, amivel valamilyen jól mérhet®, fontos mennyiséget optimalizálunk. Az, hogy mi az optimalizálandó mennyiség, függ a hálózat típusától, és az elvégzend® feladattól. Amennyiben ez a mennyiség a csoportok között futó élek számával, vagy összsúlyával arányos, és a csoportok mérete, vagy száma x, particionálásról beszélünk. Amennyiben az egymáshoz hasonló csúcsokat próbáljuk megtalálni, klaszterezésr®l beszélünk. A hierarchikus klaszterezés célja többnyire egy gráf csoportstruktúrájának (azaz az egymást tartalmazó, egyre nagyobb csoportok) feltérképezése.
2.2.1. Particionálás Elektronikus áramkörök tervezésénél például érdekes lehet az a kérdés, melyik lapkára melyik áramköri elemek kerüljenek ahhoz, hogy a lapkák között minimális számú vezeték fusson. Egy nagyobb program párhuzamosításánál fontos kérdés, hogy lehetséges-e a futó szálakat úgy szétosztani az egyes magok között, hogy minimális legyen közöttük a kommunikáció. Ehhez egy hasonló, bár majdnem ugyanolyan fontos probléma, amikor egy esküv® tervezésénél hogyan ültessük le a vendégeket úgy, hogy az egymást ismer® személyek egy asztalhoz kerüljenek. A fent felsorolt problémák közül az els® kett®nél a csoportok száma el®re adott, és az els® esetben a csoportok közötti élek számát, a második esetben pedig a köztük lév® kommunikáció volumenét (azaz az élek súlyának összegét) szeretnénk minimalizálni. A harmadik példánál x méret¶ csoportok mellett igyekszünk a csoportok között futó élek számát minimalizálni. Az ilyen jelleg¶ problémákat nevezi a számítástudomány összefoglaló néven particionálási problémának. Ezek megoldása többnyire NP-nehéz, de ügyes heurisztikákkal gyakran optimális, vagy közel optimális eredmények érhet®k el polinomiális id® alatt. A legegyszer¶bb feladat, ha egy összefügg® gráfot két részre szeretnénk vágni
19
úgy, hogy a részgráfok közötti élek száma minimális legyen, vagyis egy minimális biszekciót keresünk. A KernighanLin algoritmus [22] ezt a feladatot egy mohó optimalizációval
N 2 log N
komplexitás mellett képes elvégezni. Az algoritmus ite-
ratív módon minden lépésben megkeresi azokat a csúcsokat, amelyeket a másik csoportba helyezve a legnagyobb mértékben képes növelni a biszekció méretéb®l, és a csúcsok bels® fokszámából felállított tness-függvény mértékét. A másik híres megoldása a problémának a spektrális biszekció módszere, melynek során a hálózat Laplace-mátrixának (Lij Fiedler-vektorának
1
= di − Aij ,
ahol
di
fokszám,
Aij
szomszédsági mátrix)
adott csúcson felvett értékének el®jele alapján döntjük el, hogy
az adott csúcs melyik csoportba kerül.
2.2.2. Hierarchikus klaszterezés Vizsgáljuk meg gondolatban egy ország úthálózatát. Egy városon belül több út, vagy utca található, amelyek rendszerint kisebb forgalmat bonyolítanak le. A városokat, vagy városrészeket ezzel szemben kevesebb de forgalmasabb útvonalak, f®utak és autópályák kötik össze. Egy másik idevágó példa az internet, ahol az autonóm rendszereken, vagy akár lokális hálózatokban az egyes eszközöket (routereket, szervereket) több vezeték is összeköti egymással, míg az alhálózatok egymással kevesebb, de egyenként nagyobb sávszélesség¶ vonallal kapcsolódnak egymáshoz. Ford és Fulkerson max- ow min-cut tétele [23] alapján egy ilyen, forgalmon alapuló hálózatban két csomópont között a legsz¶kebb keresztmetszet összkapacitása (minimal cut) forgalom korlátozza az egész hálózat átereszt® képességét (maximal ow). Ilyesformán a legforgalmasabb élek azonosításával egy olyan heurisztikához juthatunk, amivel könnyebben megtalálhatjuk a fontos csoportokat összeköt® éleket. Másképpen megközelítve, amennyiben szisztematikusan mindig a legnagyobb forgalmú éleket távolítjuk el, a hálózat szétesik er®sen összefügg® komponensekre, amelyeket a robosztusság alapú megközelítést követve könnyen azonosíthatunk csoportokként. Az ilyen típusú algoritmusokat divizív hierarchikus klaszterez® algoritmusoknak nevezzük. Divizív, mivel a teljes összefügg® gráfot élek eltávolításával egyre több komponensre bontjuk, és hierarchikus, mivel egy komponens mindig két különböz® komponensre esik szét. Ennek a folyamatnak az ábrázolásai a dendrogramok. Egy ilyen dendrogram látható a 2.1. ábrán.
1a
második legkisebb magnitúdó jú sa játértékhez tartozó sa játvektor
20
2.1. ábra. Zachary karate klub hálózata, és a hozzá tartozó dentogram shortest path
betweenness esetére, bal oldalt az egyes felbontásokhoz tartozó modularitással. Forrás : [24]
Amennyiben nem állnak rendelkezésünkre forgalmi adatok, úgy becsülnünk kell ®ket. A szakirodalom számtalan módszert ismer az élek fontosságának becslésére, melyek alkalmazási területben és algoritmikus komplexitásban is széles spektrumot fednek le. Az egyik leggyakrabban használt ezek közül a GirwanNewman módszer [24], amely az egyes éleken áthaladó legrövidebb utak számát számolja össze. (Az úgynevezett shortest path betweenness -re egy igen gyors -
O(V E)
- komplexitású
algoritmust ad meg [25].) De léteznek mér®számok a csúcsok fontosságának mérésére is. Mivel a divizív hierarchikus algoritmusok minden egyes lépésben újra és újra kiszámítják ezeket a mennyiségeket, ezért a megfelel® mennyiségek alkalmazási területét leginkább a komplexitásuk határozza meg. Mindezzel ellentétes megközelítés az agglomeratív hierarchikus klaszterezés. (Meg kell azt is jegyeznem, hogy hierarchikus klaszterezés alatt sz¶kebb értelemben általában agglomeratív hierarchikus klaszterezést értünk.) Itt el®ször valamilyen metrikus térbe ágyazzuk be a gráf csúcsait, például a szomszédsági mátrix megfelel® vektorainak a hasonlósága alapján. Ezt a hasonlóságot természetesen többfajta mérték is kifejezheti. Ezek után mindig a leghasonlóbb csúcsokat összevonva egyre nagyobb klasztereket építünk, a klaszterek tulajdonságait és távolságát egy megfelel®en kiválasztott módon számolva, míg végül az egymáshoz hasonló összes csoportot összevonva egy nagy klasztert alkot az egész gráf.
21
2.3. A modularitás A hálózatok méretével a hálózatban lehetséges csoportok száma exponenciálisnál is gyorsabb ütemben növekszik. A dendrogramok lehet®séget adnak ezen csoportok közötti összefüggések megismerésére, de felvet®dik a kérdés, hogy hol van az a pont, ahol a klaszterek a hálózatot legjobban jellemz® csoportokat jelentik ? Ezt a kérdést igyekeznek orvosolni az egyes modularitás mennyiségek. A modularitás szó olyan mennyiséget jelent, amely hálózatok csoportfelbontásának min®ségét hivatott kvantitatív módon jellemezni. Ezek közül kiemelkedik a Michelle Girvan és Mark Newman [19] által alkotott fogalom. Foglaljuk össze egy gráfról alkotott ismereteinket
Pij
Pij
a priori valószín¶ségekkel.
megadja, hogy amennyiben az adott gráf topológiáját nem ismerjük, mekkora
annak valószín¶sége, hogy
i és j
csúcsok szomszédosak. Az ezen a priori valószín¶ség
megalkotására létrehozott modellt nullmodellnek nevezzük. A nullmodell alapján a Newmann-féle modularitás alakja irányítatlan hálózatokra a következ® :
QN =
1 X (Aij − Pij )δ(αi , αj ) 2M v ,v i
Ahol
i.,
M
(2.1)
j
jelenti a hálózat éleinek számát,
Aij
a szomszédsági mátrixot,
αi és αj
az
j. csúcsok csoportját, amelyekre δ(αi , αj ) = 1 akkor, ha αi = αj , különben P δ(αi , αj ) = 0. Aij δ(αi , αj ) = dαα tulajdonképpen megadja a csoport bels® fokszáP mát, míg Pij δ(αi , αj ) annak várható értékét a nullmodellben. Végeredményben illetve
QN
tehát egy szám a
[−1, 1]
intervallumban, ami azt fejezi ki, hogy hogyan alakul a
csoportok bels® fokszáma a nullmodellben várható bels® fokszámához képest. Vegyük nullmodellnek azt az esetet, hogy egy él a fokszámával arányos mértékben van összekötve bármely másik csúccsal. Ezt a nullmodellt kon gurációs modellnek hívjuk, mert egyenérték¶ azzal a sokasággal, amit az eredeti gráf éleinek végpontjainak véletlenszer¶ cserélgetésével kapunk. Ekkor
QN
Pij = di dj /2M ,
amit felhasználva
modularitást már kétféleképpen is felírhatjuk :
X 1 X di dj QN = Aij − δ(αi , αj ) = 2M v ,v 2M α i
dαα − 2M
dα 2M
2 ! (2.2)
j
Ahol a második szumma a csúcspárok helyett már az egyes csoportokon fut végig.
dαα ,
az adott csoport bels® fokszámát,
dα 22
a teljes fokszámát jelenti. A mennyisé-
2.2. ábra. Két, húsz csúcsból álló Erd®sRényi gráf valószín¶ségekkel, ahol a CPM (k
= 3)
p = 0,13
és
p = 0,22
élbekötési
csoportokat szürke és fekete jelöli. Mindkét
Erd®sRényi gráf perkolál, viszont a 3-klikkek hálózatán a kritikus élbekötési valószín¶ség
px ≈ 0,16,
ami miatt a jobb oldali ábrán a csúcsok nagy része egy nagy
közösségbe állt össze. Forrás : [29]
get a szerz®k el®ször különböz® betweenness mennyiségekkel kombináltan hierarchikus klaszterezésre mutatták be (a már említett GirwanNewman módszer ben, [24]), majd Newman egy agglomeratív, úgynevezett gyors módszert is bemutatott [26], amely már közvetlenül ezt a mennyiséget optimalizálta. A modularitásnak számos olyan vonzó tulajdonsága van, ami központi jelent®ség¶vé teszi azt a nem-átfed® csoportok keresésében. Azonban fontos megemlíteni a korlátait is. Mint azt Fortunato [27] kiemeli, a modularitás globális optimalizációja elfedi a kis
√ M
nagyságrend¶ (M a hálózat éleinek száma) csoportokat, mivel
ezek a csoportok összeolvadnak egy-egy nagyobb csoportba, és nincsen semmilyen lehet®ség arra, hogy ezeket egymástól szétválasszuk. Ez a valós hálózatoknál, ahol a kis méret¶ csoportok a nagy csoportok mellett nagy számban el®fordulnak, komoly probléma. Egy új paraméter bevezetésével, vagy a képlet módosításával [28] a felbontási határ állíthatóvá válik, de teljesen sosem szüntethet® meg.
23
2.4. A klikk-perkolációs módszer A csoportok közti átfedések fontossága miatt az utóbbi id®ben számos átfed® módszer is született [30, 31, 9, 32], ezek között az egyik els® és talán a legnépszer¶bb a CPM, vagyis a klikk perkolációs módszer, amit a CFinder nev¶ program [33] implementál. A módszer els® lépése az eredeti hálózat alapján a részgráfok) hálózatának felvétele. A
k -klikkek (k
méret¶ teljes
k -klikknek hálózatában minden csúcs egy klikk-
nek felel meg, és két csúcs akkor szomszédos, ha a két klikk egymással. A módszer alapján a hálózat csoportjai a
k−1
k -klikkek
elemben átfed
hálózatának össze-
függ® komponensei. A módszer m¶ködését a 2.2. ábra szemlélteti. A perkoláció, mint azt már említettem, az a jelenség, ahogyan egy nem összefügg® gráf élbekötési valószín¶ségét növelve az hirtelen összefügg®vé válik. A [29] cikk alapján Erd®sRényi hálózatok
k -klikk
hálózatán ez a folyamat ugyanúgy le-
játszódik, mint az eredeti hálózaton, és az élperkolációra kapott 1.1. egyenlettel konzisztensen a perkolációs küszöb :
pc (k) =
1 . [(k − 1)N ]1/(k−1)
(2.3)
Mivel egy csúcs egyszerre több klikknek is eleme lehet, a fent részletezett módszer nyilvánvalóan átfed® csoportokat ad. Mivel a CPM klikk-keresésen alapul, így exponenciális a várt futásideje. Valós hálózatokon ennek ellenére igen gyors, és emiatt nagyon elterjedt algoritmus a hálózatkutatásban. Az elterjedtségének egy másik oka a robusztussága : A módszer által a csoportokra adott de níció lokális, vagyis a hálózat egy részének megváltoztatása nincsen semmilyen hatással a hálózat távoli részeinek csoportfelbontására. A CPM sikerének harmadik oka a paraméterezhet®sége. A módszert kiterjesztették (a [34] és a [35] cikkekben) irányított és súlyozott hálózatokra is, habár a gyengébb élek elhanyagolásával adott a lehet®ség súlyozott hálózatok súlyozatlanná tételére is.
24
2.5. Átfed® modularitás fogalmak 2.5.1. A Newman-féle modularitás általánosításai A Newman-féle modularitás mintájára különböz® szerz®k igyekeztek az átfed® csoportok jellemzésére különböz® modularitás fogalmakat bevezetni. Az egyik legkézenfekv®bb megoldás a Newman-féle modularitás általánosítása az alábbi módon [36] :
1 XX di dj Q∗ = Aij − uαi uαj , 2M α 2M
(2.4)
{i,j}
ahol a korábbiakhoz hasonlóan a csoportokon fut végig.
uαi
di
az
i.
csúcs fokszáma,
2M =
P
i
di ,
és
α
index
a csoporthoz tartozás mértékét fejezi ki, és fuzzy cso-
porttagsági mátrixnak nevezzük. Bevezetve
sij =
P
α
uαi uαj
skalárszorzatot a fenti
képlet az alábbi, egyszer¶bb alakot ölti :
di dj 1 X Q∗ = Aij − sij , 2M 2M
(2.5)
{i,j}
Nepusz és munkatársai [36] bemutattak egy h®kezeléses eljárást optimalizációjára a
uαi
Q∗
közvetlen
mátrix függvényében. Egy fontos megállapításuk, hogy
csak akkor értelmezhet®, ha kikötjük
P
α
uαi = 1
uαi
peremfeltételt. Egy másik lehetsé-
ges módszer, hogy a boolean csoporttagsági mátrix függvényeként határozzuk meg az
uαi
értékeket. Az egyik legkényelmesebb ilyen jelleg¶ megoldás Hua-Wei Shen
nevéhez köthet® [37], aki egyszer¶en az alábbi módon de niálta az
uαi = ahol a
=
Bαi
uαi
mátrixot :
Bαi , qi
(2.6)
boolean csoporttagsági mátrix értéke
1,
ha
i ∈ α,
különben
0. qi =
c c Bi a csúcs úgynevezett degeneráltsága. Ez a módszer tehát úgy szorítja meg a
P
megoldások terét, hogy egy csúcs számára minden lehetséges, a csúcsot tartalmazó csoport egyenrangú. Szintén Shen nevéhez f¶z®dik a módszer, ahol számolja ki a fuzzy tagsági mátrix elemeit [38] :
25
uαi -t
a teljes klikkekb®l kiindulva
uαi ∝
α X Oij j∈α
Ahol
Oij
az
porton belüli,
(i, j)
(i, j)
Oij
Aij
(2.7)
élt tartalmazó maximális klikkek számát, míg
α Oij
az
α
cso-
élt tartalmazó maximális klikkek számát jelenti. A fenti képlet
el®nye, hogy a csoporttagság additív mennyiség lesz, azaz
uα∪β,i = uαi + uαj .
Chen [39] abból indul ki, hogy a csúcs-csoport bels® fokszám fejezi ki leginkább a csoporthoz tartozás mértékét :
uαi ∝ dαi
(2.8)
A tapasztalat azonban azt mutatja (a 3.1.3. fejezetben külön foglalkozom a kérdéssel), hogy az eltér® súlyozásokkal kapott modularitás értékek nem térnek el egymástól jelent®s mértékben.
2.5.2. A Lázár-féle modularitás Egyes szerz®k [31, 30] bizonyos kezdeti, nem átfed® csoportokból kiindulva a csoportok valamilyen fontos tulajdonságának lokális minimumát megtalálva keresnek átfed® csoportokat. Ilyen mennyiség lehet a csoport éls¶r¶sége, vagy a bels® fokszám és a teljes fokszám aránya. A Lázár-féle [20] modularitás egy csoportfelbontás min®ségét úgy jellemzi, hogy a benne található csoportok fontos jelz®it kombinálva ad egy kifejez® mér®számot. A teljes képlet megértéséhez célszer¶ egyesével végigvenni ezeket a mennyiségeket. Ha jellemezni szeretnénk egy csúcs és egy csoport kapcsolatát, azt legkönnyebben két mér®számmal tehetjük meg. Az els® a csúcs-csoport fokszám és a csúcs fokszámának hányadosa. Ez a szám
0
és
1
közötti értékeket vehet fel. Ha értéke
0,
úgy a
csúcs izolált a csoporttól, és biztosak lehetünk benne, hogy nem tagja annak. Ha értéke
1,
úgy minden éle az adott csoportba tart, tehát joggal elvárható a csúcstól,
hogy eleme legyen annak a csoportnak. Lázár és munkatársai ennél egy szorosabb feltételezéssel éltek. Szerintük egy csúcs éleinek els®sorban egy csoportba kell tartania ahhoz, hogy biztonsággal kijelenthessük, hogy az adott csúcs tagja annak a csoportnak. Ezt a feltételt biztosíthatjuk úgy, ha az egyszer¶ hányados helyett az alábbi mennyiséget használjuk :
26
P
vj ∈α
Aij −
P
Aij
vj ∈c /
di
=2
dαi −1 di
A másik ilyen mennyiség a csoport éls¶r¶sége, vagyis
(2.9)
ρα = 2Mα /Nα (Nα − 1).
E két mennyiség szorzata már eléggé jó jellemzését adja egy csoportnak. Közvetlen optimalizációja azonban ebben a formában még nem lehetséges ; ennek az oka, hogy semmi sem zárja ki egy jó modularitású csoport esetén a degenerált csoportok vagyis a közel, vagy teljesen azonos csoportok párhuzamos megjelenését egy hálózatban. Ennek a problémának az orvoslására Lázár és munkatársai egy csoport modularitását az alábbi módon határozta meg :
"
1 X QαL = Nα v ∈α
P
vj ∈c
Aij −
qi
az
i.
vj ∈c /
Aij
di qi
i
ahol
P
#
2Mα , Nα (Nα − 1)
(2.10)
csúcs degeneráltsága, vagyis a csoportfelbontásban hozzá rendelt
csoportok száma,
Nc
pedig a csoport csúcsainak száma.
Jó kérdés, hogy a csoportok modularitásából hogyan keverjük ki a csoportfelbontás modularitását. Az eredeti cikkben a szerz®k a
QαL
mennyiségek egyszer¶ átlagát
javasolják, azaz :
QL = ahol
K
1 X α Q K α L
(2.11)
a csoportok teljes száma. A gyakorlati tapasztalatok azonban azt mu-
tatják, hogy ez félrevezet® eredményre vezet. Ennek a problémának a megoldására a 3.1.2. fejezetben adok megoldást.
27
3. fejezet
A k-klikk perkoláció kritikus pontjának vizsgálata
Amennyiben súlyozott hálózatban szeretnénk csoportokat keresni, azonnal beleütközünk a problémába, hogy a legtöbb csoportkeres® eljárást súlyozatlan hálózatokra találták ki. Ilyenkor az egyik legkézenfekv®bb megközelítés az élek súlyára egy alsó küszöböt bevezetni, azaz egy gondosan kiválasztott küszöbérték alatti súlyú, így kevésbé fontos éleket eldobni, és a megmaradt élekkel pedig egységes súllyal továbbszámolni. Ha a klikk-perkolációs módszert egy elégségesen s¶r¶ hálózaton próbáljuk a fenti módszerrel alkalmazni, egy érdekes dilemmával szembesülünk : Ha túl magas küszöbértéket állítunk be, úgy sok fontos információt dobunk el, ami a gyakorlatban úgy jelentkezik, hogy az eljárás csak néhány, kis méret¶ csoportot fog megtalálni. Amennyiben viszont túl alacsony küszöbértéket alkalmazunk, elégségesen s¶r¶ hálózatban a k-klikkek hálózata összefügg®vé válik, vagyis az összes k-klikk egyetlen CPM csoportot fog alkotni. Mivel a küszöbérték mind a két széls®értéke mellett rossz min®ség¶ csoportfelbontás jelentkezik, az intuíciónk azt súgja, hogy kell léteznie egy optimális küszöbértéknek, ráadásul ennek a küszöbértéknek valamelyest nagyobbnak kell lennie, mint annak a pontnak, ahol a k-klikkek hálózata összefügg®vé válik. Az egyik feladatom az volt, hogy megvizsgáljam, tényleg létezik-e optimális küszöbérték, és ez tényleg a kritikus pont környékén jelentkezik-e. Az alábbi fejezetben tehát ismert valós hálózatokon megvizsgálom, hogy jelentkezik-e bennük a
28
k -klikk
perkoláció jelensége, és
ha igen, a fent ismertetett átfed® modularitás mennyiségek közül néhány segítségével megvizsgálom, hogy a kritikus pont környékén a CPM optimális felbontást ad-e.
3.1. Vizsgálati módszerek 3.1.1. A kritikus pont meghatározása Ahhoz, hogy megállapítsuk, hogy k-klikkek hálózata egy adott alsó küszöbérték mellett perkolál-e, két mennyiséget célszer¶ vizsgálni. Az els® a legnagyobb csoport mérete (NG ) a teljes csoportlefedés méretéhez (NC ) képest ; azt várjuk ugyanis, hogy egy id® után az egész hálózat egyetlen óriás komponensb®l fog állni. Ennek megfelel®en az alábbi mennyiségeket vizsgáltam :
SG =
NG , N
illetve SC =
NC , N
(3.1)
A másik lehet®ség a csoportméretek szórásának vizsgálata : A perkolációs átalakulás alatt a csoportméret-eloszlás skálafüggetlen, így szórása a végtelenbe tart. A csoportméret-eloszlás szórása helyett az ún. módosított szórását szokás vizsgálni, azaz a csoportméretek gigantikus komponens nélküli szórását. Ez a mennyiség a maximumát a gigantikus komponens megjelenésekor veszi fel, így kiválóan nyomon követhet® rajta a hálózat fázisátalakulása. Ezt a mennyiséget történeti okokból szuszceptibilitásnak szokás nevezni, és emiatt a jele
χ.
χ = hNα2 iα6=αG − hNα iα 6= αG 2 ,
(3.2)
3.1.2. A Lázár-féle modularitás vizsgálata Amennyiben alkalmazni szeretnénk a Lázár-féle modularitást a CFinder csoportfelbontások min®ségének jellemzésére, újabb problémákba ütközünk. Ezek a problémák az alábbiak :
Mi történik azokkal a csúcsokkal, amelyek nem szerepelnek egyetlen csoportban sem ? Milyen súlyozást használjunk a csoportok modularitásának kiszámításához ?
29
Hogyan vegyük gyelembe az élsúlyokat ?
Egy hálózat csoportfelbontásától azt várjuk, hogy az eredeti hálózat topológiai információit tömöríti. Ha a modularitás egy valós szám
[−1, 1]
halmazon, akkor azt
várjuk, hogy egyfajta korrelációs együtthatóhoz hasonlóan a magnitúdója arányos lesz a hálózatról szolgáltatott információ mennyiségével, illetve arányos lesz azzal is, hogy ez az információ mennyire helytálló. Pontosabban amennyiben az élek a csoportokon belül futnak, úgy a csoportok alapján a topológia jól becsülhet®, és a modularitás el®jele is pozitív. Amennyiben az élek a csoportok között futnak, a csoportfelbontás inkább dezinformációt hordoz, emiatt azt várjuk, hogy a modularitás el®jele negatív lesz. A Lázár-féle modularitással az eredeti de níció szerint, a csoportok modularitásának egyszer¶ átlagolásával az a probléma, hogy az els® kívánságunkat nem teljesíti. Extrém esetben például elképzelhet®, hogy a hálózatban egyetlen klikket ismerünk fel csoportként. Ekkor a modularitásra egy magas értéket kapunk, annak ellenére, hogy a gyakorlatban ez a felbontás nem sok információt hordoz az eredeti hálózatról. Ezt az problémát kiküszöbölhetjük azzal, ha az egyszer¶ átlagolás helyett egy olyan súlyozott átlagot alkalmazunk, ami kifejezi az egyes csoportok méretét az egész hálózathoz képest. Az elemzéseimben tehát a Lázár-féle modularitás (2.11. képlet) módosított alakját alkalmaztam :
ˆL = Q
X
−1 vi ∈α qi
P
N
α ahol
qi vi
csúcs csoportjainak száma,
QαL ,
−1 az vi ∈α qi
P
(3.3)
α
csoport redukált mérete
(azaz az egyes csúcsokból a csoportokba jutó töredék részek összege),
N
pedig a
szokásos módon a teljes gráf mérete. A fenti kifejezés el®nye, hogy ez már arányos a csoportfelbontás által lefedett csúcsok számával, ezen kívül gyelembe veszi, hogy a nagyobb csoportok nagyobb mértékben járuljanak hozzá a teljes modularitáshoz. Amennyiben a fenti módon számoljuk a modularitást, úgy a nem lefedett csúcsok kérdése okafogyottá válik ; ezek a csúcsok úgy viselkednek, mintha egy
0
modulari-
tású - vagyis semmilyen információt nem hordozó - csoport elemei lennének. Az egyetlen megmaradt kérdés, hogy hogyan vegyük gyelembe az élsúlyokat. Bár
dαi /di
mennyiségekben a fokszámokat gond nélkül kicserélhetnénk az élsúlyok
30
összegére, az éls¶r¶ségnek nem egyértelm¶ az ilyen irányú általánosítása. Az egyetlen lehetséges módszer tehát, hogy a Lázár-féle átfed® modularitást is a küszöbérték segítségével súlyozatlanná tett hálózaton vizsgáljuk.
3.1.3. A Shen- és Chen-féle modularitás mérése A 2.5.1. alfejezetben több átfed® modularitás mennyiséget is ismertettem, amelyek a Newman-féle modularitás általánosításai átfed® csoportokra. Ezeknek közös vonásuk, hogy egyformán a 2.4. egyenletben felírt alakban lehet ®ket kiszámítani, csupán az
uαi
fuzzy csoporttagsági mátrix kiszámításában térnek el egymástól. Az
elemzéseim során mivel nagyon hasonló eredményeket adtak ezek közül kett®t implementáltam : Shen els® módszerét (2.8. képlet, képlet,
QS ), illetve Chen módszerét (2.6.
QC ).
Ezeknél a mennyiségeknél a Lázár-féle modularitással kapcsolatos problémák nem merültek föl, hiszen ezek a csoportokra nézve önmagukban is additív mennyiségek. Ezen kívül magukban rejtik a lehet®séget, hogy a súlyozott hálózatokra az alábbi módon általánosítsuk ®ket :
1 XX Wi Wj ˆ Q∗ = wij − uαi uαj , 2W c 2W
(3.4)
{i,j}
ahol
wij
az
i és j csúcs között futó élek súlyát jelenti, Wi =
P
j
wij
és
W =
P
i
Wi .
Ez azt jelenti, hogy a súlyozatlanná tett hálózaton nyert csoportfelbontást az eredeti hálózaton is alkalmazhatjuk.
3.1.4. A Pearson-korreláció, mint mérték A 2.1. fejezetben utaltam arra, hogy létezik olyan megközelítés, ami szerint a csoport fogalmához eljuthatunk úgy is, hogy a klikk fogalmát próbáljuk általánosítani olyan módon, hogy közel klikkszer¶ objektumokat kapjunk. Ennek megfelel®en érdemes vizsgálni azt, hogy egy lefedés csoportjai mennyire klikkszer¶ek : ez az alább ismertetend® módszer célja.
Bαj
csoporttagsági mátrix alapján készítsük el
31
A˜ij
mátrixot az alábbi módon :
( A˜ij =
1 ha ∃α → Bαi Bαj = 1
(3.5)
0 ha ∀α → Bαi Bαj = 0
Amennyiben meg akarjuk vizsgálni, hogy mennyire teljesül az az állítás, hogy csoportfelbontás elemei klikkek, érdemes
A˜ij
Aij ,
Bαi
és a fenti módszerrel meghatározott
mátrix hasonlóságát vizsgálni, amire az egyik legkézenfekv®bb a két mátrix nem-
diagonális elemeib®l képzett vektorok Pearson-féle korrelációja.
2 2 szórása hxi i − hxi i
xi
boolean adatsor
= hxi i(1 − hxi i), amivel kifejezhet® a két bináris mátrix Pearson-
korrelációja :
hAij A˜ij i − hAij ihA˜ij i Cp = q , hAij ih1 − Aij ihA˜ij ih1 − A˜ij i ahol A
h·i
Cp
átlagolás az
i 6= j
(3.6)
rendezetlen párokra értend®.
pozitív értékei azt fejezik ki, hogy a csoportfelbontás jó jóslatot ad arra,
hogy az eredeti hálózatban hol vannak élek. Határesetben ha
Cp = 1,
úgy két csúcs
között pontosan akkor van él, amennyiben van olyan csoport, amelynek mindkét csúcs eleme. Ezt a határesetet azonban csak a maximális klikkek alkotta lefedés teljesíti. A fenti mennyiséghez hasonló fogalom már létezik az irodalomban [18], ez a
teljesítmény (performance). A teljesítményt eredetileg nem-átfed® csoportokra értelmezték, de triviális az általánosítása átfed® csoportokra is. A fenti jelöléssel élve a teljesítmény de níciója :
P = hAij A˜ij i + h(1 − Aij )(1 − A˜ij )i A teljesítmény
[0, 1]
(3.7)
intervallumon veszi fel az értékét, emiatt eredeti formájá-
ban nem alkalmas arra, hogy kifejezze egy csoportfelbontás esetleges dezinformatív jellegét. Az élek, és az élek hiánya ugyanolyan súllyal esik latba. Emiatt például egy csoportok nélküli csoportfelbontás teljesítménye
ρ azonos egy olyan csoportfelbontás
teljesítményével, amely az eredeti hálózatnál kétszer több élt jósol, de tartalmazza az összes élt. A teljesítmény fogalmát persze lehetne úgy általánosítani, hogy az éleket, és a nem létez® éleket különböz® súllyal vesszük gyelembe, de ekkor a két súly aránya a mérték egy paraméterévé válna, ami megnehezíti a mérték alkalmazását.
32
A Pearson-korreláció kiszámítása számítástechnikai problémába ütközhet, ha jelen van a hálózat méretével összemérhet® méret¶ csoport. Ekkor ugyanis
A˜ij
nem
lesz többet ritka mátrix. A CPM módszerrel a perkoláció miatt az óriás komponens jó eséllyel meg is jelenik. Ett®l a problémától a számításaim során úgy szabadultam meg, hogy ha egy csoport egy bizonyos méret fölé került (praktikusan ezres nagyságrendbe), akkor azt gyelmen kívül hagytam.
3.1.5. A Kendall-féle rang-korreláció, mint mérték Egy másik lehetséges megközelítése a lefedések jellemzésének a következ®. Súlyozott hálózatban a súlyok legtöbbször valamilyen formában az élek fontosságát fejezik ki : amennyiben egy élhez rendelt súly nagyobb, úgy az rendszerint fontosabb is az adott hálózatban. Amennyiben nem ismert az élek súlya, csak a hálózat csoportfelbontása, úgy a csoportfelbontás alapján hasonló becslést tehetünk. Amennyiben több csoport is létezik, amelynek két kiválasztott csúcs eleme, úgy azt gondoljuk, ahogy aközött a két csúcs között fontosabb él húzódik. A súlymátrix is, és a tagsági mátrix is meghatároz tehát egy-egy gyenge rendezést az éleken, amelyeket összehasonlítása információt szolgáltat a hálózat min®ségér®l. A csoportfelbontás alapján tehát az élek súlyaira adható becslés :
˜ ij = W
X
Bαi Bαj
(3.8)
α A fenti
˜ ij W
mennyiséget ez után összehasonlíthatjuk az eredeti hálózat
Wij
súlymátrixával. Ezt több módon is megtehetjük, például a Pearson-féle, vagy a Spearman-féle rang korrelációval. A méréseim során én a Kendall-féle
τB
rang-
korrelációs együtthatót számítottam ki [45]. Komoly probléma ezzel a módszerrel azonban, hogy magában foglalja a csúcspárokból alkotott párok enumerációját, ami miatt a naiv implementáció m¶veletigénye
O(N 4 )
zik olyan algoritmus [46], amivel ez lecsökkenthet®
nagyságrendbe esik. Bár léte-
O(N 2 ln N )
nagyságrendre, én
a futtatásaim során véletlen (milliós nagyságrend¶) mintavételezéssel mértem ezt a mennyiséget.
33
3.1.6. Az adatfeldolgozás A hálózatokat az eredmények ellen®rizhet®sége és összehasonlíthatósága miatt azonos formába kellett hoznom. A különböz® mértékeket octave szkriptekkel számítottam ki, emiatt célszer¶ volt az egyes hálózatok eredeti címkéit egymás után következ®, pozitív egész számokra cserélni. Egy másik probléma, hogy a különböz® típusú hálózatokban az élsúlyok értelme, és éppen emiatt az eloszlásuk is különböz®. Kirívó példák erre a kés®bb ismertetend® vetített hálózatok, ahol a kisebb élsúlyoknál az eloszlás diszkrét. Például az egyik vizsgált hálózatban (cond-mat ) a
0,5
súlyú élek teszik ki az összes él
8,7%-át,
míg az er®sebb élsúlyokból már csak 1-1 fordul el®. A problémát úgy próbáltam áthidalni, hogy az egyes hálózatok éleit egyenletes eloszlásúra képeztem le az alábbi módszerrel :
1. Az éleket egy tömbbe rendeztem, véletlenszer¶en permutáltam ®ket, majd ismét rendeztem ®ket, ezúttal a súlyok szerint növekv® sorrendbe. Erre azért volt szükség, hogy a csúcsok címkéib®l adódó esetleges sorrendt®l, és így az adatgy¶jtés módszeréb®l származó esetleges torzításoktól megszabaduljak. 2. Legeneráltam az élek számának megfelel® számú véletlen számot egyenletes eloszlás szerint, majd ezeket is növekv® sorrendbe rendeztem. 3. Az els® tömbben található élek súlyait kicseréltem a második tömb megfelel® helyén található véletlen számmal.
Ilyen módon tehát fontosság szerint rendeztem az éleket : A fontosabb, nagyobb súlyú élekhez magasabb, a kevésbé fontos élekhez egy kis számot rendeltem 0 és 1 között úgy, hogy az eredeti hálózatban azonos súlyú élek sorrendje egymáshoz képest véletlenszer¶, az élsúlyok összességében pedig uniform eloszlást követnek. A vizsgálat során minden
f
küszöbérték mellett eldobtam azokat az éleket, ame-
lyeknél ez, az újonnan kiszámított prioritás alacsonyabb. Az így kapott, immár súlyozatlanként kezelhet® hálózatnak CFinder segítségével megkerestem a CPM csoportjait különböz®
k
paraméterek mellett. Ha megjelent óriás komponens, azt többnyire
eldobtam a csoportfelbontásból (Az óriás komponens egy gyakorlatilag így
0
0 éls¶r¶ség¶,
információt hordozó csoport a hálózatban, ami méretei miatt mégis olyan tor-
zítást ad, ami miatt a legtöbb mennyiség értelmezhetetlen lesz.) Végül értelmeztem
34
a csoportfelbontásokon a korábbi fejezetekben részletezett, illetve a 3.1. táblázatban összefoglalt mennyiségeket. A súlyozatlan hálózatokon értelmezett mennyiségeknél szintén a küszöbözött hálózatot alkalmaztam, egyébként pedig az eredeti, súlyozott hálózatot. Az alábbiakban szerepl® (3.1., A 3.3., 3.4., 3.2., 3.5., 3.6., 3.7. és 3.8.) ábrákon
f
értékét
∆f = 0,005-ös
lépésekben változtattam. Az ábrán szerepl® szimbólumok
ritkábban szerepelnek, csak a görbék megkülönböztethet®ségét szolgálják. Az ábrákban felhasznált adatokat a [2] cikkünkben is felhasználtuk, emiatt hasonlítanak a cikkbeli ábrákra.
SG
Az óriás komponensben szerepl® csúcsok száma.
SC
A csoportfelbontásban szerepl® csúcsok száma.
QL ˆL Q
A Lázár-féle modularitás az eredeti, 2.11. képlet szerint.
QS
Az eredeti Shen-féle fuzzy modularitás mérték a 2.6. és
A Lázár-féle modularitás az új, 3.3. képlet szerint.
2.4. képletek szerint.
QC
Az eredeti Chen-féle fuzzy modularitás mérték a 2.8. és 2.4. képletek szerint.
ˆS Q
A Shen-féle fuzzy modularitás mérték súlyozott hálózatokra a 2.6. és 3.4. képletek szerint.
ˆC Q
A Chen-féle fuzzy modularitás mérték súlyozott hálózatokra a 2.8. és 3.4. képletek szerint.
Cp
A Pearson-féle korrelációs mérték súlyozatlan hálózatokra a 3.6. képlet szerint.
τB
A Kendall-féle
τB
korrelációs mérték súlyozott hálóza-
tokra a 3.1.5. (A nagy futásid® miatt csak
k=3
CPM
csoportokra vizsgáltam.) fejezet szerint. 3.1. táblázat. A különböz® hálózatok CPM csoportjain vizsgált mennyiségek.
35
3.2. Eredmények 3.2.1. Mobiltelefon hívások hálózata A mobile hálózat adatait egy hazai mobiltelefonszolgáltató bocsájtotta a tanszék rendelkezésére egy korábbi elemzéshez, természetesen anonim formában, vagyis az adatok alapján nem lehet beazonosítani az egyes felhasználókat. Az adatbázisban az egyes csúcsok az egyes ügyfeleket azonosítják, és rendelkezésünkre állt az ügyfelek közötti telefonbeszélgetések összesített id®tartama egy hónapon belül, amivel a hálózat éleit súlyoztuk. Az eredeti hálózat 6,4 millió csúcsot és összesen 1,58 millió irányítatlan élt tartalmaz. Ennek az adatbázisnak a feldolgozása a CFinderrel sajnos (eddig) nem volt lehetséges, ezért mintavételeznem kellett a hálózatot, hogy egy kisebb, jobban kezelhet® adathalmazt kapjak. A mintavételezett hálózatban egy véletlenszer¶en kiválasztott csúcsból kiindulva breath- rst search (el®ször a csúcs szomszédait, majd a szomszédok listája alapján a másodszomszédait, stb. végiglátogatva) enumerációval gy¶jtöttem ki az els® 100.000 legközelebbi szomszédot. Az így nyert hálózat 273.146 csúcsot tartalmazott, de az
−5 éls¶r¶sége jóval magasabb (2,73 · 10 a
3,86 · 10−8 -hoz
képest). Ennek az oka, hogy
a mintavételezett hálózat a hubokat nagyobb valószín¶séggel tartalmazza, mint a periferiális csúcsokat. Azonban ez klikk-perkolációs csoportok lokális jellege miatt ez elvileg nem okozna különösebb problémát. Azonban ebben a hálózatban nem jelent meg gigantikus komponens. Az ok az, hogy ez a hálózat még így is túl ritka, így a klaszterezettsége is alacsony. Ez abban jelentkezik, hogy a csoportfelbontás még
5,9%-ára
k=3
esetben vett
f = 0 küszöbérték mellett is csupán a teljes hálózat méretének
terjed ki.
3.2.2. Kollaborációs hálózatok A cond-mat, astro-ph, hep-th hálózatokat az Arxiv azonos nev¶ kategóriájában 1995 és 1999 között publikált cikkek alapján állította el® Newman [40, 41, 42]. A vizsgált hálózatok a cikkek és a szerz®k alkotta bipartit
1
gráfból az úgynevezett
Newman-féle vetítés módszerével álltak el®, amit az alábbi képletben foglalhatunk össze :
1 Lsd.
függelék A.1. fejezete.
36
Wij0 =
X k
Ahol az z®ket,
k
Aik
A A P ik jk l Alk − 1
(3.9)
az eredeti bipartit hálózat szomszédsági mátrixa, vagyis
az egyes cikkeket indexeli.
Aik = 1
i
a szer-
amennyiben az adott kutató szerz®je
0 az adott cikknek. Wij az eredményként kapott egymódosú hálózat élinek súlya. A vizsgált hálózatok sorra 30.732, 16.046 és 7.610 csúcsot tartalmaznak, éls¶r¶ségük sorra
2,88 · 10−4 , 9,42 · 10−4
A hep-th hálózatban
és
k =3
5,45 · 10−4 . esetben már rögtön
gigantikus komponens, de ez csak a hálózat
f ≈0
küszöbértéknél kialakul
5%-ra terjed ki, és a küszöbérték emelé-
sével azonnal szertefoszlik. Emiatt ezen a hálózaton nem gyelhetjük meg a keresett jelenséget.
k = 4 esetben a hep-th
hálózatban már le sem játszódik a fázisátalakulás,
mivel a 2.3. egyenlet értelmében a kritikus pontnak még alacsonyabb küszöbérték mellett kellene jelentkeznie. A kollaborációs hálózatokra jellemz® perkolációs átalakulás talán a legjobban a 3.1. a.) ábrán látszódik. A kritikus pontban a szuszceptibilitás megugrik, és kialakul egy óriás komponens, de az óriás komponens nem olvasztja magába a hálózat többi részét, hanem attól függetlenül növekszik. Ennek a tudományos világ megosztottsága a f® oka. A csoportok egymástól függetlenül m¶ködnek, a publikációk jelent®s része egyetlen kutatócsoport tagjaitól származik. Amennyiben mégis van együttm¶ködés a kutatócsoportok között, azok egyszeriek, és ilyenkor jellemz®en minden csoportból egy-egy személy vesz részt bennük. (Például az astro-ph hálózatban az élek leggyengébb
83%-a
megegyezik a Newman-féle súlyozással a
0,49
súlyú,
vagy gyengébb élekkel, amelyek több szerz® alkalmi együttm¶ködését jelentik.) Éppen emiatt, bár a vizsgált modularitás mennyiségek többségénél valamiféle csúcs jelentkezik a kritikus pont környékén, ez a csúcs nem mindig elég határozott. Különösen igaz ez a Lázár-féle módosított illetve a Chen- és a Shen-féle modularitásokra. A Chen- és Shen-féle modularitások egymáshoz nagyon hasonlóan viselkednek : fontosabb befolyásoló tényez®nek mutatkozik, hogy súlyozott, vagy súlyozatlan hálózaton értelmezzük ®ket.
f = 0-ban magas értékhez tartanak, mivel a hálózatnak
a jelent®s része ekkor még nem olvad bele az óriás komponensbe, illetve
0-ba
f = 0-ban
tartanak, mert a hálózatból elt¶nnek a csoportok. Az eredeti Lázár-féle modu-
laritásban nem jelentkezik semmiféle csúcs, minden esetben monoton növekszik. Ennek az az oka, hogy a küszöbértéket emelve sorra t¶nnek el a hálózatból a
37
k -klikkek,
míg végül csak néhány klikk marad. Ezeknek a Lázár-féle modularitása közel
1 lesz,
hiszen minden megmaradt él ezekben a klikkekben marad, nincsenek átfedések, és az éls¶r¶ség is közel
1 lesz, tehát ezen csoportok modularitásának egyszer¶ átlaga is
magas lesz. A korrelációs mértékekben a kritikus ponttól csökkentve a küszöbsúlyt egy ugrás mutatkozik. Az ugrás a mérés hibájából adódik, ebben a pontban ugyanis ahogyan megjelenik az óriás komponens, kivesszük a csoportfelbontásból. Fontos továbbá megjegyezni, hogy a 2.3. képlettel összhangban a magasabb
k
értékhez tartozó CPM csoportoknak egyre alacsonyabban van a kritikus pontja. Ennek az egyik következménye, hogy
k > 4 esetén már az itt vizsgált hálózatok sem
perkolálnak.
38
a) 25000 20000 S 15000 10000
75 60
SC SG 𝜒
45
5000 b)
15 0,18 0,15 0,12 0,09 QL 0,06 0,03
0,8 0,7
QL
0,6 0,5
QL QL
^
^
0,4 c)
Q
d)
0,35 0,28 0,21 0,14 0,07 0,00 0,5
QS QS QC QC ^
^
Cp 𝜏B
0.022 0.019 0.016 0.013 𝜏B 0.010 0,007
0,4 Cp
𝜒
30
0,3 0,2
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 f 3.1. ábra. A cond-mat hálózat CPM csoportfelbontásának mértékei
k = 3 mellett, f
alsó súlyküszöb függvényében. A szürke vonal a kritikus pont becsült helyét jelöli. a.) A perkolációs átalakulás
f ≈ 0,79
alsó küszöbérték mellett jelentkezik, bár a
hálózat nem olvad teljesen bele az óriás komponensbe. b.) A Lázár-féle modularitás eredeti alakjában monoton növekszik, a módosított alakja lassan növekszik, majd a kritikus pont el®tt letörik. c.) A Shen- és Chen-féle de níció nagyon hasonlóak. Mint a súlyozott, mint a súlyozatlan hálózaton értelmezett verziókban letörés mutatkozik a kritikus pont el®tt, bár az el®bbi monoton csökken, az utóbbi növekszik a letörés el®tt. d.) A korrelációs mértékekben határozott csúcs látszik a kritikus pont fölött.
39
a) 12500
SC SG 𝜒
10000 S
b)
QL
c)
7500
80 60
5000
40
2500
20
0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2
𝜒
0,18 0,15 0,12 0,09 QL 0,06 0,03
QL QL
^
^
QS QS QC QC
0,4
^
0,3 Q
100
^
0,2 0,1
d)
Cp
0,6 0,5 0,4 0,3 0,2 0,1
Cp
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 f 3.2. ábra. Az astro-ph hálózat CPM csoportfelbontásának mértékei
f
k=4
mellett,
alsó súlyküszöb függvényében. A szürke vonal a kritikus pont becsült helyét je-
löli. a.) A perkolációs átalakulás jelentkezik, mint a cond-mat
f ≈ 0,6
k=3
alsó küszöbérték mellett talán élesebben
esetben, de a hálózat itt sem olvad bele az óriás
komponensbe. b-c.) A Lázár-féle modularitás eredeti és módosított alakja, valamint a fuzzy mértékek is nagyon hasonlóan haladnak a 3.1. ábrán látottakhoz. d.) A Pearson-korrelációs mértéknek maximuma van a kritikus pont fölött, de a kritikus pontból csökkentve
f -t
ismét ugrik egyet. Ennek az oka az, hogy a mérése során itt
kivesszük az óriás komponenst a csoportfelbontásból.
40
a) 25000
SC SG 𝜒
20000 S 15000 10000 5000 b)
QL
c)
Q
d)
Cp
0,9 0,8 0,7 0,6 0,5 0,4 0,3
180 150 120 90 60 30
𝜒
0,18 0,15 0,12 0,09 QL 0,06 0,03 ^
QL QL ^
0,6 0,5 0,4 0,3 0,2 0,1
QS QS QC QC ^
^
0,6 0,5 0,4 0,3 0,2 0,1
Cp
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 f 3.3. ábra. A cond-mat hálózat CPM csoportfelbontásának mértékei
f
k=4
mellett,
alsó súlyküszöb függvényében. A szürke vonal a kritikus pont becsült helyét jelöli
f ≈ 0,08
helyen. a.) A 2.3 egyenlettel összhangban itt jóval korábbi küszöbértéknél
jelentkezik a perkoláció, mint
k = 3
esetben. Emiatt az óriás komponens alig éri
el az egész, csoportok által lefedett hálózat harmadát. A szuszceptibilitás csúcsa nem olyan éles, mint korábban. b.) A Lázár-féle mennyiségek a korábbiaknak megfelel®en viselkednek. c.) A fuzzy mennyiségeknek a kritikus ponton, illetve fölötte van enyhe csúcsa. d.) A Pearson korrelációs mértéknek is maximuma mutatkozik, és nagyjából megfelel
Qc
és
QS
maximumának.
41
a) 15000
20
12000
16
S
9000 6000 3000
b)
QL
c)
Q
d)
Cp
0,8 0,7 0,6 0,5 0,4 0,3 0,20 0,16 0,12 0,08 0,04 0,00 0,55 0,50 0,45 0,40 0,35 0,30
12
SC SG 𝜒
𝜒
8 4 0,18 0,15 0,12 0,09 QL 0,06 0,03
QL QL
^
^
QS QS QC QC ^
^
0,024
Cp 𝜏B
0,020 0,016 𝜏 B 0,012 0,008
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 f 3.4. ábra. Az astro-ph hálózat CPM csoportfelbontásának mértékei
f
k=3
mellett,
alsó súlyküszöb függvényében. A szürke vonal a kritikus pont becsült helyét jelöli
f ≈ 0,87
helyen. a.) A szuszceptibilitásban nem jelentkezik határozott csúcs, ami
arról árulkodik, hogy ebben a hálózatban a gigantikus komponens megjelenése nem befolyásolja jelent®sen a hálózat többi részét. A maradék hálózat itt sem t¶nik el. b.)
ˆ L -nek Q
enyhe csúcsa gyelhet® meg a kritikus pont el®tt. c.) töréspont látszik a
kritikus pont el®tt, hasonlóan a 3.1. és a 3.2. ábrákhoz. d.) A korrelációs mértékekben határozott csúcs jelentkezik.
42
3.2.3. Szóasszociációs hálózat A szerz®k a [43] hálózat adatait egy internetes honlap segítségével gy¶jtötték. A honlapon minden alkalommal egy el®zetesen elkészített adatbázisból nyert szó szerepelt, ami mellé a felhasználóknak kellett egy olyan szót írniuk, amire az adott szóból asszociáltak. A tesztet több, mint egymilliószor végezték el, és a válaszok több, mint
75%-át
ugyanattól a hatezer felhasználó származik. A hálózat éleit az
asszociáció gyakorisága alapján súlyozták. Az eredeti hálózat irányított volt, amit én az adott szópárhoz tartozó élek összeadásával tettem irányítatlanná. A hálózat 10.614 csúcsot és 63.789 élt tartalmaz, így éls¶r¶sége
1,13 · 10−3 .
A perkolációs átalakulás a legszebben ezen a hálózaton látszik. A 3.5. és a 3.6. a.) ábráján nyomon követhetjük, ahogyan az alsó köszöbértéket
f = 1-r®l
folyama-
tosan csökkentve egyre növekszik a CPM csoportok által lefedett hálózat mérete, majd
λ ≈ 0,72 érték mellett lejátszódik a perkolációs átalakulás, ami egy óriás kom-
ponens kialakulásához vezet, miközben a szuszceptibilitásnak éles maximuma van. Tovább csökkentve az alsó küszöbértéket az óriás komponens magába olvasztja az egész hálózatot. A b-d.) ábrákon egyértelm¶en látszik, hogy az eredeti Lázár-féle modularitás kivételével a vizsgált mértékek mindegyikében csúcs mutatkozik a kritikus pont fölött
k
mindkét értékére, habár ezek a maximumok nem ugyanannál a
súlyküszöbnél vannak.
43
a) 5000
1000
4000 S
3000 2000 1000
b)
QL
c)
Q
d)
0,60 0,45 0,30 0,15 0,00 -0,15 0,18 0,15 0,12 0,09 0,06 0,03
600
SC SG 𝜒
0,2
𝜒
400 200 0,03 0,02 0,01 QL ^
QL QL ^
0,00
QS QS QC QC ^
^
0,4 0,3
Cp
800
0,003 0,002
Cp 𝜏B
0,001
0,1
𝜏B
0,000
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 f 3.5. ábra. A szóasszociációs hálózat CPM csoportfelbontásának mértékei mellett,
f
k = 3
alsó súlyküszöb függvényében. A szürke vonal a kritikus pont becsült
helyét jelöli,
f ≈ 0,72 mellett. a.) A perkolációs átalakulás nagyon szépen látszik, az
óriás komponens kiterjed az egész hálózatra b.) A Lázár-féle modularitás módosított
ˆ L ) maximuma van a kritikus pont fölött. c.) Az összes fuzzy modularitás alakjának (Q mérték hasonlóan viselkedik, és maximuma van közvetlenül a kritikus pontnál. d.) Mindkét korrelációs mértéknek a
ˆ L -hez Q
hasonló maximuma jelentkezik a kritikus
pont felett.
44
a) 4000
SC SG 𝜒
3200 S
b)
QL
c)
2400
750 600 450
1600
300
800
150
0,4 0,3 0,2 0,1 0,0 -0,1 -0,2
𝜒
0,000 -0,007 -0,014 Q L -0,021
QL QL
^
^
-0,028 QS QS QC QC
0,25
^
0,20 Q
0,15
^
0,10 0,05 d)
Cp
0,35 0,30 0,25 0,20 0,15 0,10 0,05
Cp
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 f 3.6. ábra. A szóasszociációs hálózat CPM csoportfelbontásának mértékei lett,
f
k = 4 mel-
alsó súlyküszöb függvényében. A szürke vonal a kritikus pont becsült helyét
f ≈ 0,32. a.) A perkolációs átalakulás alsó küszöbérték mellett rendesen lejátˆ L modularitásnak messze a kritikus pont fölött van maximuma. c.) Az szódik. b.) A Q jelöli,
összes fuzzy modularitás mértéknek maximuma van közvetlenül a kritikus pontnál. d.) A Pearson-korrelációnak parabola alakú maximuma van a kritikus pont fölött. Amint megjelenik az óriás komponens, gyelmen kívül hagyjuk, ennek köszönhet® az ugrás a kritikus pont alatt.
45
3.2.4. Egyetemisták online szociális hálózata Az unical hálózat a University of California diákjainak fenntartott webes felületén keresztül egymásnak küldött üzenetek alapján készült [44]. Az adatbázis 1899 felhasználót tartalmaz, és bár több típusú adat is rendelkezésre állt az üzenetváltásokról, én az egymásnak elküldött karakterek számát választottam az élek súlyozására. Ebben a hálózatban 20.298 él szerepelt, így éls¶r¶sége
1,13 · 10−2 .
Az eredeti
adatbázis irányított éleket tartalmazott, amit én az adott csúcspárhoz tartozó élek súlyának összeadásával tettem irányítatlanná. A 3.7. és a 3.8. ábrákon azt látjuk, hogy ez a hálózat nagyon s¶r¶ : A kritikus pont magasan van, és felhasználók
60%-át.
f = 0-nál
a
k = 3
Érdekes jelenség, hogy
CPM óriás komponens tartalmazza a
ˆ L -nek Q
nem maximuma van, hanem
egy enyhe csökkenés után egy töréspontja meredek csökkenésbe, amellett, hogy és
QL
ˆL Q
is negatív. Ez azt jelenti, hogy a legtöbb csúcs-csoport párra teljesül, hogy
2dαi < di .
Valószín¶leg emiatt lehetséges az is, hogy ez az egyetlen olyan hálózat,
ahol a Kendall-féle korrelációs mértéknek nincsen csúcsa a kritikus pontnál.
3.2.5. Összefoglalás Megvizsgáltunk tehát több súlyozott hálózatot, és gyeltük bennük a CPM csoportfelbontás különböz® modularitás értékeit az alsó súlyküszöb változtatása mellett. Sajnálatos módon a Lázár-fele modularitás az eredeti formájában nem mutat maximumot a kritikus pont közelségében, a többi modularitás mennyiség azonban igen. Ráadásul az is elmondható, hogy a csoportfelbontás maximuma annál jobban kiugrik, minél határozottab a perkolációs átalakulás, ami alapján elmondható, hogy a CPM módszer optimális csoportfelbontást ad a kritikus pont felett.
46
a) 1000
12 10 8 6 4 2
800 S
600 400 200
b)
QL
-0,2 -0,3 -0,4 -0,5 -0,6 -0,7 -0,8
c) 0,015 0,012 Q 0,009 0,006
SC SG 𝜒
𝜒
-0,005 -0,010 -0,015 Q L -0,020 ^
QL QL ^
-0,025
QS QS QC QC ^
^
0,003 d)
0,13 Cp
0,025 0,020 0,015 0,010 0,005 0,000
0,16 0,10
Cp 𝜏B
0,07 0,04
𝜏B
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 f 3.7. ábra. Az unical hálózat CPM csoportfelbontásának mértékei
k=3
mellett. A
szürke vonal a kritikus pont becsült helyét jelöli. a.) A perkolációs átalakulás
≈ 0,85
f ≈
alsó küszöbérték mellett határozottan jelentkezik. b.) Itt mindkét mérték
negatív eredményt ad. Ennek oka, hogy ebben a hálózatban a CPM csoportokra nem teljesül, hogy egy átlagos csúcs éleinek többsége egy csoportba tart. c.) A fuzzy mértékeknek a kritikus pontnál maximuma van. d.) A Pearson-féle korrelációnak maximuma van a kritikus pont felett, a Kendall-féle korreláció viszont szigorúan monoton csökken.
47
a)
S
600 500 400 300 200 100
b)
-0,3 -0,4
QL
-0,5 -0,6
SC SG 𝜒
-0,008
QL QL
-0,012 Q L -0,016 ^
^
-0,020
c) 0,018 0,015 0,012 Q 0,009 0,006 0,003
Cp
0,18 0,15 0,12 0,09 0,06 0,03
𝜒
-0,004
-0,7
d)
9,0 7,5 6,0 4,5 3,0 1,5
QS QS QC QC ^
^
Cp
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 f 3.8. ábra. Az unical hálózat CPM csoportfelbontásának mértékei
k = 4
mellett.
A szürke vonal a kritikus pont becsült helyét jelöli. a.) A perkolációs átalakulás
λ ≈ 0,59
alsó küszöbérték mellett határozottan jelentkezik. b.) Itt is mindkét mér-
ték negatív eredményt ad. c.) A fuzzy mértékeknek a kritikus pontnál egy lokális maximuma van. d.) A Pearson-féle korrelációnak maximuma van a kritikus pontnál.
48
4. fejezet
Az átfed® modularitás optimalizációja
A Lázár-féle modularitás fogalom megalkotásának egyik fontos szempontja volt, hogy egy olyan mennyiség legyen, amely optimalizációja egy, a valós hálózatokban meg gyelhet® csoportstruktúrát eredményez. A diplomamunkám egyik legfontosabb feladata éppen ezért egy olyan algoritmus elkészítése volt, ami ezt a m¶veletet elvégzi. A legtöbb csoportkeresési eljárás csoportfelbontásokat generál le egymás után úgy, hogy ezen csoportfelbontások sorozata egy optimális megoldásba konvergáljon. Egy megoldás akkor optimális, ha egy kiválasztott célfüggvény a globális széls® értékét rendeli hozzá. A determinisztikus algoritmusok esetén a sorozat minden egyes tagjáról egyértelm¶en eldönthet®, hogy milyen csoportfelbontás követi, míg a sztochasztikus eljárások során egy adott csoportfelbontást több, különböz® felbontás követhet, amelyeket az eredeti megoldás szomszédos megoldásainak nevezünk. Eddig nem sikerült olyan determinisztikus algoritmust találnom, amely megtalálja a Lázár-féle modularitás az maximumát. Ez részben érthet®, hiszen ez egy olyan költségfüggvény, amit boolean csoportfelbontásokon értelmezünk, így jó eséllyel több globális maximuma is lehet. Emiatt kézenfekv® volt sztochasztikus eljárást választani. Tettem egy eddig sikertelen kísérletet egy genetikus algoritmus kifejlesztésére, illetve implementáltam egy szimulált h®kezeléses eljárást a probléma megoldására. A genetikus algoritmusok a sztochasztikus eljárások egy olyan osztályát alkotják,
49
ahol mindig egy megoldáshalmazt tartunk fent. Egy adott megoldáshalmazból minden lépésben különböz® módszerekkel mutáció és cross-over, a létez® megoldás kis módosítása, vagy a létez® megoldások összekombinálása egy új halmazt generálunk le, amib®l a költségfüggvény segítségével kiválogatva a legjobb megoldásokat kapjuk a következ® megoldáshalmazt. Az egymást követ® megoldáshalmazokat generációknak nevezzük. Bár az eredmények biztatóak, és további munkával minden bizonnyal hatékonyabbá tehet® a módszer, mivel a genetikus algoritmusnál jóval egyszer¶bb, szimulált h®kezelésen alapuló eljárással gyorsabban, jobb eredményeket sikerült elérnem, ezért az alábbiakban ezt ismertetem.
4.1. A szimulált h®kezelésr®l A szimulált h®kezelést, mint sztochasztikus optimalizációs eljárást az ötvenes években kifejlesztett
M R2 T 2 algoritmus [47] elméleti hátterére alapozva alkotta meg
Kirkpatrick, Gelatt és Vecchi [48]. Az eljárás lényege dióhéjban az, hogy minden lépésben egy aktuális ismert megoldásból véletlenszer¶en új megoldást generálunk. A megoldások min®ségét az el®re adott célfüggvénnyel mérjük. Amennyiben az újabb megoldás jobb, mint az el®z® volt, úgy az új megoldással számolunk tovább. Amennyiben rosszabb, a célfüggvény változásának nagysága alapján általában exponenciálisan lecseng® valószín¶séggel az új, egyébként a régi megoldással számolunk tovább. Azzal, hogy néha az ismertnél rosszabb megoldást is elfogadunk, elkerülhetjük hogy az optimális megoldás keresése közben beragadjunk egy lokális maximumba. A rosszabb megoldás elfogadásának esélyét folyamatosan csökkentjük, ezzel korlátozva az elérhet® megoldások terét, ami így végül egy remélhet®leg optimális megoldásra korlátozódik. Az eljárás egy lehetséges pszeudokódja olvasható a 4.1.1 kódrészletben. A módszernek két fontos pontja van, ami nagyban befolyásolja a teljesítményt. Az els® a szomszédos megoldások kiválasztása, a második pedig az alkalmazott h¶tési procedúra, vagyis a h®mérséklet függése a ciklusok számától. Az implementációmban az egyes állapotok az egynél több csúccsal rendelkez®, összefügg® csoportok halmazai, az alkalmazott célfüggvény pedig a Lázár-féle átfed® modularitás.
50
Kódrészlet 4.1.1:
függvény
szimuláltH¶tés(C0, n)
Q(C)
Visszatér célfüggvény értékével függvény
C
megoldásra.
DQ(k)
Visszatér a k. iterációban használandó h®mérséklettel. függvény
next(C)
Visszatér egy függvény
C -vel
szomszédos, véletlenszer¶ megoldással.
rnd()
Visszatér egy uniform eloszlású random számmal
Q0 ← Q(C0 ) k ← 1 to n ∆Q ← (k), C1 ← (C0 ), Q1 ← Q1 −Q0 do if exp( )> () ∆Q then C ← C , Q ← Q
for
DQ 0
return
next RND
1
0
Q(C1)
1
(C0 )
4.2. Az algoritmus elemei 4.2.1. A Lázár-féle átfed® modularitás pontosítása A Lázár-féle modularitás optimalizálásához ismét szükség van néhány kérdés megválaszolásához, ezek az alábbiak :
Hogyan de niáljuk az éls¶r¶ségét azoknak a csoportoknak, amelyek egyetlen csúcsból állnak ? Ezeknek az éls¶r¶sége ugyanis divergál. Hogyan számoljunk modularitást izolált pontokra ? Mi történik azokkal a csúcsokkal, amelyek nem szerepelnek egyetlen csoportban sem ?
51
Milyen súlyozást használjunk a csoportok modularitásának kiszámításához ?
Az implementációmban az egyetlen csúcsból álló csoportok modularitását de níció szerint -1-nek választottam. Ezt az indokolja, hogy általában ha egy csoportot a csúcsok elhagyásával folyamatosan zsugorítunk, úgy mind az éls¶r¶ség, mind a kimen® fokszám és a teljes fokszám aránya 1-be tart. Az izolált pontok az implementációmban egyetlen csúcsból álló csoportot alkotnak, így a modularitásuk ezeknek is -1. A két csúcsnál kevesebb csúcsból álló csoportokat az algoritmusban ezek után nem is szükséges külön számon tartanom. Amennyiben egy csúcsnak egyetlen csoportja sincs, akkor úgy értelmezem, hogy az egy egy elem¶ csoportban van. Ezzel kizárom, hogy a hálózatban legyen olyan egy elem¶ csoport, amit tartalmaz egy másik, nagyobb csoport. A súlyozást a 3. fejezetben részletezett módon, a redukált csoport méret alapján végzem el. Fontos megjegyezni azonban, hogy mégsem pontosan úgy számoljuk a modularitást, mint az említett fejezetben, mivel ott a csoportba nem sorolt csúcsok együtt egy 0 modularitású csoportot alkotnak. Ezt a módosítást a képletben azért kellett elvégezni, hogy a csoportoktól mentes állapot ne jelentsen lokális maximumot a modularitásban.
4.2.2. A szomszédos megoldások hálózata A szimulált h®kezelés során két kritériumra kell ügyelni, amikor megválasztjuk a módszert, ami alapján az adott állapotból a következ® állapotot generáljuk le :
A szomszédos megoldások hálózatának átmér®je ne legyen túl nagy, különben a megoldások sorozata nagyon lassan fog konvergálni. A szomszédos megoldások hálózata legyen összefügg®, vagyis bármelyik megoldásból legyen elérhet® a többi megoldás. Ellenkez® esetben az eljárás beakadhat az állapottér egy részhalmazába, amely nem tartalmazza az optimális megoldást.
Bár a szimulált h®kezelés legtöbb alkalmazási területén olyan rendszereket vizsgálnak, ahol a részletes egyensúly elve teljesül, ez nem kritérium, és ezt az algoritmusomban ki is használom.
52
Az implementációmban az els® lépés egy szomszédos állapot legenerálásához, hogy a gráf elemei közül véletlenszer¶en kijelölök egy csúcsot. Ezután a csúcs csoport fokszámmal arányosan kiválasztok közülük egy csoportot. (A csúcscsoport fokszám néhány kivételt®l eltekintve a csoport elemeire, és a csoport elemeivel szomszédos elemekre nem nulla.) A Lázár-féle modularitás képletét megvizsgálva könnyen beláthatjuk, hogy annak értéke a csúcs-csoport fokszámoktól négyzetesen függ, emiatt igen el®nyös a magasabb csúcs-csoport fokszámmal járó lépések preferenciája. A csúcs-csoport pár kijelölésével meg is kaptunk egy m¶veletet, amit elvégezve megkapjuk a következ® megoldást. Ugyanis ha a csúcs tagja ennek a csoportnak, úgy a m¶velet a csúcs eltávolítása a kiválasztott csoportból, vagyis a csoport zsugorítása, míg ha a csúcs nem tagja a csoportnak, úgy megpróbáljuk a csúcsot hozzáadni a csoporthoz. Bár ez a módszer önmagában eléggé gyors, ha pusztán ezeket a lépéseket tesszük meg a szomszédos állapotok keresése érdekében, a szimulált h®kezelés elégtelen megoldásokat ad. A probléma ilyenkor a megoldásokkal az alábbiak :
Nem minden csoport összefügg®. Az ilyen csoportokat komponenseire bontva közvetlenül növelhetnénk a teljes hálózat modularitását, ezen kívül az ilyen csoportok zikailag nem is értelmezhet®ek. Bizonyos csoportok többször is el®fordulnak a felbontásban, illetve gyakran tartalmazzák egymást. Ilyenkor egyik, vagy másik csoport modularitása jellemz®en negatív. A jelenség érthet® : az eredeti képlet bünteti az átfedéseket, így ha egy csoportban vannak negatív modularitású csúcsok, könnyen lehet növelni a teljes modularitást azzal, ha a negatív járulékot adó csúcsokon új csoportokat de niálunk. A f® gond itt is az, hogy ezek a csoportok nem hordoznak valódi zikai jelentést.
A fenti problémák elkerüléséhez a szomszédos megoldások keresését plusz lépésekkel kell b®víteni. Zsugorítás esetén ez két dolgot jelent : Egyrészt meg kell vizsgálni, hogy a zsugorítással nyert csoport összefügg® lenne-e. Ha nem, úgy tiltani kell az adott átmenetet. A másik, hogy megvizsgálom, hogy a zsugorítás utáni csoportot tartalmazza-e másik csoport a hálózatban ; ha igen, a zsugorítás új értelmet nyer, ekkor a zsugorítandó csoportot egyszer¶en eltávolítom a csoportfelbontásból.
53
Ha egy csoporthoz hozzáadunk egy csúcsot, a létrejöv® csoport biztos, hogy összefügg® lesz. Amennyiben a növelend® csoportot nem tartalmazta másik csoport, abban is biztosak lehetünk, hogy a nagyobbat sem fogja. Egyedül azt kell tehát ellen®riznünk, hogy az újonnan létrejöv® csoport ne tartalmazzon más csoportokat a lefedésb®l. Amennyiben tartalmaz, úgy ezeket a csoportokat az új lefedésb®l szintén ki kell hagynunk.
4.2.3. Könyvelés Adott egy csoportfelbontás tok száma
L.
N
méret¶,
z
átlagos fokszámú gráfon, ahol a csopor-
Legyen továbbá a csúcsok átlagos degeneráltsága
csoportok átlagos mérete
hqi i.
Ez alapján a
hqi iN/L.
A Lázár-féle modularitás központi mennyisége a csúcs-csoport fokszám, ennek
kiszámításához
szükséges
L · N · hqi iN/L = hqi iN
2
m¶veletek
száma
minden
csúcs-csoport
párra
. Egy másik fontos mennyiség a csúcsok degeneráltsága,
amihez kiszámításához minden csoport minden elemén végig kell iterálnunk, ennek m¶veletigénye tehát
hqi iN .
A csúcs-csoport fokszámok és a degeneráltságok ismere-
tében egyszer ismét enumerálnunk kell az összes csoport minden tagját, hogy megkapjuk az átfed® modularitást. Ennek költsége ismét modularitás kiszámításának amortizált költsége
hqi iN , ami alapján a Lázár-féle
hqi iN +hqi iN +hqi iN 2 = O(hqi iN 2 ).
Minden egyes megoldásra ezt a komplexitást nyilvánvalóan nem engedhetjük meg magunknak, ezért szükség van a csúcs-csoport fokszámok könyvelésére. A 4.2.2. alfejezetben javasolt algoritmus alapján két egymást követ® lefedés úgy térhet el egymástól, hogy egyes csoportokat elhagyunk, bizonyos csúcsok egy elem¶ csoportba kerülnek, illetve egyetlen csoport egy csúccsal nagyobb, vagy eggyel kisebb lesz. Ennek a csoportnak a csúcs-csoport fokszámát tehát megkaphatjuk az el®z® állapotból úgy, hogy a hozzá kijelölt csúcs szomszédainak csúcs-csoport fokszámát egyel növeljük, vagy csökkentjük. Átlagban tehát a csúcs-csoport fokszám könyvelésének m¶veletigénye
hdi i = z
(a gráf átlagos fokszáma).
Annak a m¶veletigénye, hogy ellen®rizzük egy átlagos csoport összefügg®ségét breath- rst search algoritmussal
zhqi iN/L, hiszen a csoport összes élét meg kell láto-
gassuk. Egy csoport növelésekor egyetlen csúcs csoportjait kell megvizsgálnunk, hogy azokat tartalmazza-e az új csoport. Ennek a m¶veletigénye
hqi i2 N/L,
amennyiben
könyveljük azt is, hogy egy csúcs mely csoportoknak tagja. Csoportok zsugorítása-
54
kor a létrejöv® csoportot össze kell hasonlítanunk azokkal a csoportokkal, amelyeknek tagjai a létrejöv® csoport csúcsai közül valamelyik. Ezeknek a csoportoknak az enumerációja szintén ható értéke
hqi i
hqi i2 N/L
m¶veletigény¶. A kapott csoportok számának vár-
nagyságrend¶, így azt ellen®rizni, hogy ezen csoportok bármelyike
hqi i2 N/L
tartalmazza-e az új csoportot szintén
m¶veletigény¶ feladat.
hqi iN ,
A teljes modularitás kiszámítása a fokszámok ismeretében most is alapján egy iteráció teljes m¶veletigénye
= O(hqi iN ).
ami
2
N hqi i + zN hqi i/L + z + hqi i N/L =
A fokszámok, és a csúcsok csoportjainak könyvelésével tehát sikerült
kiküszöbölnünk az iterációk m¶veletigényének négyzetes függését a gráf méretét®l.
4.2.4. Az összes szomszédos megoldás meglátogatásához szükséges id® Érdekes kérdés, hogy hogyan függ a szimulált h®kezelés során szükséges iterációk száma a vizsgált hálózat tulajdonságaitól. A folyamat hosszát jól jellemzi az az id®, ami ahhoz szükséges, hogy egy adott megoldás összes szomszédos megoldását végiglátogassuk. Ez az id® szükséges ahhoz is, hogy amennyiben az aktuális megoldás hosszú ideje nem változott, belássuk, hogy lokálisan optimális megoldást találtunk. Legyen
C0
egy ilyen megoldás, amit
Bαi
boolean tagsági mátrix jellemez, ahol
Bαi = 1, amennyiben vi ∈ α és Bαi = 0, ha vi ∈ / α. Ha C1 és
vi
csúcs jelöli ki, akkor a
C0 → C1
megoldást ebb®l
α csoport
átmeneti valószín¶ség :
dαi dαi P(C0 → C1 ) = pαi ∝ P ≈ . di β dβi Itt a jobb oldali közelítésnél azzal a feltételezéssel éltünk, hogy
(4.1)
P
β
dβi ∝ di ,
ami a tapasztalatok szerint jó közelítéssel teljesül, mivel a legtöbb csúcs általában egyetlen csoporthoz tartozik. Annak a valószín¶sége, hogy a látogattuk meg, értelemszer¶en
k.
iteráció után
(1 − pαi )k ≈
{i,α}
állapotot még mindig nem
(1−pαi )k . Mivel a szomszédos állapotok száma nagy,
ezért a meg nem látogatott állapotok várható értéke
X
C1
X {i,α}
55
k
iteráció után :
exp (−kpαi )
(4.2)
Ahol kihasználtuk, hogy séget a legkisebb
pdi
pαi
kicsi, emiatt
értékkel tudunk felülr®l becsülni. Legyen
tehát a szomszédos állapotok legalább rációk száma
k ln(1 − pαi ) ≈ −kpαi .
99%-ának
A fenti mennyi-
min pαi = pmin ,
ekkor
végiglátogatásához szükséges ite-
4,6/pmin .
4.2.5. Egyéb részletek A h¶tés ütemezésére Kirkpatrick és munkatársai által a [48] cikkben javasolt exponenciális sémát alkalmaztam. A séma ciklusokra bomlik, amelyek alatt a h®mérséklet konstans. A és
∆Q0
k. ciklusban a h®mérséklet ∆Qk = ∆Q0 αk , ahol α h¶tési ráta
kezd®h®mérséklet az algoritmus paraméterei. A ciklusok hosszát az aktuá-
lis csoportfelbontásból az el®z® fejezetben részletezett módon számítom ki minden ciklus elején. A ciklusok száma az algoritmusomnak nem paramétere, megállási feltételként azt vizsgálom, hogy egy ciklus alatt változik-e a megoldás. Amennyiben egy ciklus alatt nem változott a megoldás, a futás véget ér. Az algoritmust Java SE 6.0 programozási nyelven implementáltam, mivel kiváló kompromisszumot jelent a magas szint¶ szintaxis, a sebesség és a hordozhatóság között. A teljes forráskód megjegyzések nélkül 1466 sorból áll.
4.3. Eredmények 4.3.1. A vizsgált hálózatok Zachary karate klub hálózata [49] egy olyan hálózat, amit rendszeresen szoktak alkalmazni csoportkeres® algoritmusok tesztelésére. Maga a hálózat Zachary 70-es évekbeli publikációjából származik, amiben kis közösségek szétszakadásának okait és körülményeit vizsgálta. A hálózat egy egyetemi karate klub szociális hálózatát tartalmazza, ahol élek olyan személyek között vannak, akik a a meg gyelés két éve alatt rendszeresen találkoztak egymással a klubon kívül is. A klub az oktatója és adminisztrátora (1-es és 34-es csúcs) miatti nézeteltérés miatt két részre szakadt, ami a hálózat egy természetes csoportfelbontását adja. A hálózat 34 csúcsból és 74 élb®l áll.
56
A gimnáziumi osztály hálózat egy 2009-ben, egy f®városi gimnáziumban végzett osztály szociogramja az érettségi évében. Az osztállyal minden évben kitöltettek egy tesztet, amelyben három kérdést tettek fel, mind a három kérdésre pedig legfeljebb három-három névvel lehetett válaszolni. A hálózat a viszonzott kapcsolatokat tartalmazza, vagyis azokat az eseteket, amikor ketten feltüntették egymás nevét ebben a tesztben. Az eredeti hálózat összesen 33 csúcsot és 61 élt tartalmaz, de tartalmaz 4 izolált csúcsot, amit az 4.2. ábrán nem tüntettem fel.
Del nek hálózata egy 2003-ból származó hálózat, az új-zélandi Doubtful Sound fjordnál él® del nek közösségét mutatja be. A hálózat 62 csúcsa között 159 él fut. Az élek azon del nek között futnak, akiket gyakran meg gyeltek egymás társaságában.
Az amerikai focicsapatok hálózta amerikai f®iskolák focicsapatai között 2000 ®szén játszott meccseket tartalmazza. Az egyes csapatok összesen 12 csoportban játszottak egymással, ami így a csúcsok egy természetes csoportosítását adja. A hálózat összesen 615 mérk®zést tartalmaz 115 csapat között.
4.3.2. Teljesítmény A program teljesítményét többek között lehet úgy mérni, ha mohó futtatásokat végzünk, azaz vizsgáljuk, hogy
0
h®mérséklet mellett mekkora modularitású megol-
dásokat ad a program, hány lépésben, és milyen hosszú a lépések futásideje. Ezt a mérést 1000 futtatásra elvégeztem a fent felsoroltak közül az els® négy hálózaton. A leállási feltételt úgy határoztam meg, hogy a lépésszám egyezzen meg a futtatás során elért legjobb modularitáshoz tartozó lépésszám duplájával. A mérési eredményeket a 4.1. táblázat tartalmazza. A futtatásokat egy személyi számítógépeken végeztem.
4.3.3. Az algoritmus eredményei példahálózatokon Az alábbi ábrák elkészítéséhez két lépést alkalmaztam : El®ször mohó optimalizációval kerestem egy megoldást, majd egy próbálgatással kiválasztott alacsony h®mérsékletet és h¶tési rátát kiválasztva a konvergenciáig futtattam az algoritmust. Az ábrákat magukat Gephi segítségével készítettem, és utólag kézzel jelöltem be benne a csoportokat. Az Amerikai focicsapatok hálózata túl nagy volt ahhoz, hogy a h¶tés paramétereivel kísérletezve azonnal látható legyen az eredmény. Emiatt ennél
57
Hálózat
Qmax
hQi
σQ
hni
σn
ts [µs]
Karate klub
0,339
0,284
0,0280
1028,66
527,428
109,328
Gimnáziumi osztály
0,442
0,401
0,0305
597,863
285,947
206,692
Del nek
0,235
0,120
0,0122
4563,64
1819,49
113,792
Amerikai focicsapatok
0,307
0,251
0,0285
28508,7
6691,44
231,674
4.1. táblázat. Az algoritmus tesztelése kis csoportokkal, mohó optimalizációval. A fenti táblázat minden sora ezer futtatás eredményét tartalmazza. tatás alatt mért maximális modularitás, szórása.
hni és σn
szórása,
ts
hQi
és
σQ
Qmax
az ezer fut-
a mért modularitások átlaga és
a lokális maximum eléréséhez szükséges ciklusok átlagos száma és
pedig egy ciklus átlagos hossza
µs-ban.
a hálózatnál csak mohó optimalizációt végeztem. A kapott csoportfelbontásban 15 csapat szerepel, és a felbontás modularitása 0,252.
4.4. Az elkészült algoritmusról Mára már csoport keres® eljárásból rengeteg elérhet® a szakirodalomban, még akkor is, ha ezeknek csak egy kis része keres átfed® csoportokat. Az általam prezentált módszer ezekkel szemben annyiban nyújthat többet, hogy általánosítható : gyakorlatilag bármilyen jelleg¶ modularitás mennyiség kiértékelésére fel lehet használni. Hátránya persze ennek is van ; mégpedig, hogy sajnos az algoritmus java implementációja messze nem eléggé gyors, ezen kívül az alkalmazása a futtatási paraméterek helyes meghatározása miatt körülményes. Mindezen segíthetne az evolúciós algoritmus implementációja. Várhatóan azonban nagyságrendbeli gyorsulás ezen a téren sem várható, ez pedig jelen®sen korlátozza az ezen mérték optimalizálásán alapuló módszerek alkalmazhatóságát.
58
15 16
23 21 31
22
33
19 27
20
9
2
18
34 30
10
14
3
6
5
7
17
13
32
28 26
12
11
4
29
24
1
8
25
4.1. ábra. A karate klub hálózat csoportfelbontása a Lázár-féle modularitás optimalizációjával. Az ábrán látható felbontás modularitása 0,341. A CPM módszerrel,
k = 3
paraméter mellett kapott csoportfelbontás ugyanezen a hálózaton 0,164. A
hagyományosan ismert két csoport határát az ábrán szaggatott vonal jelöli.
a.)
b.)
30
19
26
33 9
17
21 17
16
3
24
12
11 12
4 27
23
20
1
13 8
6
22
25
32 27
20
1
29
22
25
24
14 2
32
8
16
3
29
11
13
10
7
14
4
28
9
10 21
2
26
33
28
7
30
19
23 6
4.2. ábra. a.) Egy gimnáziumi osztály szociogramjának csoportfelbontása a Lázárféle modularitás optimalizációjával. Az ábrán látható felbontás modularitása 0,442. b.) Egy gimnáziumi osztály szociogramjának csoportfelbontása CFinderrel. Az ábrán látható felbontás modularitása 0,301.
59
Five
Vau
Cross
MN60
SMN5 Trigger
SN89
MN83 MN105
Zap DN16
Wave
DN21
TR82
SN100
Web
Feather
Haecksel Topless
Gallatin
SN90 Zig
Ripplefluke
Grin
Scabs
Hook SN63
Beescratch Upbang Oscar
Stripes
Shmuddel TR88 Beak
Kringel
TR120
TSN103
SN4
SN9
Double
Patchback
Jonah
TR99
CCL
Fork
TSN83
Fish
Jet
TR77
Knit DN63
Zipfel
Whitetip
SN96 PL
Number1
Thumper
Quasi MN23
Bumper Mus
Notch
4.3. ábra. A del nek szociális hálózatának csoportfelbontása a Lázár-féle modularitás optimalizációjával. Az ábrán látható felbontás modularitása 0,218, míg a CPM módszerrel,
k = 3 paraméter mellett kapott csoportfelbontás ugyanezen a hálózaton
-0,108.
60
5. fejezet
Összefoglalás
5.1. Célok és motivációk A diplomamunkámnak kett®s célja volt. Az egyik, hogy ellen®rizzünk egy régóta álló ökölszabályt, miszerint a CPM módszert a
k -klikk
perkoláció kritikus pontja
felett célszer¶ használni a jó eredményekért. Ezt a hipotézist ellen®riztem, és - legalábbis a vizsgált hálózatokon, kvalitatív módon - bizonyítást nyert. Ezen kívül az eddigi modularitás mennyiségek mellett újabbakat is kerestem, illetve kipróbáltam. A másik cél az Lázár-féle modularitás közvetlen sztochasztikus optimalizációján alapuló csoport keres® alkalmazás elkészítése volt, és ezt a célt is sikerült elérnem. A munka folytatható az alkalmazás felhasználó-baráttá tételével, vagyis integrációja valamilyen gra kus felülettel (pl. Gephi, Cytoscape), illetve többfajta célfüggvény beépítésével. Ezen kívül érdemes lehet még a végére járni, hogy milyen javulás érhet® el teljesítményben a genetikus algoritmusok alkalmazásával.
5.2. A Lázár-féle modularitásról A diplomamunkám legfontosabb motivációja a Lázár-féle modularitás vizsgálata volt. Sajnos végeredményben elmondhatom, hogy az eredeti Lázár-féle modularitás tartalmaz hiányosságokat : Az eredeti cikkben fontos kérdések kifejtés nélkül maradnak, mint például az egy- két csúcsból álló csoportok modularitásának kérdése, vagy hogy mi a teend® a csoportokba be nem sorolt csúcsokkal. Az eredeti képlet szerencsétlennek bizonyult abból a szempontból is, hogy a modularitást a csoportok
61
modularitásának átlagában határozza meg, illetve abból, hogy a szerz®k igyekezete ellenére a képlet egy nem-lokális de níciót ad. Ez a felismerés vezetett el engem a 3. fejezetben bemutatott újabb típusú modularitás mennyiségek vizsgálatához, bár tény, hogy ezek sem lokálisan additív mennyiségek. A Lázár-féle fogalom mindennek ellenére tartalmaz helyes és fontos gondolatokat. Ilyen, hogy el®ször a megtalált csoportok min®sége alapján próbálja jellemezni a teljes hálózatot, vagyis ebben az értelemben mégis lokális. Ezen kívül nem szükséges semmilyen további paraméter az alkalmazásához, tehát abszolút, illetve az, hogy valamilyen szinten a csoportfejl®dés jellegzetességeit szem el®tt tartva készült. A Lázár-féle modularitás optimalizálására írandó algoritmus mutatott rá számomra, hogy milyen reális elvárásokat támaszthatunk egy mennyiség optimalizációján alapuló átfed® csoportkeres® algoritmussal szemben :
1. Az egész hálózat modularitása legyen meghatározható a csoportok modularitása alapján. 2. A módszer által kapott csoportok legyenek összefügg®ek. 3. A csoportok éls¶r¶sége legyen nagyobb a környezetüknél. 4. A csoportok ne tartalmazzák egymást, a megoldás ne tartalmazhassa ugyanazt a csoportot kétszer. 5. A környez® élek, csoportok kis változására legyen a megoldás stabil. (Teljesüljön a lokalitás.)
5.3. Köszönetnyilvánítás El®ször is szeretném megköszönni a témavezet®mnek, Palla Gerg®nek az iránymutatást, a cikkeket, a rengeteg jó tanácsot, és segítséget, amit ezen munka során, illetve a publikáció során is kaptam. Szeretném megköszönni Vicsek Tamás tanár úrnak, amiért gyelmembe ajánlotta ezt a témát, illetve segített a munka publikációjában, és általában Pollner Péternek és a tanszék munkatársainak, amiért megengedték, hogy súlyos CPU id®t orozzak el el®lük közös szervereken.
62
A függelék
Fontos fogalmak, jelölések
A gráfelmélet és a hálózatkutatás eredményeit többen, többféle módon foglalták már össze, vagy fordították le magyarra. A különböz® fordításokban az azonos fogalmakra használt magyar kifejezések sajnos nem minden esetben egyeznek meg, arról nem is beszélve, hogy az egyes fogalmakra használt jelölések is nagyon különböz®ek a szakirodalomban. Ezt a problémát leküzdend® az alábbi fejezetben igyekszem tisztázni az általam használt alapfogalmakat, illetve megadni a megfelel® jelölések jelentését.
A.1. Gráfok típusai G = (V [G], E[G]) E[G] = {e1 , e2 , ...eM }
gráf alatt
V [G] = {v1 , v2 , ...vN }
csúcsok (node, vertex) és
élek (edge, link) halmazának párosát értjük.
gráf, vagy más szóval digráf, amennyiben
E[G]
a
V [G]
G
irányított
halmaz elemeib®l alkotott
rendezett, irányítatlan gráf (vagy egyszer¶en gráf ) amennyiben rendezetlen párok halmaza. Az irányítatlan gráfokat többnyire fel lehet fogni digráfként úgy, mintha minden irányítatlan él két, egymással ellentétes irányú irányított élb®l állna. Amennyiben a gráf hurkot (loop), vagyis olyan élt tartalmaz, amelynek a két végpontja azonos, úgy pszeudográfról, amennyiben két csúcs között több élt tartalmaz (vagyis olyan élt tartalmaz, aminek a multiplicitása nagyobb, mint 1), multigráfról beszélünk. Az olyan nem-multigráfokat, amelyek nem tartalmaznak hurkot, egyszer¶ gráfoknak nevezzük.
H = (V [H], E[H])
gráf
G
gráf részgráfja, amennyiben
63
V [H] ⊂ V [G]
és
E[H] ⊂
⊂ E[G]. H
feszít® részgráfja
G
tartalmazza
G-nek, ha V [H] = V [G], és feszített, amennyiben E[H]
összes olyan élét, ami
H
csúcsait köti össze. Csoport alatt a legtöbb
esetben a csoport csúcsaira feszített részgráfot értünk.
Összefügg®nek nevezzük azt a gráfot, amelyben bármely két csúcs között létezik a gráfban út. Teljes gráfnak nevezzük az olyan egyszer¶ gráfokat, amelyekben bármely két csúcs között létezik él. Fának nevezzük az olyan összefügg® gráfokat, amelyekb®l bármelyik élt eltávolítva a gráf már nem lesz összefügg®. Erd®nek nevezzük az olyan gráfokat, amelyek felírhatók több fa uniójaként. Bipartitnak nevezünk egy gráfot akkor, ha a csúcsokat két osztályba lehet sorolni úgy, hogy az azonos osztályban lév® csúcsok között nincsen él.
G gráf súlyozott, amennyiben minden ei ∈ E[G] élhez egyértelm¶en hozzárendelhet®
w(ei )
általában pozitív, valós szám. Leggyakrabban egyszer¶ gráfokkal dolgo-
w
függvényt, hogy olyan élekre is de niálva legyen,
ami nem része a gráfnak. Ekkor a
Wij = w(vi , vj ) súlymátrix (weight matrix) megfe-
zunk, ilyenkor úgy vezetjük be
lel® eleme
0.
Irányítatlan gráfokra
szerint nincsenek hurkok, így
Wij
Wij = Wji ,
és mivel egyszer¶ gráfokban de níció
diagonális elemei azonosak
0-val.
1
lenne.
gráfokra tekinthetünk úgy is, mintha minden létez® él súlya
A súlyozatlan
Két csúcs szomszédos egymással, ha a gráfnak van olyan éle, amelyik a két csúcsból áll. A
vi
viszonyt az
vj
csúccsal szomszédos csúcsok halmazát
Aij
N (vi )
jelöli. A szomszédsági
szomszédsági mátrix (adjacency matrix) fejezi ki, ahol
közötti élek multiplicitását jelenti. Emiatt irányítatlan gráfok esetén
Irányított gráfok esetén azonban lyek kezd®pontja
Aij
Aij
a
vi
és
Aij = Aji .
alatt szigorúan azon élek számát értjük ame-
vi , végpontja vj . Egyszer¶ súlyozatlan gráfok szomszédsági mátrixa
emiatt megegyezik a súlymátrixukkal. Egy csúcs és egy él szomszédos, amennyiben az él tartalmazza a csúcsot, vagy más szavakkal az él kezd®- vagy végpontja az adott csúcs. Két irányított élt szomszédosnak nevezünk, amennyiben az egyik végpontja megegyezik a másik kezd®pontjával. Két irányítatlan élt szomszédosnak nevezünk, amennyiben van közös csúcsuk.
A.2. A fokszám ≡ di,ki ,
ill.
alatt azon élek számát értjük, amelynek kezd®, illetve végpontja
vi ,
Irányított gráfoknál
dGi ≡ di,be )
vi
csúcs kimen®, illetve bemen® fokszáma (diG
64
azaz :
X
di,ki =
Aij ,
illetve
di,be =
vj ∈G
X
Aji .
(A.1)
vj ∈G
Irányítatlan gráfokban a két szám megegyezik, vagyis
di = di,ki = di,be .
De -
niáljuk a csúcscsoport fokszámot, mint a azon élek számát, amelyeknek az egyik végpontja
vi ,
a másik végpontja pedig
α
részgráf egy csúcsa. Irányított esetben ezt
meg tudjuk különböztetni a csoportcsúcs fokszámtól :
diα =
X
Aij ,
illetve
dαi =
vj ∈α Ha
α, β ⊆ G,
X
Aji
(A.2)
vj ∈α
de niálhatjuk köztük a csoport-csoport fokszámot :
dαβ =
XX
Aij .
(A.3)
vi ∈α vj ∈β
α
részgráf teljes fokszáma megegyezik a teljes gráal vett fokszámával. Ilyesfor-
mán irányított gráfban megkülönböztethetünk kimen® (dαG bemen® nek :
dGα =
P
vi ∈α
di,be
=
P
vi ∈α
di,ki ),
illetve
teljes fokszámokat. Irányítatlan esetben ezek megegyez-
dGα = dαG = dα .
Beszélhetünk küls®, illetve bels® fokszámról is. A bels® fokszám irányított és irányítatlan esetben is megegyeznek, és a részgráf önmagával vett csoport-csoport fokszámát jelenti :
dαα =
P
vi ,vj ∈α
Aij .
Irányított esetben megegyezik az csoportban
futó élek számával, irányítatlan esetben annak kétszeresével. A (kimen®, bemen®) küls® fokszám (dαα ,
dαα )
nem más, mint a (kimen®, bemen®) teljes fokszám, és a
bels® fokszám különbsége. A szám azt jelenti, hogy az adott részgráfnak mennyi kapcsolata van a környezetével.
A.3. Legrövidebb út és átmér® Bolyongásnak (walk) nevezünk egy gráfon belül egy szomszédos élek alkotta sorozatot. A bolyongás hossza a bolyongás éleinek száma. A zárt bolyongás ugyanabban, a nyílt bolyongás eltér® csúcsban végz®dik, mint ahonnan kiindult. Séta (open trail) alatt olyan bolyongást értünk, amely nem tartalmaz egy élt kétszer, út (open path)
65
alatt olyan nyílt sétát értünk, ami nem érint egy csúcsot kétszer. Kör alatt olyan zárt sétát értünk, amely minden egyes csúcsot legfeljebb egyszer hagy el.
vi
és
vj
csúcs távolsága alatt általában a
hosszát értjük.
vi
vi
és
vj
között található legrövidebb út
excentricitása a legnagyobb távolság, ami
vi
és a gráf többi csúcsa
között létezik.
A.4. Gráfok alapvet® metrikái G
gráf mérete a csúcsainak száma, jele általában
N. M
a gráf éleinek száma,
ami digráfoknál megegyezik a gráf bels® fokszámával, irányítatlan gráfokra pedig
dG = 2M . z = dG /N
a gráf átlagos fokszáma. A gráf éls¶r¶sége megegyezik a gráf
éleinek számának, és a gráfban maximálisan lehetséges élek számának a hányadosával. Irányított és irányítatlan esetben is kifejezhet® a fokszámmal :
ρ = dG /N (N − 1)
A gráf átmér®je, illetve sugara a gráf csúcsainak excentricitása közül a legnagyobb, illetve legkisebb. Fontos metrika még
hli,
vagyis az átlagos legrövidebb út-
hossz. Nagyságrendileg mind a három szám megegyezik, nem összefügg® gráfokra egyformán végtelenek.
66
Irodalomjegyzék
[1] Palla Gergely, Derényi Imre, Farkas Illés, and Vicsek Tamás. Uncovering the overlapping community structure of complex networks in nature and society.
Nature, 435(814-818), Június 2005. [2] Bálint Tóth, Tamás Vicsek, and Gergely Palla. Overlapping modularity at the critical point of k-clique percolation. Journal of Statistical Physics, December 2012. DOI :10.1007/s10955-012-0640-5. [3] Erd®s Pál and Rényi Alfréd. The evolution of random graphs. Magyar Tud.
Akad. Mat. Kutató Int. Közl., 5 :1761, 1960. [4] Nagy Máté, Ákos Zsuzsa, Bíró Dóra, and Vicsek Tamás.
Hierarchical group
dynamics in pigeon ocks. Nature, 464 :890893, 2010. [5] Zafeiris Anna and Vicsek Tamás. Collective motion. Physics Reports, 517 :71 140, 2012. [6] Romualdo Pastor-Satorras and Alessandro Vespignani. Evolution and Structure
of the Internet - A Statistical Physics Approach. Cambridge University Press, 2004. [7] Steven Strogatz Duncan J. Watts.
Collective dynamics of 'small-world' net-
works. Nature, 393(6684) :440442, 1998. [8] J.-P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A.-L. Barabási. Structure and tie strengths in mobile communication networks. Proc. Natl. Acad. Sci. USA, 104 :73327336, 2007. [9] Jörg Reichardt and Stefan Bornholdt. Detecting fuzzy community structures in complex networks with a potts model. Physicsal Review Letters, 93, 2004.
67
[10] H. Ebel, L.-I. Mielsch, and S. Bornholdt. Scale-free topology of e-mail networks.
Phys. Rev. E, 66 :035103(R), 2002. [11] Barabási Albert-László Albert Réka. Statistical mechanics of complex networks.
Reviews of Modern Physics, 74 :4797, 2002. [12] Duncan J. Watt. Six Degrees : The Science of a Connected Age. W. W. Norton and Company, 2003. [13] Barabási Albert-László. Villanások. Nyitott Könyvm¶hely, 2010. [14] Erd®s Pál and Rényi Alfréd. On random graphs. i. Publicationes Mathematicae, 6 :290297, 1959. [15] Barabási Albert-László and Albert Réka. Emergence of scaling in random networks. Science, 286(5439) :509512, Október 1999. [16] Sergey Dorogovtsev and José Fernando Mendes. Exactly solvable small-world network. Europhys. Lett., 50 :17, 2000. [17] Sergey Dorogovtsev and José Fernando Mendes.
Eect of the accelerating
growth of communications networks on their structure. Phys. Rev. E, 63, 2001. [18] Santo Fortunato. Community detection in graphs. Physics Reports, 486 :75174, 2010. [19] Mark E. J. Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical Review E, 69, 2004. [20] Lázár Anna, Abel Dániel, and Vicsek Tamás. Modularity measure of networks with overlapping communities. EPL, 90 :18001, Április 2010. [21] Coen Bron and Joep Kerbosch. Algorithm 457 : nding all cliques of an undirected graph. Communications of the ACM, 16(575-577), 1973. [22] Lin Shen Brian W. Kernighan. An e cient heuristic procedure for partitioning graphs. Bell Systems Technical Journal, 49 :291307. [23] Lester Randolph Ford and Delbert Ray Fulkerson.
Maximal ow through a
network. Canadian Journal of Mathematics, 8 :399404, 195.
68
[24] Michelle Girvan and Mark E. J. Newman. Community structure in social and biological networks. PNAS, 99 :78217826, 2002. [25] Ulrik Brandes. A faster algorithm for betweenness centrality. Journal of Ma-
thematical Sociology, 25 :163177, 2001. [26] Mark E. J. Newman.
Fast algorithm for detecting community structure in
networks. Physical Review, 2004. [27] Santo Fortunato and Marc Barthélemy. Resolution limit in community detection. PNAS, 104 (1) :3641, 2007. [28] Zhenping Li, Shihua Zhang, Rui-Seng Wang, Xiang-Sun Zhang, and Luonan Chen. Quantitative function for community detection. Physicsal Review E, 77, 2008. [29] Derényi Imre, Palla Gergely, and Vicsek Tamás. Clique percolation in random networks. Physical Review Letters, 94, 2005. [30] Jerey Baumes, Mark Goldberg, and Malik Magdon-Ismail. E cient identi cation of overlapping communities. LNCS, pages 2736, 2005. [31] Andrea Lancichinetti, Santo Fortunato, and Kertész János. Detecting the overlapping and hierarchical community structure in complex networks. New Jour-
nal of Physics, 11, 2009. [32] Jierui Xie and Boleslaw K. Szymanski. Community detection using a neighborhood strength driven label propagation algorithm. IEEE NSW, pages 188195, 2011. [33] Adamcsek Balázs, Palla Gergely, Illés J. Farkas, Derényi Imre, and Vicsek Tamás. C nder : Locating cliques and overlapping modules in biological networks.
Bioinformatics, 22(1021-1023), 2006. [34] Palla Gergely, Farkas Illés, Pollner Péter, Derényi Imre, and Vicsek Tamás. Directed network modules. New Journal of Physics, 9, 2007. [35] Farkas Illés, Ábel Dániel, Palla Gergely, and Vicsek Tamás. Weighted network modules. New Journal of Physics, 9, 2007.
69
[36] Nepusz Tamás, Petróczi Andrea, Négyessy László, and Bazsó Fülöp.
Fuzzy
communities and the concept of bridgeness in complex networks. Physical Re-
view E, 77, 2008. [37] Hua-Wei Shen, Xue-Qi Cheng, Kai Cai, and Mao-Bin Hu. Detect overlapping and hierarchical community structure in networks. Physica A, 388 :17061712, 2009. [38] Hua-Wei Shen, Xue-Qi Cheng, and Jia-Feng Guo. Quantifying and identifying the overlapping community structure in networks. Journal of Statistical Me-
chanics, 2009. [39] Duan-Bing Chen, Ming-Sheng Shang, Ze-Hua Lv, and Yan Fu. Detecting overlapping communities of weighted networks via a local algorithm.
Physica A,
389 :41774187, 2010. [40] Mark E. J. Newman. Scienti c collaboration networks : I. network construction and fundamental results. Physical Review E, 64 :404409, 2001. [41] Mark E. J. Newman. Scienti c collaboration networks : II. shortest paths, weighted networks, and centrality. Physical Review E, 64, 2001. [42] Mark E. J. Newman. The structure of scienti c collaboration networks. Proc.
Natl. Acad. Sci. USA, 98 :404409, 2001. [43] Doughlas
L.
Neslon,
Cathy
L.
McEvoy,
and
Thomas
A.
Schreiber.
http ://www.usf.edu/FreeAssociation/, 1998. [44] Tore Opsahl and Pietro Panzarasa.
Clustering in weighted networks.
Social
Networks, 31 :155163, 2009. [45] Maurice Kendall. A new measure of rank correlation. Biometrika, 30 :8189, 1938. [46] David Christensen. Fast algorithms for the calculation of kendall's
τ.
Comp-
utational Statistics, 20 :5162, 2005. [47] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, and Teller Ede Teller Mária. Equation of state calculation by fast computing machines.
Reviews of Modern Physics, 21 :10871091, 1953. 70
[48] Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi.
Optimization by
simulated annealing. Science, 220 :671680, 1983. [49] Wayne W. Zachary. An information ow model for con ict and ssion in small groups. Journal of Anthropological Research, 33(4) :452473, 1977.
71
