A PageRank és alkalmazása

A PageRank és alkalmazása Szakdolgozat

Írta: Kiss Dániel Matematika BSc szak matematikai elemző szakirány

Témavezető:

Grolmusz Vince egyetemi tanár Számítógéptudományi Tanszék

Eötvös Loránd Tudományegyetem Természettudományi Kar 2012

Tartalomjegyzék Bevezetés

4

1. Hálózati csomópontok centralitásának mérőszámai

5

1.1. A centralitás lehetséges értelmezései egy példán keresztül . . . . . . . . . . .

5

1.2. Néhány központisági mérőszám . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2.1. Fokszám centralitás

. . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2.2. Sajátvektor centralitás . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2.3. Katz-féle centralitás . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2. Markov-láncok alkalmazása a PageRang problémára

9

2.1. Markov-láncok és tulajdonságaik . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.1. Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.2. Állapotok osztályozása . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.3. Aszimptotikus tulajdonságok . . . . . . . . . . . . . . . . . . . . . . 13 2.2. PageRang levezetése Markov-láncokkal . . . . . . . . . . . . . . . . . . . . . 14 2.2.1. A PageRang mátrixos alakja . . . . . . . . . . . . . . . . . . . . . . 14 2.2.2. Első finomítás : visszatérőség . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.3. Második finomítás: irreducibilitás . . . . . . . . . . . . . . . . . . . . 17 2.2.4. Harmadik finomítás : aperiodicitás . . . . . . . . . . . . . . . . . . . 17 2.2.5. Egyszerű példa PageRang kiszámítására . . . . . . . . . . . . . . . . 17 3. A PageRang kiszámítása, paraméterei és stabilitása

19

3.1. Numerikus módszerek néhány alapfogalma . . . . . . . . . . . . . . . . . . . 19 3.1.1. Normák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.2. Sajátértékek és sajátvektorok . . . . . . . . . . . . . . . . . . . . . . 20 3.1.3. Hibák és kondíciószámok . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2. A PageRang mint sajátérték-feladat . . . . . . . . . . . . . . . . . . . . . . 24 3.2.1. A hatványmódszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.2. A hatványmódszer alkalmazhatósága a G mátrixra . . . . . . . . . . 26 3.2.3. A hatványmódszer konvergenciasebessége . . . . . . . . . . . . . . . 27 3.2.4. A hatványmódszer gyakorlati megvalósítása . . . . . . . . . . . . . . 29 3.3. A PageRang mint lineáris egyenletrendszer . . . . . . . . . . . . . . . . . . . 30 2

3.3.1. A megoldás létezése és helyessége . . . . . . . . . . . . . . . . . . . . 31 3.3.2. Az I − cH mátrix M -mátrix . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.3. A feladat kondicionáltsága . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.4. Lehetséges megoldási módszerek . . . . . . . . . . . . . . . . . . . . 34 3.4. A PageRang egyenlet paraméterei . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4.1. A c konstans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4.2. A H hiperlink mátrix . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.4.3. Az E teleportációs mátrix . . . . . . . . . . . . . . . . . . . . . . . . 37 3.5. Perturbált adatok hatása a modellre . . . . . . . . . . . . . . . . . . . . . . 38 4. A PageRang alkalmazása hálózatok összehasonlítására

42

4.1. Protein-protein interakciós hálózatok . . . . . . . . . . . . . . . . . . . . . . 42 4.2. Az IsoRank eljárás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2.1. Az IsoRank-modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2.2. A hasonló részgráf előállítása . . . . . . . . . . . . . . . . . . . . . . 45 4.2.3. Az IsoRank megvalósítása MATLAB környezetben . . . . . . . . . . 46 4.2.4. Teszteredmények . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.5. Összegzés, következtetések . . . . . . . . . . . . . . . . . . . . . . . . 47 Összefoglalás

50

Summary

51

Köszönetnyilvánítás

52

Irodalomjegyzék

53

Függelék

54

3

Bevezetés Komplex rendszerek vizsgálatának elterjedt módja az, amikor a rendszer alkotóelemeit és a közöttük megfigyelhető kölcsönhatásokat hálózatként értelmezzük. A rendszer eredetétől függetlenül gyakran elegendő a kapott hálózat topológiájára koncentrálva tanulmányoznunk azt, hogy ismereteket szerezzünk jellemzőiről vagy viselkedéséről, legyen az akár emberek egy csoportja, tartályba zárt gázmolekulák, a világháló, esetleg egy sejt a szervezetünkben. Hálózatokat szokás egyszerű gráfokkal modellezni, mivel ezek matematikailag jól kezelhetőek, különböző mérhető jellemzőiknek meghatározására és elemzésére pedig számos eljárás ismeretes. Egy viszonylag gyakran vizsgált és jól mérhető jellemző a gráf csúcsainak központisága vagy centralitása, mely érték az eredeti hálózat jellegétől függően például az egyes csomópontok népszerűségeként, fontosságaként, relevanciájaként vagy esszencialitásaként fogható fel. A centralitás számszerűsítésére számos megközelítés létezik, a hálózattól és az elemzés céljától függően általában más és más mérték használata előnyös. A dolgozatban egy ilyen centralitás-mértéket, a PageRank1 eljárást vizsgálom. Bemutatom a probléma eredetét, majd a Markov-láncok alapjainak összefoglalása után levezetem a PageRank alapegyenletét. A probléma két megközelítésben is tárgyalható : sajátértékfeladatként és lineáris egyenletrendszerként. Megmutatom, hogy a megfelelő feltételek teljesülése esetén a módszer hatékonyan kezelhető mindkét megközelítésben. Kitérek arra az esetre, amikor a modellbe hibákkal terhelt adatok kerülnek, és becslést adok ezek hatására. Ahogyan látni fogjuk, megfelelő paraméterválasztással az eljárás stabilnak tekinthető. Végül nagyon röviden összefoglalom a fehérje-hálózatok probléma szempontjából leglényegesebb jellemzőit, és bemutatok egy PageRank-alapú módszert fehérje-fehérje interakciós hálózatok összehasonlítására. A dologzat további részében – témavezetőm javaslatára – PageRank helyett a magyarul természetesebben hangzó és beszédesebb PageRang elnevezést használom.

1

A PageRank szó a Google bejegyzett védjegye.

4

1. fejezet

Hálózati csomópontok centralitásának mérőszámai 1.1. A centralitás lehetséges értelmezései egy példán keresztül Egy hálózat csomópontjainak központiságát tekinthetjük úgy, mint relatív fontosság a teljes hálózatban. Ez a fontosság azonban a hálózat eredetétől és az elemzés céljától függően mást és mást jelenthet, így nem lehetséges egyetlen olyan központisági mértéket definiálni, amely minden hálózatban és minden kérdésre jól megragadná a csomópontok fontosságát. Ennek bemutatásához egy képzeletbeli számítógépes hálózat csomópontjainak központiságát elemezzük. Amint látni fogjuk, a „Melyik csomópont a legfontosabb ?” kérdésre többféleképpen is válaszolhatunk. Először mondjuk azt, hogy egy csomópont akkor fontos, ha sok kapcsolattal rendelkezik, hiszen ha egy ilyen hibásodik meg, akkor sok másik eszközzel szűnik meg a kommunikáció. Ekkor fokszám centralitás (degree centrality) alapján rangsoroljuk a csomópontokat, és az 1.1. (b) ábra 8 jelzésű pontja lesz a legfontosabb, a többiek jóval kisebb mérőszámokkal rendelkeznek. Most nevezzünk egy csomópontot fontosnak akkor, ha a többi ponttal gyorsan kapcsolatba tud lépni, azaz köztük a távolság viszonylag kicsi. Így közelség centralitás szerint osztályozunk, és ahogyan az 1.1. (c) ábrán látható, jóval egyenletesebbek a csomópontok mérőszámai, nehéz egyértelműen győztest hirdetni. Utolsó példaként hívjunk egy csomópontot fontosnak akkor, ha sok információ fut rajta keresztül, hiszen egy ilyen kiesése megbéníthatja a forgalmat. Ez közöttiség centralitás (betweenness centrality) alapján vizsgálja a pontokat. Az 1.1. (d) ábra szerint a legtöbb pont közöttiség centralitás mértéke elhanyagolhatóan kicsi, mindössze néhány pont játszik csak lényeges szerepet a hálózatban. A fenti példa mindössze néhány központiság mérőszámot mutatott be, talán mégis érzékelhető volt, mennyire eltérő válaszokat kaphatunk ugyanarra a kérdésre, ha azt nem kellően pontosan tesszük fel.

5

1

1

4

4

3

3

2

2

5

5

6

6

7

7

9

9 8

8

10

12 14

11 14

13

15

10

12

11

13

15 Pajek

Pajek

(a) A hálózat.

(b) Fokszám centralitás. 1

1

4

4

3

3

2

2

5

5

6

6

7

7

9

9 8 12

10

12

11 14

15

8

10

11 14

13

15

Pajek

13 Pajek

(c) Közelség centralitás.

(d) Közöttiség centralitás.

1.1. ábra. Képzeletbeli számítógépes hálózat különböző mértékek szerint ábrázolva.

6

1.2. Néhány központisági mérőszám Ebben a szakaszban Newman [8] művének felhasználásával röviden megvizsgálunk három, egymásból származtatható központisági mértéket, melyeknek közös vonása, hogy a centralitást a csúcs szomszédságának jellemzőire építve definiálják. A dolgozat lényegét képező PageRang ezek egyféle finomításaként fogható fel, mely számos előnyös tulajdonsága miatt eredményesebben alkalmazható a valóságban előforduló hálózatokra.

1.2.1. Fokszám centralitás Ahogyan az előző szakaszban már láthattuk, egy gráf csúcsainak központiságát gyakran kézenfekvő azok fokszámával mérni. Irányítatlan gráfok esetén ez minden csúcsra egyetlen, míg irányított gráfok csúcsaira kettő (be-fokszám és ki-fokszám) mérőszámot definiál, mely egyszerűsége ellenére gyakran igen szemléletes jelentéssel bír. Ismerettségi hálózatokban például felfoghatjuk úgy, hogy a sok kapcsolattal rendelkező egyének ismertebbek, vagy nagyobb hatással vannak a közösségre. Tudományos szakirodalomban egy összefoglaló jellegű cikk végén sok hivatkozást találunk a téma legfontosabb munkáira, így az ilyen cikkeknek magas a ki-fokszáma, ugyanakkor egy jelentős eredményt felmutató cikket várhatóan sok későbbi munka referenciái közt olvashatunk, ami magas be-fokszámot okoz. Amennyiben a hálózatot leíró gráf A szomszédsági mátrixával adott, akkor az i-edik csúcsának fokszám centralitása vi =

X

ATij .

j

Egyszerűsége mellett ennek a mértéknek megvan az a gyengesége, hogy a csúcs minden szomszédját egyenrangúként kezeli, ami a valóságban gyakran nem helytálló feltevés.

1.2.2. Sajátvektor centralitás Mivel egy csúcs szomszédai maguk is különbözőek lehetnek központiságukat tekintve, így logikusnak látszik, hogy a nagyobb és kisebb centralitású szomszédok szavazatait ne egyformán kezeljük. Definiáljuk egy csúcs centralitásának mérőszámát úgy, hogy az legyen arányos a szomszédai mérőszámainak összegével, vagyis vi = c

X

ATij vj

j

valamilyen c =

1 -tól függő arányossági tényezővel. Mátrixműveletekre átírva és rendezve λ

ez AT v = λv, tehát a csúcsok mérőszámaiből álló v vektor éppen az AT mátrix egyik sajátvektora λ sajátértékkel. Bizonyos feltételek teljesülése esetén a megfelelő sajátvektor egyértelmű, így valóban alkalmas a csúcsok mérőszámainak definiálására.

7

A sajátvektor centralitás értelmezhető a következőképp: egy csomópont magas központiságú lehet azért, mert nagyon sok alacsony központiságú kapcsolata van (például nagyon sok ismerőse van), de azért is, mert kevés, viszont magas központiságú kapcsolattal bír (például befolyásos ismerősei vannak). A módszer különösen irányítatlan gráfokon használható eredményesen, mivel azok szomszédsági mátrixa szimmetrikus. Irányított esetben is működik, azonban itt a jobb- és baloldali sajátvektorokból kapott mérőszámok más jelentést hordoznak. Ilyen gráfok esetén a legnagyobb probléma mégis az, hogy csak egy erősen összefüggő komponensben, vagy annak egy ki-komponensében lévő csúcsnak lehet nullától különböző sajátvektor centralitása. A valóságban megjelenő hálózatok nagy részére (úgymint a világháló vagy citációs hálózatok) viszont ettől eltérő topológiát mutatnak, így a sajátvektor centralitás a gyakorlatban kevéssé használható.

1.2.3. Katz-féle centralitás A sajátvektor centralitás említett hiányosságát korrigálhatjuk úgy, hogy minden csomópontnak a sajátján kívül adunk valamilyen kicsi pozitív ε mértéket, azaz vi = c

X

ATij vj + ε,

j

valamilyen pozitív c konstanssal. Ezt mátrixos alakra írva és átrendezve kapjuk a v = ε I − cAT


−1

e

egyenletet, ahol e egy megfelelő méretű, csupa egyesekből álló vektor. Mivel v elemeinek pontos értéke nem, csak egymáshoz való viszonya érdekes, így ε értéke tetszőlegesen megválasztható, például 1-nek. Ha c értékét nullához közeli értékre állítjuk, akkor minden csúcs centralitása majdnem azonos értékű lesz. A másik véglet, amikor c az λ1 értékhez közelít
(λ az AT mátrix legnagyobb sajátértéke), mivel ekkor I − cAT közel szinguláris. A Katz-féle centralitás hasonlít a sajátvektor centralitásra, de tartalmaz egy paramétert, melynek segítségével szabályozható a sajátvektor összetevő és a konstans összetevő aránya. Ez egyben kiküszöböli az irányított gráfoknál jelentkező korábbi problémát is, mivel c megválasztásától függően minden csúcs rendelkezni fog valamekkora központisággal. Az eljárásnak az előbb tárgyalt előnyei mellett megvan az a kellemetlen tulajdonsága is, hogy egy magas centralitású csúcs szomszédai mind magas centralitásúak lesznek, függetlenül azok számától. Ahogyan a következő fejezetben látni fogjuk, egy egyszerűbb módosítással ez megszüntethető, így eljutunk a PageRang centralitás fogalmához.

8

2. fejezet

Markov-láncok alkalmazása a PageRang problémára Képzeljünk el egy személyt, aki a weben szörfözik : elindul egy bizonyos oldalról, majd az azon található hivatkozások mentén egy másik oldalra navigál. Ott megint talál egy számára érdekes hivatkozást, melyen át ismét egy másik oldalra kerül, és így tovább. Egy idő után azonban elunja magát, és teljesen véletlenszerűen felkeres egy új weboldalt, ahonnan tovább folytatja az előbbi szörfözést. Sergey Brin, Lawrence Page és stanfordi hallgatótársai valahogy így képzelték el egy „sztochasztikus szörföző” viselkedését. Feltevésük szerint a weboldalakok elhelyezett hivatkozások egymáshoz kapcsolják a webet alkotó oldalakat, és ajánlásokként működnek. Ezt feltételezve a weben definiálható az egyes oldalak népszerűsége vagy fontossága : egy oldal fontos és ezáltal PageRang centralitása magas, ha arra fontos oldalakról mutat hivatkozás. Ez az előző fejezetben bemutatott módszerekhez hasonlóan egy rekurzív definíció, melyet egy végtelen szavazási folyamatként is elképzelhetünk. Kezdetben minden csúcspont ugyanakkora centralitással rendelkezik, majd a csúcsok minden lépésében egyenletesen szétosztják saját centralitásukat azok között a csúcsok között, melyekre a szavazataikat leadják, cserébe kaphatnak valamennyit a szavazóiktól. Ebből következően az i oldal fontosságát jellemző ci centralitás mérték most is iterációval számítható ki, értéke a k-adik lépésben az (k) ci

=

X c(k−1) j j:eji ∈E

|Fj |

(2.1)

képlettel definiálható, ahol |Fj | a j oldalon lévő hivatkozások száma, E pedig most is a hálózat irányított éleinek halmaza ([4] nyomán). Az előbbiek szerint a PageRang mérőszámra gondolhatunk úgy is, mint a csúcs szomszédsága között egyenletesen szétosztott központiságra, de úgy is, mint a gráf csúcsain történő véletlen bolyongás során előálló valószínűségeloszlásra. Ahogyan látni fogjuk, az utóbbi megközelítés könnyen tárgyalható Markov-láncokra építve, ezért a következőkben összefoglalom a leglényegesebb fogalmakat ennek elméletéből.

9

2.1. Markov-láncok és tulajdonságaik 2.1.1. Alapfogalmak 2.1.1. Definíció. Az {Xt }t∈N valószínűségi változókból álló halmazt diszkrét idejű sztochasztikus folyamatnak nevezzük. A folyamat lehetséges értékeiből álló S = {s0 , s1 , . . . , sn−1 } véges halmaz a folyamat állapottere. Esetünkben ésszerű az állapottérről feltételezni annak végességét, valamint azt, hogy a folyamat diszkrét idejű. A dolgozatban ezért csak diszkrét idejű és diszkrét (véges) állapotterű folyamatokat tárgyalunk. 2.1.2. Definíció. Az {Xt }t∈N folyamatot (elsőrendű) diszkrét idejű, diszkrét állapotterű Markov-láncnak nevezzük, ha minden t ∈ N pillanatban és tetszőlegesen választott s0 , . . . , st ∈ S állapotok esetén teljesül P (Xt+1 = st+1 | Xt = st , Xt−1 = st−1 , . . . , X0 = s0 ) = P (Xt+1 = st+1 | Xt = st ) . (2.2) A Markov-lánc tehát egy sztochasztikus folyamat, mely teljesíti a Markov-tulajdonságot: a folyamat jövőbeli állapota csak a jelenbelitől függ, a múltbeliek nincsenek hatással rá. Ez egyféle emlékezetnélküliséget fogalmaz meg, a folyamat „elfelejti”, hogy korábban milyen állapotokban járt. Természetesen a definíció általánosítható magasabb rendű láncokra is, egy m-edrendű lánc csak az előző m lépésre „emlékszik”. Gyakran szemléltetik a Markov-láncokat élsúlyozott, irányított gráfokkal, ahogyan az például a 2.1. ábrán látható. Ha a szörfözőről feltételezzük, hogy valóban minden oldalon véletlenszerűen, korábbi döntéseitől függetlenül határoz a következő meglátogatandó oldalról, akkor a felkeresett weboldalak indexeinek sorozata egy elsőrendű Markov-lánc lesz.

1

2 7

4 3

6

5

8

2.1. ábra. Egy Markov-lánc gráf reprezentációja. A 2.2 egyenlet jobboldalán álló feltételes valószínűség valamely t és t + 1 időpillanatban bekövetkező, si állapotból sj állapotba való közvetlen átmenet valószínűségét adja meg, melyre külön elnevezést is bevezetünk. 10

2.1.3. Definíció. A pij (t, t+1) = P (Xt+1 = sj | Xt = si ) mennyiségeket az s0 , s1 , . . . , sn−1 ∈ ∈ S állapotterű {Xt }t∈N Markov-lánc egylépéses átmenet-valószínűségeinek nevezzük. Az ezekből alkotott n × n méretű 

p11

p12

···

  p21 p22 · · ·  P= . .. ..  .. . .  pn1 pn2 · · ·

p1n



 p2n   ..  .   pnn

mátrixot a Markov-lánc egylépés átmenetvalószínűség-mátrixának nevezzük. Hasonlóan definiálható az a valószínűség, amely si és sj állapotok közötti m lépésből álló átmenet esélyét adja meg. 2.1.4. Definíció. Jelölje tetszőleges si , sj ∈ S és m ∈ N mellett (m)

pij (m)

ahol a pij

= pij (t, t + m) = P (Xt+m = sj | Xt = si ) ,

mennyiségeket a Markov-lánc m-lépéses átmenet-valószínűségeinek nevezzük.

Amennyiben m = 0, akkor (0)

pij

 1, ha i = j, = 0, ha i 6= j.

Az egylépéses átmenetvalószínűség-mátrix mintájára bevezethetjük a többlépéses átmenetvalószínűség-mátrixot is. Ennek a P(m) mátrixnak az ij-edik eleme éppen az előbb (m)

definiált pij

valószínűség.

A Markov-láncok számunka lényeges osztályát képezik azok, melyeknek előbb definiált átmenet-valószínűségei a t paraméter értékétől, vagyis az időtől függetlenek. Az ilyen Markov-láncokat homogénnek nevezzük. Feltételezzük azt, hogy a szörföző a lépéseinek számától függetlenül, az éppen rendelkezésre álló hivatkozások közül egyenlő valószínűséggel választ egyet. Bolyongása ekkor egy homogén Markov-lánc, melyet reprezentáló G(V, E) gráf egy vi ∈ V csúcsából vj ∈ V csúcsába húzott él súlya (a pij egylépéses átmenetvalószínűség) 1/ degki (vi ). Ezekkel a feltételezésekkel a 2.1. ábrán látható homogén Markov-lánc egylépéses átmenetvalószínűségmátrixa   0 0 0 0 0 0 0 0    1 0 0 0 0 0 0 0     0 0 0 1/2 1/2 0 0 0    0 0  1 0 0 0 0 0   P= . 0 0  1 0 0 0 0 0     0 1/3 1/3 0 0 0 0 1/3   0 0 0 0 0 1/2 1/2 0    0 0 0 0 0 0 1/2 1/2

11

Eddig azt feltételeztük, hogy a szörföző bolyongása egy véletlenszerűen kiválasztott si csúcsból indul, és a folyamat ettől függően fejlődik valahogyan. Megtehetjük azonban azt is, hogy kiindulásként nem egyetlen csúcsot adunk meg, hanem egy valószínűségeloszlást a csúcsokon. Az így kapott valószínűségeloszlást, vagyis a pi = P (X0 = si ) , (si ∈ S) eloszlást a Markov-lánc kezdeti eloszlásának nevezzük. Rendezzük ezeket a pi értékeket egy n hosszúságú π vektorba úgy, hogy π i = pi . A megadott kezdeti eloszlás, valamint a teljes valószínűség tételének segítségével megadhatjuk a folyamat t időpillanatbeli állapotainak eloszlását, vagyis a P (Xt = sj ) valószínűségeket minden sj ∈ S-re. P (Xt = sj ) =

X

P (Xt = sj | X0 = si ) P (X0 = si )

si ∈S

Az egyenlet jobboldala a t-lépéses átmenetvalószínűségek és a kezdeti eloszlás, valamint ezek vektoros és mátrixos alakjának felhasználásával felírható a X (t) X (t) pij pi = Pij π i si ∈S

i

formában.

2.1.2. Állapotok osztályozása A Markov-láncok vizsgálatakor gyakran a folyamat aszimptotikus tulajdonságaira vagyunk kíváncsiak. Az állapotok közötti kapcsolatokat elemezve előfordulhat, hogy bizonyos állapotok hasonlóan viselkednek, így együttesen vizsgálhatók, ezáltal a vizsgálat egyszerűbbé válik. 2.1.5. Definíció. Azt mondjuk, hogy az sj ∈ S állapot elérhető az si ∈ S állapotból, ha (m)

létezik olyan m ≥ 1 egész, melyre pij

> 0. Ha két si , sj állapot kölcsönösen elérhetők

egymásból, akkor az állapotpárt kapcsolódónak hívjuk. A kapcsolódás egy ekvivalencia-reláció (reflexív, szimmetrikus és tranzitív reláció) két állapot között, ami miatt az egymással kapcsolódó állapotok diszjunkt részhalmazokra, osztályokra bontják az állapotteret, és egy kapcsolódó pár azonos osztályhoz tartozik. Ha egy adott osztálybeli állapotból egy osztályon kívüli állapotba kerülés valószínűsége nulla, akkor az osztályt zártnak hívjuk. Az egyelemű zárt osztály neve elnyelő állapot. Ha egy S állapotterű Markov-lánc olyan tulajdonságú, hogy S egyetlen valódi részhalmaza sem zárt, akkor a folyamatra külön elnevezést használunk. 2.1.6. Definíció. Egy Markov-láncot irreducibilisnek hívunk, ha bármely állapot elérhető bármely más állapotból, azaz tetszőleges két si , sj ∈ S állapotok esetén létezik olyan m ≥ 1 (m)

egész, melyre pij

> 0.

A 2.1. ábrán látható Markov-láncot a kapcsolódó állapotok négy osztályra bontják: C1 = {1}, C2 = {2}, C3 = {3, 4, 5} és C4 = {6, 7, 8}. Ezek közül C1 és C3 zártak, előbbi speciálisan egy elnyelő állapot. 12

Vizsgáljuk most annak a valószínűségét, hogy a folyamat valamikor visszatér egy adott állapotba. Legyenek si , sj ∈ S most is tetszőleges állapotai a rendszernek, és vezessük be az alábbi jelöléseket: (0)

fij = 0, (1)

fij = P (X1 = sj | X0 = si ) , (n)

fij = P (Xn = sj , Xm 6= sj , ha m = 1, 2, . . . , n − 1 | X0 = si ) , (n)

A fenti fij

n = 2, 3, . . .

mennyiség tehát azt a valószínűséget adja meg, hogy az si állapotból (n)

induló folymat először n lépés után kerül az sj állapotba. Amennyiben i = j, úgy az fij

mennyiség az si állapotba n lépés alatt történő első visszatérés valószínűségét adja. Ennek segítségével egy másik szempont alapján is osztályozhatjuk egy Markov-lánc állapotait. 2.1.7. Definíció. Egy si ∈ S állapot visszatérő, ha ∞ X

(n)

fii = 1.

n=1

Ha egy állapot nem visszatérő, akkor átmenetinek nevezzük. Ha az összes állapot visszatérő, akkor a Markov-láncot visszatérőnek mondjuk. Ha egy állapot olyan, hogy az csak bizonyos k, 2k, 3k, . . . (k > 1 egész) lépés után térhet vissza, akkor periodikus állapotnak nevezzük. 2.1.8. Definíció. Jelölje tetszőleges si ∈ S állapot esetén d (i) azoknak az m ≥ 1 egészek(m)

nek a legnagyobb közös osztóját, melyekre pii

(m)

> 0. Ha pii

= 0 minden m ≥ 1-re, akkor

legyen d (i) = 0. Az így definiált d (i) számot az si állapot periódusának nevezzük. Egy Markov-láncot aperiodikusnak nevezünk, ha minden állapotának periódusa 1. Vizsgáljuk a folyamat visszatérő állapotainak várható visszatérési idejét. 2.1.9. Definíció. Az si ∈ S állapot visszatérési idejének várható értéke a µsi =

∞ X

(n)

nfii

n=1

mennyiség. Egy si ∈ S állapot visszatérő nemnullaállapot, ha µsi < ∞, és visszatérő nullaállapot, ha µsi = ∞.

2.1.3. Aszimptotikus tulajdonságok Az egyik legérdekesebb kérdés a szörföző viselkedését leíró Markov-lánccal kapcsolatban, hogy létezik-e egyensúlyi eloszlása a folyamatnak. Amennyiben létezik ilyen, akkor az megadja, hogy elég hosszú idő múltán melyik oldalon mekkora valószínűséggel találjuk meg a szörfözőt, így egyféle rangsorát kapjuk az oldalaknak (feltételezve, hogy egy fontosnak tartott oldalon valószínűbben találjuk). Először az egyensúlyi eloszlás fogalmát pontosítjuk. 13

2.1.10. Definíció. Egy π eloszlást stacionárius vagy egyensúlyi eloszlásnak nevezünk, ha kezdeti eloszlásnak választva tetszőleges t időpillanatban fennáll a π (t) = π egyenlőség. A következő tétel elégséges feltételt szolgáltat egyensúlyi eloszlás létezésére bizonyos típusú Markov-láncok esetén. 2.1.11. Tétel. (Michelberger et al., [7]) Legyen az {Xt }t∈N Markov-lánc homogén, irreducibilis és aperiodikus. (A) Ekkor tetszőleges si ∈ S állapot esetén létezik a (t)

π i = lim π i t→∞

határérték, amely nem függ a kezdeti eloszlástól. Ha minden állapot átmeneti, vagy visszatérő nullaállapot, akkor nem létezik stacionárius eloszlás, és π i = 0 minden állapotra. (B) Ha minden állapot visszatérő nemnullaállapot, akkor létezik, a π stacionárius eloszlás, melyet egyértelműen meghatároznak a következő egyenletek : X

π i = 1,

i

πj =

X

π i pij .

i

A tétel bizonyítását terjedelmi okok miatt nem tárgyalom, az megtalálható a jelölt forrásban 13.39. tétel néven.

2.2. PageRang levezetése Markov-láncokkal A 2.1.11. tétel garantálja az egyensúlyi eloszlás létezését egyes Markov-láncok esetén. Ez az egyensúlyi eloszlás (amennyiben nem azonosan nulla valószínűségekből áll) egyben arra is alkalmas, hogy segítségével sorrendbe rendezzük a Markov-lánc állapotait valószínűségek szerint. A (2.1) egyenletből kiindulva egy homogén, irreducibilis, aperiodikus Markov-láncot (egészen pontosan egy átmenetvalószínűség-mátrixot) konstruálunk, melynek az előbbiek szerint létezik stacionárius eloszlása. Az így kapott eloszlást értelemzzük a csúcsok PageRang mérőszámaiként.

2.2.1. A PageRang mátrixos alakja Egy G = (V, E) gráf szomszédsági (adjacencia) mátrixa a következő |V | × |V | méretű mátrix:

 1 ha eij ∈ E, Aij = 0 egyébként. 14

1

3

2

5

4

2.2. ábra. Egy öt csúcsból álló irányított hálózat gráfja. Ez súlyozatlan gráfokra irányítatlan és irányított esetben is egyszerűen használható, élsúlyozott esetben bizonyos megkötések szükségesek az egyértelműség biztosításához. A 2.2. ábrán látható irányított, élsúlyozatlan gráf szomszédsági mátrixa például  0  0   A = 0  0  0

1 0 0 0



 0 1 1 0   1 0 1 1 .  0 1 0 1  0 0 0 0

Definiáljuk egy irányított gráf hiperlink mátrixát, mely hasonló a szomszédsági mátrixhoz: Hi,j

 1/ deg (vi ) ha létezik vi -ből vj -be él, ki = 0 egyébként.

Ha a gráf n csúcsból áll, akkor ez egy n × n méretű nemnegatív elemekből álló mátrix lesz, melyben minden sor összege legfeljebb 1. Az ilyen típusú mátrixokra külön elnevezést vezetünk be. 2.2.1. Definíció. Egy négyzetes mátrixot szubsztochasztikusnak nevezünk, ha elemei nemnegatívak és minden sorának összege legfeljebb 1. Ha elemei nemnegatívak és minden sorának összege pontosan 1, akkor sztochasztikusnak nevezzük. A definíció szerint H szubsztochasztikus mátrix lesz. Például a 2.2. ábrán látható gráf esetén 

0

1

0

0

0



  0 0 1/2 1/2 0      H = 0 1/3 0 1/3 1/3 .   0 0 1/2 0 1/2   0 0 0 0 0

15

A (2.1) egyenlettel kiszámított ri rangokat rendezzük egy n hosszúságú π vektorba, a PageRang-vektorba. H és π segítségével az egyenlet a következőképp írható fel: π (k)T = π (k−1)T H. H hasonló egy egylépés átmenetvalószínűség-mátrixhoz, ami a szörföző bolyongását irányította az előző szakaszan. Elképzelhető azonban, hogy H tartalmaz teljes nulla sort, amit úgy értelmezhetünk, hogy ha a szörföző a sornak megfelelő állapotba lép, akkor azt többé nem hagyja el, tehát annak a valószínűsége, hogy t → ∞ esetén ebben az állapotban lesz, éppen 1. A jelenség neve Brin és Page [9] cikkében rank-sink (rang-süllyesztő), mely a rangsor szempontjából nem kívánatos, mivel az ilyen állapotok indokolatlanul kapnának magas pontszámot.

2.2.2. Első finomítás : visszatérőség A 2.1.11. tételben láttuk, hogy ha (egyebek mellett) a Markov-lánc állapotai mind visszatérő nemnullaállapotok, akkor létezik nemtriviális stacionárius eloszlás. Az előbb tárgyalt elnyelő állapotok azonban lehetetlenné teszik a többi állapot visszatérőségét, ezáltal a megfelelő stacionárius eloszlás létezését is. Brin és Page úgy oldották meg ezt a problémát, hogy a H mátrixot sztochasztikussá tették az azonosan nulla sorok elemeit 1/n elemekre cserélésével, így kapva egy S mátrixot. Ekkor ha az S átmenetmátrixú szörföző elnyelő állapotba kerül (vagyis olyan oldalra jut, melyről nem mutat más oldalra link), akkor véletlenszerűen ugorhat tetszőleges állapotba. Matematikailag ez a változtatás a következőképp írható le az előző szakasz jelöléseit felhasználva. Legyenek az n hosszú d vektor1 elemei  1 ha si elnyelő állapot, di = 0 egyébként.

(2.3)

Jelölje a továbbiakban e a csupa egyesekből álló n-hosszú vektort, ekkor S=H+

1 T de , n

(2.4)

vagyis S a H és az egy rangú deT mátrix kombinációjaként áll elő. Az így kapott mátrix definíció szerint sztochasztikus lesz, példánkban   0 1 0 0 0    0 0 1/2 1/2 0      S =  0 1/3 0 1/3 1/3 .    0 0 1/2 0 1/2   1/5 1/5 1/5 1/5 1/5 1

Brin és Page azokat az oldalakat, melyekről nem mutat más oldalra hivatkozás, dangling node-nak („lógó csúcsnak”) nevezte.

16

2.2.3. Második finomítás : irreducibilitás Egy S átmemetmátrixú Markov-láncnak még nem feltétlenül létezik stacionárius eloszlása, mivel rendelkezhet több elemű zárt osztályokkal, vagyis nem feltétlenül irreducibilis. Ez azonban igen könnyedén elérhető a következő módosítással. Ahogyan az előző fejezetben utaltunk rá, tételezzük fel, hogy a szörföző bizonyos számú kattintás után megunja a hivatkozásokon keresztüli navigációt, és felkeres egy véletlenszerű oldalt, mintegy teleportálva arra. Ezzel a képességgel a bolyongását leíró Markov-lánc átmenetmátrixát a következő G márixra módosítja: G = cS + (1 − c)E,

(2.5)

ahol E = evT képlettel definiált egy rangú mátrix, v pedig egy valószínűségeloszlást reprezentáló n-hosszú vektor. Álljon az egyszerűség kedvéért v most azonosan 1/n elemekből. A c egy valós paraméter, melyre 0 < c < 1. Ennek hatását úgy képzelhetjük el, hogy a szörföző összidejének c-edrészében az oldalakon található hivatkozásokat követve navigál, de (1 − c)-edrészében véletlenszerűen ugrik egy új oldalra. Az E mátrixot épp ezért teleportációs mátrixnak szokás hívni, ugyanis épp a web egyes oldalaira történő véletlen ugrás valószínűségeit tartalmazza. G ugyancsak sztochasztikus mátrix lesz, hiszen két sztochasztikus mátrix konvex kombinációjaként áll elő. Mivel így tetszőleges si , sj ∈ S állapotok esetén a két állapot biztosan kapcsolódó, ezért a G átmenetvalószínűség-mátrixú Markov-lánc irreducibilis.

2.2.4. Harmadik finomítás : aperiodicitás Az előbb bevezetett G mátrix egyben az aperiodicitás problémáját is megoldja, ugyanis a teleportációs mátrix bevezetésével tetszőleges állapotból egy lépéssel önmagába is lehet kerülni pozitív valószínűséggel. Ezáltal az állapottér minden si állapotának a periódusa 1, vagyis a Markov-lánc aperiodikus. A fentiek következményeképp a finomítások elvégzésével kapott G átmenetvalószínűségmátrixú Markov-láncnak a 2.1.11. tétel szerint létezik π = 0-tól különböző stacionárius eloszlása, melyet az ott leírt egyenletek egyértelműen meghatároznak.

2.2.5. Egyszerű példa PageRang kiszámítására 2.2.2. Példa. Számítsuk ki a 2.2. ábrán lévő hálózat csúcsainak PageRang-jait. Tételezzük fel, hogy a modellben bemutatott szörföző idejének 85%-ában irányított éleket követve navigál, 15%-ában pedig véletlenszerűen ugrik, vagyis c = 0.85. A bolyongását leíró

17

Markov-lánc átmenetvalószínűség-mátrixa ekkor (kerekített értékekkel)  0.03  0.03   G = 0.03  0.03  0.2

0.88 0.03 0.03 0.03



 0.03 0.46 0.46 0.03   0.31 0.03 0.31 0.31 .  0.03 0.46 0.03 0.46  0.2 0.2 0.2 0.2

Nézzük meg, hogyan alakulnak a π (k) vektor elemei néhány iterációs lépés után attól függően, hogy a kezdeti eloszlás egyenletes, teljesen egyenlőtlen, vagy véletlenszerű volt. (k)T

π1

k

(k)T

π2

(k)T

π3

0

(0.20 0.20 0.20 0.20 0.20)

(0.00 0.00 0.00 0.00 1.00)

(0.61 0.03 0.24 0.04 0.08)

1

(0.06 0.29 0.23 0.21 0.21)

(0.03 0.31 0.03 0.31 0.31)

(0.04 0.63 0.07 0.12 0.13)

2

(0.07 0.19 0.28 0.26 0.22)

(0.08 0.12 0.35 0.23 0.23)

(0.05 0.11 0.37 0.34 0.13)

3

(0.07 0.20 0.25 0.22 0.25)

(0.07 0.24 0.21 0.22 0.27)

(0.05 0.20 0.24 0.20 0.30)

4

(0.07 0.20 0.25 0.23 0.24)

(0.08 0.19 0.27 0.24 0.23)

(0.08 0.19 0.25 0.24 0.24)

Látható, hogy viszonylag gyorsan csillapodnak a kezdeti eloszlás miatti különbségek. Az egyensúlyi eloszlást megadó vektor egyébként a π T = (0.07 0.20 0.26 0.23 0.24), melyhez mindhárom kezdeti eloszlásból kiindulva egészen közel kerültünk csupán 4 lépés alatt. A π PageRang vektor i-edik elemének értékét valószínűségként is képzelhetjük, ami azt mondja meg, hogy hosszú távon mekkora eséllyel tartózkodik épp a gráf i-edik csúcsában a szörföző. Példánkban az 1-es csúcsban tartózkodás esélye nagyjából 7%, ezzel szemben a 3-asban mintegy 26%, tehát ésszerű feltételeznünk, hogy a 3-as csúcs valamiért népszerűbb az 1esnél. A kapott valószínűség-értékek alapján a 2.2. ábrán látható gráf csúcsaira a következő rangsor adódik: (5 4 1 3 2), vagyis a legnépszerűbb csúcs a 3-as, őt követi az 5-ös, majd 4-es, 2-es, és végül az 1-es. A következő fejezetben megvizsgáljuk, milyen módon számítható ki hatékonyan az egyensúlyi eloszlás, egyes módszerek esetén mekkora pontosságot várhatunk el, illetve mennyire gyorsan terjednek a hibák, ha eredeti adatainkban feltételezzük ezek jelenlétét.

18

3. fejezet

A PageRang kiszámítása, paraméterei és stabilitása 3.1. Numerikus módszerek néhány alapfogalma A fejezetben tárgyalt problémák jelentős része vektor- és mátrixműveleteken alapul, így szükséges lesz néhány fogalom és állítás, hogy a vektorokat és mátrixokat bizonyos, azokat jól jellemző mennyiségi tulajdonsággal elláthassuk, valamint eltéréseiket számszerűsíteni tudjuk. A szakaszban szereplő definíciókat és tételeket [1] alapján foglaltam össze.

3.1.1. Normák 3.1.1. Definíció. Egy V vektorteret normált térnek nevezünk, ha létezik olyan d : V 7→ R leképezés, melyre 1. d(v) ≥ 0 és d(v) = 0 ⇔ v = 0 minden v ∈ V -re, 2. d(cv) = |c| d(v) tetszőleges v ∈ V -re és c skalárra, valamint 3. d(u + v) ≤ d(u) + d(v) minden u, v ∈ V esetén. Az így definiált d(v) leképezést a v ∈ V elem normájának hívjuk, és általában kvk-val jelöljük. A definíció feltételeti teljesítő leképezés többféleképpen is megadható. Általánosan az n hosszú v vektor p-normáján a kvkp =

n X

!1/p |vi |p

i=1

értéket értjük. Legáltalánosabb ilyen norma a 2-es (vagy euklideszi) norma, a PageRang probléma tárgyalása során azonban többször is hasznosnak bizonyul az 1-es norma (vagy rácsnorma, Manhattan-norma), illetve a ∞-norma (maximumnorma). 19

Vektorok normáinak felhasználásával definiálhatjuk mátrixok normáit is az alábbi módon. kAkp = sup

kAxkp kxkp

x6=0

Az így definiált mennyiséget a p-vektornorma által indukált mátrixnormának nevezzük. Belátható, hogy a fenti mennyiség valóban teljesíti a normáktól elvárt tulajdonságokat. A számunkra hasznosnak bizonyuló 1-es és ∞-normákat közvetlenül A elemeinek segítségével is felírhatjuk (ezek levezetése megtalálható például [1]-ben): kAk1 = max

m X

j=1,...,n

illetve kAk∞ = max

i=1,...,m

|aij |,

i=1 n X

|aij |,

j=1

melyek miatt oszlopösszeg-, illetve sorösszegnormának is szokás őket hívni. Azt mondjuk, hogy egy k·kv vektornorma kompatibilis egy k·km mátrixnormával, ha tetszőleges A négyzetes mátrixra teljesül kAxkv ≤ kAkm kvkv .

3.1.2. Sajátértékek és sajátvektorok 3.1.2. Definíció. Egy λ skalárt az A mátrix (jobboldali) sajátértékének nevezünk, ha létezik olyan v nemnulla vektor, melyre Av = λv. A v vektort ekkor a λ-hoz tartozó (egyik) sajátvektornak mondjuk. Ezzel analóg módon értelmezhető egy mátrix baloldali sajátértéke és sajátvektora is, melyek a PageRang probléma tárgyalása során gyakran előkerülnek majd. Egy A mátrix sajátértékeiből álló halmazt a mátrix spektrumának hívunk, és σ(A)val jelölünk. A max {|λ| : λ ∈ σ(A)} mennyiséget a mátrix spektrálsugarának nevezzük, és ρ(A)-val jelöljük. Sztochasztikus mátrixok spektrálsugarára fennáll az alábbi egyenlőség, melyet a későbbiekben felhasználunk. 3.1.3. Állítás. Ha A sztochasztikus mátrix, akkor spektrálsugara ρ(A) = 1. Bizonyítás. A sztochasztikus mátrix definíciója szerint A minden sorösszege 1, tehát λ1 = = 1 valóban sajátértéke a mátrixnak. Annak igazolásához, hogy ennél nagyobb sajátértéke nincs, tegyük fel, hogy λm A legnagyobb abszolútértékű sajátértéke, vagyis ρ(A) = |λm |. Legyen xm a hozzá tartozó sajátvektor, valamint k·kv az k·km mátrixnormával kompatibilis vektornorma. Ekkor ρ(A) kxm kv = |λm | kxm kv = kλm xm kv = kAxm kv ≤ kAkm kxm kv , 20

melyből ρ(A) ≤ kAkm következik tetszőleges mátrixnormára. Legyen m = ∞, ekkor ugyanis kAk∞ = max i

X

aij = 1,

j

mivel A sztochasztikus. Ezzel az állítást igazoltuk.



A 3.2.1. tétel bizonyításánál felhasználjuk a következő állítást. 3.1.4. Állítás. (Parseval-egyenlőség) Ha v1 , v2 , . . . , vn a Cn tér egy 2-es normában ortonormált bázisa, akkor tetszőleges x = α1 v1 + α2 v2 + · · · + αn vn esetén kxk22 =

n X

|αi |2 .

i=1

Bizonyítás. Írjuk fel az x vektor transzponált konjugáltjának önmagával vett skaláris szorzatát, amely épp x euklideszi normájának négyzete. A vi vektorok páronkénti merőlegességéből és normáltságából következően kxk22

H

= hx, xi = x x =

n X

! αi v H i

i=1

n X i=1

! αi vi

=

n X

|αi |2 ,

i=1



mely igazolja az állítást.

3.1.3. Hibák és kondíciószámok Egy fizikai vagy mérnöki probléma megoldásán gyakran a jelenség alapján felállított matematikai modell számítógépes eljárással kapott megoldását értjük. Ebben az esetben a felállított modellbe (számítási eljárásba) adatokat táplálunk, műveleteket végzünk velük, majd megkapunk egy végeredményt. Azoban a módszer jellegéből adódóan ez általában nem az elméletben kinyerhető, tökéletesen pontos x érték, hanem annak egy x ˜ közelítése lesz. A két érték abszolút eltérését, vagyis az |x − x ˜| mennyiséget az x ˜ közelítés abszolút |x − x ˜| mennyiséget pedig relatív hibájának nevezzük. Ezeknek egy-egy felső hibájának, az |x| korlátját a megfelelő hibakorlátnak hívjuk. Az előbb leírt folyamat esetén többféle hibalehetőség adott. Ha már a bemenő adatokat is pontatlanul tudjuk csak mérni, akkor hozott hibáról beszélünk. A bemenő adatokat a számítógép általában lebegőpontos számként ábrázolja, ezzel is elkövetve valamekkora kerekítési hibát, e kettő összessége a kiindulási hiba. Az alkalmazott számítási módszerből adódó hibát képlethibának nevezzük, az eddigi hibákat összességében pedig végső hibának. Fontos tisztában lennünk azzal, hogy a hibalehetőségek függvényében mekkora pontosságú eredményt várhatunk el egy számítástól. Hogy ezt valahogyan számszerűsíthessük, vegyük a számítás során előálló végső hiba és a számítás kezdetén meglévő abszolút kiindulási hiba hányadosának lehetséges legnagyobb értékét, melyet a számítás abszolút kondíciószámának nevezünk.

21

Gyakran előforduk, hogy az abszolút végső hiba az abszolút kiindulási hiba lineáris függvényével becsülhető, vagyis |f (x) − f (˜ x)| ≤ L |x − x ˜| , ahol x és x ˜ a pontos kiindulási adat és annak egy (hibával terhelt) közelítése, f (x) és f (˜ x) a számítás során előálló pontos- és közelítő végeredmények, L pedig egy kiindulási adatoktól független konstans. Ekkor L egyben a számítás abszolút kondíciószáma is. A korábban említett fizikai vagy mérnöki problémák egy része lineáris egyenletrendszerrel modellezhető matematikailag. Nézzük meg egy példán keresztül, milyen hatása lehet a kiindulási hibáknak. 3.1.5. Példa. Vizsgáljuk az alábbi egyenletrendszereket. ! ! ! ! ! 7 430 437 x1 7 430 x1 = és = 2 123 x2 125 2 122.9 x2

437

!

125

A két egyenletrendszer csak az együtthatómátrix egyetlen elemében különbözik, mindösszesen 0.08%-ban. Azt feltételezhetnénk, hogy a két egyenletrendszer megoldásai is csak alig fognak különbözni, ám az első egyenletrendszer megoldása x = (1, 1)T , a másodiké viszont x ≈ (−142.33, 3.33)T . Vizsgáljuk meg általánosabban, mi okozta a nagymértékű eltérést. Elsőként tegyük fel, hogy az Ax = b egyenletrendszer megoldását keressük, azonban a pontos b vektor nem áll rendelkezésünkre, csak egy b + δb közelítése. Ekkor nyilván az eredményvektornak is csak egy x + δx közelítését kaphatjuk a számítás eredményééül. Az egyenletrendszer alakja ekkor A(x + δx) = b + δb. A inverzével balról szorozva kapjuk, hogy x + δx) = A−1 (b + δb) x + δx = A−1 b + A−1 δb x + δx = x + A−1 δb δx = A−1 δb, amiből



kδxk = A−1 δb ≤ A−1 kδbk következik valamilyen normában. Az abszolút kondíciószám definíciójából következően en

nek a számítási eljárásnak az abszolút kondíciószáma A−1 . Hasonlóan kaphatunk felső becslést a számítás relatív kondíciószámára is :

−1



A δb

kδbk kAk A−1 δb kAk A−1 kδbk kδxk = = ≤ = kAk A−1 . kxk kxk kAk kxk kbk kbk

22



3.1.6. Definíció. Legyen A reguláris mátrix. Ekkor a cond p (A) = kAkp A−1 p számot a mátrix kondíciószámának hívjuk. Egy feladat kondíciószáma szemléletesen azt adja meg, hogy ha a bemenő adatok 1%os eltérése a végeredmény hány százalékos eltérését okozza. Látható, hogy a kondíciószám értéke függ a választott mátrixnormától, azonban értéke nem lehet 1-nél kisebb. Nagy kondíciószám esetén azonban már viszonylag kicsinek tűnő kiidnulási hiba is jelentős eltéréshez vezethet a végeredményben. Visszatérve a 3.1.5. példára, a második együtthatómátrix közel szinguláris, ebből következően kondíciószáma nagy (≈ 6 · 105 euklideszi normában), így érthető a két egyenletrendszer megoldásvektorainak jelentős eltérése. Most tegyül fel, hogy az egyenletrendszer együtthatómátrixának elemei terheltek viszonylag kicsi hibával. 3.1.7. Tétel. (Faragó–Horváth, [1]) Legyen A = I + X alakú valós mátrix, ahol kXk = q < 1 valamilyen normában. Ekkor A reguláris és

−1

A ≤

1 . 1−q

Bizonyítás. Legyen x egy tetszőleges, megfelelő méretű vektor. Ekkor Ax = (I + X) x Ax − Xx = x kAx − Xxk = kxk kAxk + kXxk ≥ kAx − Xxk = kxk . Az egyenlőtlenségből következően kAxk ≥ kxk − kXxk ≥ kxk − kXk kxk = (1 − kXk) kxk = (1 − q) kxk . Ebből látható, hogy x 6= 0 választás esetén Ax 6= 0, tehát A valóban reguláris. Emiatt invertálható, és inverzének valamely normája definíció alapján

−1

−1

A = sup A y . kyk y6=0 Legyen most éppen y = Ax, ekkor

−1 kxk 1

A = sup kxk ≤ = . kxk (1 − q) 1−q x6=0 kAxk



3.1.8. Tétel. (Faragó–Horváth, [1]) Legyen A reguláris, valós mátrix, és tegyük fel,

hogy A−1 δA < 1 teljesül valamilyen normában. Ekkor az A + δA mátrix is reguláris, és

−1 (A + δA)

≤

−1

A . 1 − kA−1 δAk

A tétel bizonyításához először belátunk egy lemmát. 23

3.1.9. Lemma. Az A + δA mátrix inverze (A + δA)−1 = I + A−1 δA


−1

A−1 .

Bizonyítás. A mátrixokra vonatkozó szorzási- és inverzképzési tulajdonságok alapján
−1 (A + δA)−1 = AA−1 A + AA−1 δA =

−1 = A A−1 A + A−1 δA =

−1 = A I + A−1 δA =
−1 −1 = I + A−1 δA A .



A 3.1.8. tétel bizonyítása. Mivel A−1 δA < 1 feltevés szerint teljesül, ezért a 3.1.7. tétel szerint az I + A−1 δA mátrix reguláris. Felhasználva a 3.1.9. lemmát adódik, hogy




−1 −1
−1



−1 −1 −1 = ≤ (A + δA) I + A δA A I + A δA





A−1 . Végül szintén a 3.1.7. tétel alapján


−1

I + A−1 δA ≤ tehát valóban

−1 (A + δA)

≤

1 , 1 − kA−1 δAk

−1

A . 1 − kA−1 δAk



A fejezetben felhasznált legfontosabb fogalmak és állítások után rátérünk a dolgozat egyik tárgyára, a PageRang probléma kiszámításának tárgyalására.

3.2. A PageRang mint sajátérték-feladat A PageRang feladat előző fejezetben felírt mátrixos alakjában lényegében egy sajátértékprobléma: keressük a G mátrix 1 sajátértékhez tartozó π baloldali domináns sajátvektorát, melyben az elemek összege 1, vagyis π T = π T G, π T e = 1.

(3.1)

Brin és Page eredetileg egy iterációs folyamatként kezelte a problémát, a PageRangvektort jobbról szorozgatva egy mátrixszal, majd a kapott eredményt normalizálva végezte annak kiszámítását. Ez lényegében a hatványmódszer nevű eljárással egyezik meg, melyet történeti okokból, valamint a módszer egyszerűsége és eredményessége miatt tárgyalunk.

3.2.1. A hatványmódszer Tételezzük fel, hogy az A ∈ Rn×n mátrixnak van egy egyszeresen domináns sajátértéke, λ1 , vagyis a |λ1 | > |λ2 | ≥ |λ2 | ≥ · · · ≥ |λn | egyenlőtlenség fennáll. Ebből következően λ1 valós, máskülönben λ1 komplex konjugáltja is sajátérték lenne, ami ellentmondana a feltételezésnek, mivel abszolútértékük megegyezik. 24

Tegyük fel, hogy A diagonalizálható. Ekkor létezik n független sajátvektora, v1 , v2 , . . . , vn , melyek az Rn tér egy bázisát alkotják. Alkalmas α1 , . . . , αn skalárok segítségével egy y(0) vektor kifejezhető ezek lineáris kombinációjaként, vagyis y(0) = α1 v1 + α2 v2 + · · · + αn vn . Az egyenlet mindkét oldalát balról szorozva az A mátrix k-adik hatványával kapjuk, hogy Ak y(0) = Ak (α1 v1 + α2 v2 + · · · + αn vn ) = = α1 Ak v1 + α2 Ak v2 + · · · + αn Ak vn = = α1 λk1 v1 + α2 λk2 v2 + · · · + αn λkn vn =  k  k ! λ λn 2 = λk1 α1 v1 + α2 v 2 + · · · + αn vn . λ1 λ1

(3.2)

Feltételezésünk szerint λ1 domináns, ami miatt a zárójelben lévő tagok az első kivételével nullához tartanak, amint k → ∞. Ezt úgy értelmezhetjük, hogy k növelésével az Ak y(0) vektor egyre inkább v1 irányába fog mutatni. λ1 -től függően előfordulhat, hogy a keletkező vektor hossza nullához vagy végtelenhez tart, ezért célszerű minden lépésnél normálni. Hatványmódszer alatt az alábbi iteráció eredményeként előálló vektorsorozatot értjük. Kiindulásként legyen y(0) olyan vektor, mely nem merőleges a fenti v1 sajátvektorra,

továbbá y(0) 2 = 1. A k-adik iterációs lépésben (k = 1,2, . . . ) legyenek x(k) = Ay(k−1) ,



y(k) = x(k) / x(k) ,

(3.3)

2

λ(k) = y(k)T Ay(k) . Az így előálló y(k) vektor a domináns sajátvektorhoz (vagy annak −1-szereséhez), λ(k) pedig a hozzá tartozó sajátértékhez közelít, melyet a következő tétel garantál. 3.2.1. Tétel. (Faragó–Horváth, [1]) Legyen az A diagonalizálható mátrix egyszeresen domináns sajátértéke λ1 , a hozzá tartozó sajátvektor pedig v1 . Ekkor a (3.3) iteráció által előállított sorozatokra az alábbiak teljesülnek. Ak y(0)

(A) y(k) =

Ak y(0) , 2 (B) lim λ(k) = λ1 , k→∞

(C) létezik olyan (γk ) valós sorozat, hogy |γk | = 1 (k = 1,2, . . . ) és lim γk y(k) = v1 . k→∞

Bizonyítás. A tétel (A) állítása teljes indukcióval igazolható. Ellenőrizzük először k = 1-re. x(1) Ay(1−1) A1 y(0)

=

=

y(1) =

x(1)

Ay(1−1)

A1 y(0) 2 2 2

25

Tegyük fel, hogy az állítás igaz valamilyen k − 1-re. Ekkor k−1 (0)

y(k)

k (0)

A y A AAk−1 yy(0) k k2 kAk−1 y(0) k2 x(k) Ay(k−1) Ak y(0)

=

=

=

= =

x(k)

Ay(k−1)

Ak y(0) , kAk y(0) k2

A Ak−1 y(0) 2 2 2

kAk−1 y(0) k kAk−1 y(0) k2 2 2

tehát az állítás teljesül k-ra is. A (C) állítás igazolásához legyen most is y(0) = α1 v1 + α2 v2 + · · · + αn vn és α1 6= 0. Ekkor a tétel (A) pontja és az Ak y(0) -ra felírt korábbi összefüggés valamint a 3.1.4. állítás alapján   k   k λ2 α1 v1 + α2 λ1 v2 + · · · + αn λλn1 vn qP = = n 2k 2 i=1 |λi | |αi |   k  k  α 2 λ2 α n λn k λ1 α1 v1 + α1 λ1 v2 + · · · + α1 λ1 vn r = . Pn λi 2k αi 2 k |λ1 | |α1 | 1 + i=2 λ1 α1 λk1

y(k)

Az egyenletet átrendezve a k

|λ1 | |α1 | (k) y = λk1 α1

v1 +

 k v2 + · · · + ααn1 λλn1 vn r P 2k 2 1 + ni=2 λλ1i αα1i

α2 α1



λ2 λ1

k

összefüggést kapjuk. Vezessük be a γk =

|λ1 |k |α1 | λk1 α1

jelölést. Ekkor |γk | = 1, valamint a feltételek miatt a jobboldal számlálója v1 -hez, nevezője pedig 1-hez tart k → ∞ esetén, tehát a tétel (C) állítását igazoltuk. A (B) állítás igazolásához használjuk fel, hogy limk→∞ γk y(k) = v1 , tehát fennáll a     T  lim γk y(k) A γk y(k) = lim γk2 y(k)T Ay(k) = vT1 Av1 k→∞

k→∞

összefüggés. Mivel |γk | = 1, valamint a módszer alapján λ(k) = y(k)T Ay(k) , ezért   lim γk2 y(k)T Ay(k) = lim λ(k) = vT1 Av1 = λ1 , k→∞

k→∞



amivel igazoltuk az állítást.

3.2.2. A hatványmódszer alkalmazhatósága a G mátrixra Több oldalról is érdemes megvizsgálnunk a 3.2.1. tételt, amely a hatványmódszer konvergenciáját biztosítja. A tételben feltettük, hogy az A mátrix rendelkezik egy egyszeresen domináns sajátértékkel, valamint diagonalizálható. Ez azonban nem teljesül tetszőleges mátrixra, így előfordulhatna, hogy a PageRang problémára sem alkalmazható. 26

3.2.2. Definíció. Egy A mátrixot pozitívnak nevezünk, ha minden aij elemére aij > 0 teljesül. A (2.5) képlet alapján látható, hogy G pozitív mátrix, és ebben az esetben teljesül rá a következő tétel. 3.2.3. Tétel. (Perron tétele egyszeres és domináns sajátértékre) Ha A pozitív mátrix, melynek spektrálsugara λ1 = ρ(A), akkor (A) λ1 egyszeres sajátértéke A-nak, (B) λ1 domináns, azaz minden további λi sajátértékre |λi | < λ1 . A tétel bizonyítását terjedelmi okok miatt nem tárgyaljuk, az megtalálható [11]-ben 12.2. tétel néven. A 3.1.3. állítás alapján G spektrálsugara 1, vagyis Perron tétele szerint ez egy egyszeres és domináns sajátérték. Azonban még mindig előfordulhat, hogy G nem diagonalizálható. Bizonyos esetekben azonban ez sem szükséges feltétel a hatványmódszer konvergenciájához. Vizsgáljuk ismét a (3.2) összefüggést. Ahogyan korábban láttuk, az Ak y(0) vektor iránya k kövelésével a domináns sajátvektor irányához közelít. Tetszőlegesen nagy k-ra akkor létezik határértéke ennek a vektorsorozatnak, ha Ak -nak létezik határértéke, vagyis a hatványmódszer alkalmazhatósága lényegében ennek a határértéknek a létezésétől függ. A következő állítás biztosítja, hogy a G mátrix esetén a hatványmódszer valóban alkalmazható, és a helyes megoldást szolgáltatja. 3.2.4. Állítás. Ha egy A mátrixra ρ(A) < 1, vagy ha ρ(A) = 1 és λ1 egyszeresen domináns sajátérték, akkor létezik a limk→∞ Ak határérték. Az állítás levezetése megtalálható [6]-ban 7.10.33 jelöléssel, a dolgozatban nem tárgyaljuk.

3.2.3. A hatványmódszer konvergenciasebessége Nem elhanyagolható szempont az sem, hogy amennyiben a hatványmódszer konvergens, úgy hány iterációs lépés után várhatjuk, hogy egy előre megadott hibánál kisebb eltéréssel sikerült közelítenünk a valódi sajátvektort. A (3.2) összefüggés levezetéséből látható, hogy a módszer konvergenciája a |λ2 | / |λ1 | hányadostól, tehát lényegében a λ2 sajátértéktől függ. Amennyiben ez az érték kicsi λ1 = 1-hez viszonyítva, úgy gyakorlatban is használható módszert kapunk G domináns sajátvektorának kiszámítására. A következő tétel a λ2 sajátértékre ad korlátot. 3.2.5. Tétel. (Kamvar–Haveliwala, [2]) Legyen S egy n × n-es sztochasztikus mátrix, továbbá c ∈ (0,1) valós szám. Legyen E az az n × n-es egy rangú sztochasztikus mátrix, melyet az E = evT egyenlőség definiál, ahol e csupa egyesekből álló n hosszú vektor, v pedig egy valószínűségeloszlást reprezentáló n hosszú vektor. 27

Definiáljuk a G mátrixot a következőképpen: G = (cS + (1 − c)E)T . Ekkor G második sajátértéke |λ2 | ≤ c. A tételt egymásra épülő lemmákkal bizonyítjuk. 3.2.6. Lemma. A G mátrix második sajátértéke |λ2 | < 1. 

Bizonyítás. A lemma állítása közvetlenül adódik a 3.2.3. tétel (B) állításából.

3.2.7. Lemma. A G mátrix x2 második sajátvektora merőleges az e vektorra, azaz eT x2 = 0. Bizonyítás. A lemma állításának igazolásához előbb megmutatjuk, hogy ha xi a G mátrix λi sajátértékhez tartozó sajátvektora, valamint yj a GT mátrix λj sajátértékhez tartozó sajátvektora, akkor xi T yj = 0, ha λi 6= λj . Induljunk ki a sajátvektorok definíciójából: Gxi = λi xi GT yj = λj yj . Vegyük az utóbbi egyenlőség mindkét oldalának transzponáltját, majd szorozzuk meg xi vel jobbról: yj T Gxi = λj yj T xi .

(3.4)

Most szorozzuk meg az első egyenlőség mindkét oldalát yj T -tal balról : yj T Gxi = λi yj T xi .

(3.5)

Vonjuk ki (3.5)-ből (3.4)-et, majd vegyük az oldalak transzponáltjait, ekkor a 0 = (λi − λj ) xi T yj összefüggést kapjuk. Mivel feltevésünk szerint λi 6= λj , ez csak akkor teljesül, ha xi T yj = 0. A 3.2.6. lemma alapján |λ2 | < |λ1 |, tehát az előzőek szerint G második sajátvektora, x2 merőleges GT első sajátvektorára. GT definíciójából következően egy sztochasztikus mátrix, vagyis domináns sajátvektora az e vektor, ezért x2 T e = eT x2 = 0, ami bizonyítja 

a lemma állítását. 3.2.8. Lemma. ET x2 = 0.

Bizonyítás. Definíció szerint E = evT , tehát ET = veT . Ekkor ET x2 = veT x2 , vagyis a 3.2.7. lemma alapján valóban ET x2 = 0.



3.2.9. Lemma. A G mátrix x2 második sajátvektora az ST mátrixnak egy γi = λ2 /c sajátértékhez tartozó yi sajátvektora.

28

Bizonyítás. A sajátvektor definíciója és a G mátrix megadása alapján Gx2 = λ2 x2 (cS + (1 − c)E)T x2 = λ2 x2 cST x2 + (1 − c)ET x2 = λ2 x2 . A 3.2.8. lemmát felhasználva kapjuk, hogy cST x2 = λ2 x2 . Mivel c 6= 0, ezért eloszthatjuk vele az egyenlőség mindkét oldalát : ST x 2 =

λ2 x2 . c

Vezessük be az x2 = yi és γi = λ2 /c jelöléseket, melyekkel ST y i = γ i y i . Tehát az yi = x2 vektor valóban az ST mátrix egy sajátvektora, mégpedig γi = λ2 /c sajátértékkel. Ebből következően λ2 = cγi .



3.2.10. Lemma. |λ2 | ≤ c. Bizonyítás. A 3.2.9. lemma szerint λ2 = cγi . Mivel S sztochasztikus mátrix, és spektrálsugara megegyezik ST spektrálsugarával, ezért a 3.1.3. állítás szerint |γi | ≤ 1, vagyis |λ2 | ≤ c. Ezzel egyben a 3.2.5. tételt is bebizonyítottuk.



Bizonyítás nélkül említem Kamvar és Haveliwala [2] eredményét, mely szerint ha a webgráf alapján létrehozott S átmenetvalószínűség-mátrixú Markov-láncnak legalább két irreducibilis osztálya van, akkor a λ2 = c egyenlőség teljesül. Tapasztalatok alapján a web szerkezete valóban ilyen, amiből azt a következtetést vonhatjuk le, hogy a G mátrixra eredményesen alkalmazható a hatványmódszer, az elfogadottnak vélt c = 0.85 érték mellett ([4] alapján).

3.2.4. A hatványmódszer gyakorlati megvalósítása Ahogyan a (3.3) összefüggésekben láttuk, a hatványmódszer igen egyszerű lépésekből áll, számítógépes megvalósítása is nagyon egyszerű. Ennek ellenére mégis hatékony tud lenni, ha alaposabban szemügyre vesszük. Kiszámításához egy vektort szorzunk minden lépésben egy mátrixszal, ami n × n méretű mátrix és a hozzá illeszkedő vektor esetén n2 szorzást jelent, mivel G sűrű mátrix. Némi átalakítással azonban sok szorzást megtakaríthatunk.

29

π (k+1)T = π (k)T G = = π (k)T (cS + (1 − c)E) = 1 − c (k)T T = cπ (k)T S + π ee = n   1 1 = cπ (k)T H + deT + (1 − c)π (k)T eeT = n n   1 cπ (k)T d + 1 − c eT = cπ (k)T H + n A levezetés alapján a költséges mátrix-vektor szorzásokat nem szükséges a sűrű G mátrixszal végezni, ezek elvégezhetőek a ritka H mátrixszal is, melynek O(n) nemnulla eleme van, így lényegében összesen ennyi szorzást kell elvégeznünk. Valószínűleg ez volt a legfontosabb szempont, ami miatt Brin és Page a hatványmódszer mellett döntött, ugyanis ritka mátrixok esetén nagyon takarékos. Ezen túl több, számítógépes megvalósítás szempontjából előnyös tulajdonsága is van, melyeket megtalálunk például [4] 4.6. szakaszában.

3.3. A PageRang mint lineáris egyenletrendszer A PageRang probléma sajátérték-feladatként való tárgyalása történetileg és technikailag mindenképp lényeges, ám nem az egyetlen lehetőség. Tekitsük ismét az előző szakaszban tárgyalt (3.1) egyenleteket. π T = π T G, π T e = 1. Ebben a szakaszban megmutatom, hogy ez a sajátérték-probléma felírható lineáris egyenletrendszerként is, egy másik megközelítési lehetőséget nyújtva ezzel a PageRang problémára. Ennek igazolásához, valamint a feladat egy gyakorlatban is hasznosnak bizonyuló formájának előállításához végezzük el a következő átalakításokat, felhasználva G (2.5)-ben definiált alakját.

πT

πT G = πT
cS + (1 − c)evT = π T

cπ T S + (1 − c)π T evT = π T cπ T S − π T = −(1 − c)π T evT

(3.6)

π T − cπ T S = (1 − c)π T evT π T (I − cS) = (1 − c)vT Az egyértelmű megoldás létezéséhez természetesen szükséges a korábbi π T e = 1 feltétel is.

30

Most használjuk fel, hogy S = H + dvT , és írjuk át ennek segítségével a kapott egyenletet.
π T I − cH − cdvT = (1 − c)vT π T (I − cH) − cπ T dvT = (1 − c)vT π T (I − cH) = (1 − c)vT + cπ T dvT

Legyen π T d = γ, mely a (2.3)-ban definiáltak alapján H összes elnyelő állapotához tartozó PageRang-ok összege lesz. γ felhasználásával egyenletünk a π T (I − cH) = (1 − c + γc)vT alakot ölti. Az előzőek szerint γ értéke tetszőlegesen megválasztható, mivel π normalizációját csak az egyenletrendszer megoldása után végezzük el. Válasszuk γ értékét éppen 1-nek, ekkor ugyanis a π T (I − cH) = vT

(3.7)

egyenlethez jutunk, mely több szempontból is igen előnyös, ahogyan azt hamarosan megmutatjuk. Az egyenlet egy általánosabb alakjának felírásához transzponáljuk az oldalakat : (I − cH)T π = v.

(3.8)

3.3.1. A megoldás létezése és helyessége A következő tétel igazolja, hogy az előbbiekben levezetett lineáris egyenletrendszer megoldása valóban létezik és helyes. 3.3.1. Tétel. (Langville–Meyer [4]) A PageRang vektor előáll π T = ahol

xT

xT kxT k1

alakban,

az xT (I − cH) = vT

lineáris egyenletrendszer megoldása. Bizonyítás. Az előálló π vektor pontosan akkor a PageRang vektor, ha teljesíti a (3.1) összefüggéseket. Mivel π T =

xT kxT k1

=

xT , xT e

így látható, hogy π T e = 1 valóban teljesül, már csak azt

kell igazolnunk, hogy fennáll π T (I − G) = 0T . Ez az előbbi állítás miatt ekvivalens annak igazolásával, hogy xT (I − G) = 0T . Felhasználva (2.5)-öt és (2.4)-et

xT (I − G) = xT I − cS + (1 − c) evT =
= xT I − cH − cdvT − (1 − c) evT = = xT (I − cH) − xT (cd + (1 − c) e) vT . A folytatáshoz belátjuk, hogy xT (cd + (1 − c) e) = 1. xT (cd + (1 − c) e) = cxT d + xT e − cxT e = = xT e − cxT (e − d) , 31

továbbá az e−d vektorban pontosan azon koordináták helyén áll nulla, melyeknek megfelelő állapotok elnyelőek, azaz hozzájuk H-ban 0T sor tartozik. Emiatt e − d = He, vagyis xT e − cxT (e − d) = xT e − cxT He = = xT (I − cH) e. Utolsó lépésként használjuk ki, hogy xT a tétel feltevése alapján megoldása az xT (I − cH) = = vT egyenletrendszernek, tehát xT (I − cH) e = vT e = 1, ezért valóban xT (cd + (1 − c) e) = 1, vagyis xT (I − G) = xT (I − cH) − vT = = vT − vT = = 0T . 

Ezzel a tétel állítását igazoltuk.

3.3.2. Az I − cH mátrix M -mátrix Vizsgáljuk a továbbiakban a (3.7) egyenletben bevezetett I − cH mátrixot. A mátrixok egy, numerikus módszerek szempontjából fontos osztályát alkotják az úgynevezett M -mátrixok. 3.3.2. Definíció. Egy A mátrixot M -mátrixnak nevezünk, ha főátlón kívüli elemei nempozitívak, nemszinguláris és inverze nemnegatív. A definícióban szereplő feltételek ellenőrzése általában nehéz, viszont a következő – bizonyítás nélkül közölt – állítás könnyen ellenőrizhető feltételt biztosít. 3.3.3. Állítás. (Faragó–Horváth, [1]) Legyen az A mátrix minden főátlóján kívüli elem nempozitív. A pontosan akkor M -mátrix, ha van olyan g > 0 vektor, mellyel Ag > 0. Ennek segítségével bebizonyítjuk a következő állítást. 3.3.4. Állítás. Az I − cH mátrix M -mátrix. Bizonyítás. A 3.3.3. állítás alapján azt kell megmutatnunk, hogy létezik olyan pozitív elemű g vektor, melyre az Ag vektor is pozitív lesz. Legyen g = e, vagyis a csupa egyesekből álló megfelelő méretű vektor. Ekkor nyilván e > 0, továbbá (I − cH) e = e − cHe. A He vektor a (2.3)-mal definiált d vektor segítségével kifejezhető e − d alakban, mivel H szubsztochasztikus, és pontosan azon sorait alkotja 0T vektor, ahol a d vektorban egyes áll. Ezek alapján e − cHe = e − c(e − d) = (1 − c)e + cd, ami c 6= 1 esetén egy pozitív és egy nemnegatív vektor összege, tehát pozitív. 32



Az M -mátrixok kellemes tulajdonsága, hogy ha A egy M -mátrix, akkor AT is M mátrix lesz. Ezt a tulajdonságot felhasználhatjuk az egyenletrendszer megoldhatóságának biztosítására, ahogyan később látni fogjuk.

3.3.3. A feladat kondicionáltsága A 3.1.5. példában egy rosszul kondicionált egyenletrendszert vizsgáltunk, és arra a következtetésre jutottunk, hogy kis együtthatómátrixbeli változások is okozhatják az eredményvektor használhatatlan torzulását. Az alábbi tétel azt mutatja, hogy megfelelő c konstans választásával a PageRang problémánál ilyen nem fordul elő. 3.3.5. Tétel. (Kamvar–Haveliwala, [3] alapján) Legyen S egy n × n-es sztochasztikus mátrix, melyre Sii = 0, továbbá c ∈ (0,1) valós szám. Legyen E az az n×n-es sztochasztikus mátrix, melyet az E = evT egyenlőség definiál, ahol e csupa egyesekből álló n hosszú vektor, v pedig egy valószínűségeloszlást reprezentáló n hosszú vektor. Definiáljuk a G mátrixot a következőképpen : G = (cS + (1 − c)E)T . Ekkor a Gx = x feladat kondíciós száma rácsnormában κ≤

1+c . 1−c

Megjegyzés. Kamvar és Haveliwala eredetileg egyenlőséget bizonyított igen újszerű és elegáns módon, egyszerű lemmák sorozatán keresztül. A kondíciós számra adódó felső korlát bizonyításához fel fogunk használni néhány korábbi tételt, valamint az alábbi lemmákat.

3.3.6. Lemma. I − cST 1 = 1 + c. Bizonyítás. Mivel feltevésünk szerint Sii = 0, ezért





I − cST = kIk + c ST = 1 + c ST . 1 1 1 1 Az S mátrix sztochasztikus, következésképp transzponáltjában minden oszlopösszeg 1 lesz,

vagyis ST = 1. Ezek alapján valóban 1



I − cST = 1 + c. 1


−1

3.3.7. Lemma. I − cST

≤ 1



1 . 1−c

Bizonyítás. Legyen X = −cST . Ekkor a 3.1.7. tétel alapján I − cST reguláris, és


−1 1

−1 .

I − cST

= (I + X) ≤ 1 − kXk1 1 1

Az kXk = −cST = c ST = c összefüggés a 3.3.6. lemma alapján fennáll, tehát valóban


−1

I − cST

≤ 1

33

1 . 1−c



A 3.3.5. tétel bizonyítása. A (3.6) egyenletek alapján a Gx = x feladat π = x helyettesítéssel átírható az xT (I − cS) = (1 − c) vT egyenletté, melynek mindkét oldalát transzponálva kapjuk az
I − cST x = (1 − c) v lineáris egyenletrendszert, melynek együtthatómátrixa tehát A = I − cST . A feladat kon

díciószámát a 3.1.6. definíció szerint a κ = cond 1 (A) = kAk1 A−1 1 képlet adja. Erre a 3.3.6. és a 3.3.7. lemmák alapján valóban a κ≤

1+c 1−c 

becslés adódik.

3.3.4. Lehetséges megoldási módszerek Lineáris egyenletrendszerek megoldására általában két különböző módon történhet : direkt módszer, illetve iterációs módszer alkalmazásával. Az alábbiakban röviden összefoglalom mindkét módszertípus alaptulajdonságait. Direkt módszerek Direkt megoldási módszerről akkor beszélünk, ha az egyenletrendszer pontos megoldásához véges sok számítási művelet elvégzésével jutunk hozzá. Természetesen számítógépen végezve ennek a pontosságnak ismert határa van, de ha azt feltételezzük, hogy minden lépésben a számítási műveleteket pontosan tudjuk végezni, akkor a módszer – legalábbis elvben – pontos megoldást szolgáltat. Az egyik legismertebb és legegyszerűbb ilyen módszer a Gauss-módszer. Alapgondolata az, hogy az egyenletrendszer A együtthatómátrixát egy U felső háromszögmátrixszá alakítja a mátrix bizonyos sorainak más sorokból való szisztematikus kivonásával (eliminációval). Az így előálló U együtthatóiból visszafelé haladva előállítható az egyenletrendszer megoldása. Bizonyítás nélkül közlöm, hogy amennyiben az A mátrix M -mátrix, akkor a Gauss2 módszer végrehajtható, és n×n méretű együtthatómátrix esetén műveletigénye n3 +O(n2 ) 3 lebegőpontos művelet. Ezek alapján a PageRang probléma mint lineáris egyenletrendszer megoldható Gauss-módszerrel. Felhasználva a (3.8) egyenletet a π = x helyettesítéssel, az egyenletrendszer együtthatómátrixa az (I − cH)T ritka mátrix lesz. A Gauss-módszer azonban nem tudja kihasználni ezt a tulajdonságot, mivel az eljárás során a nulla elemek helyét „feltölti”. Összességében elmondhatjuk, hogy direkt módszerek használata a PageRang proléma esetén leginkább akkor célravezető, ha kevesebb csúcsból álló hálózatokon (úgymint intranetek, kisebb közösségi hálók) dolgozunk, ekkor ugyanis elfogadható időben kapunk pontos eredményt. 34

Iterációs módszerek Iterációs módszer esetén nem a pontos megoldást akarjuk előállítani, csak annak egy megfelelő közelítését. Ezek a módszerek egy iteráció által előálló sorozatot adnak eredményül, melynek határértéké a pontos megoldás. A lineáris iterációs eljárások általános alakja x(k) = Bx(k−1) + f ,

k = 1,2, . . . ,

ahol az x vektor tart a pontos megoldáshoz. Látható, hogy a módszer egy iterációs lépésének elvégzése egy mátrix-vektor szorzásból és egy vektor-vektor összeadásból áll, vagyis összesen n2 +n2 lebegőpontos műveletet igényel n×n-es mátrix esetén. Ez akkor kedvezőbb a Gauss-módszer 2/3n3 lépésszámánál, ha nem több mint n/3 iterációs lépésből megfelelő pontosságú megoldáshoz jutunk. Erre általános mátrixok esetén kicsi esélyünk van, ritka mátrixok esetén azonban az elvégzendő lebegőpontos műveletek száma drasztikusan csökken a nagyszámú nulla elem miatt. 3.3.8. Definíció. (Faragó–Horváth, [1]) Az x(k) = Bx(k−1) + f iterációt az Ax = b egyenletrendszerrel konzisztensnek nevezzük, ha x? = Bx? + f , ahol x? az egyenletrendszer megoldása. Tegyük fel, hogy Ax = b egyenletrendszer együtthatómátrixa előáll A = P − Q alakban, ahol P egy reguláris mátrix. Ekkor b = Ax = Px − Qx, melyet P inverzével balról szorozva, majd x-et kifejezve az x = P−1 Qx + P−1 b összefüggés adódik. Bevezetve a B = P−1 Q és f = P−1 b jelöléseket, az x(k) = Bx(k−1) + f = P−1 Qx(k−1) + P−1 b iterációt kapjuk, amely a fentiek szerint konzisztens az eredeti egyenletrendszerrel. A kifejezésben szereplő P mátrixot prekondicionálási mátrixnak nevezzük, megválasztásától függ az iteráció megoldhatóságának nehézsége. A következő tétel szükséges és elégséges feltételt biztosít egy lineáris iteráció konvergenciájára. 3.3.9. Tétel. (Faragó–Horváth, [1]) Egy, az Ax = b egyenletrendszerrel konzisztens lineáris iteráció pontosan akkor tart az egyenletrendszer megoldásához tetszőleges kezdővektor esetén, ha ρ(B) < 1. Bizonyítás. Legyen e(k) az iteráció k-adik lépésében előálló hibavektor, vagyis e(k) = x(k) − x? = Bx(k−1) + f − (Bx? + f ) = Be(k−1) . 35

A k-adik lépésbeli hiba kifejezhető a kezdeti hiba segítségével : e(k) = Bk e(0) , tehát a konvergenciához szükséges, hogy limk→∞ Bk = 0. Ez pontosan akkor teljesül, ha B spekrálsugara 1-nél kisebb, amivel az állítást igazoltuk.



Tekintsük ismét a (3.8) egyenletet a π = x helyettesítéssel: (I − cH)T x = v. Ekkor a korábbi jelöléseket felhasználva P = I és Q = cHT , vagyis B = P−1 Q = IcHT = = cHT , és f = P−1 b = Iv = v. Mivel H szubsztochasztikus mátrix és c < 1, így nyilván ρ(B) < 1. A 3.3.9. tétel következményeként az így definiált x(k) = cHT x(k−1) + v lineáris iteráció konvergens lesz. Az is látható, hogy műveletigénye HT ritkasága miatt igen kedvező, a mátrix-vektor szorzás egy iterációs lépésben csak O(n) lebegőpontos számítási műveletet igényel. Olyan nagy méretű hálózatok esetén mint a WWW, épp ezért előnyös iterációs módszer használata direkt módszerrel szemben. A prekondicionálási mátrix megválasztásától függően különböző módszereket kapunk (például Jacobi-, vagy Gauss–Seidel-iteráció). Ezeket és a korábban említett direkt módszereket alaposabban tárgyalja például [1].

3.4. A PageRang egyenlet paraméterei 3.4.1. A c konstans A (2.5) egyenletból látható, hogy a c paraméter egy súlyozó tényezőként működik. Azt szabályozza, hogy a G mátrixban mekkora szerep jusson a gráf kapcsolatai alapján épített S mátrixnak, és mekkora a véletlen ugrásokat jelképező E-nek. Minél közelebb van c egyhez, annál relevánsabb egy-egy csúcs PageRang-ja, hiszen annál inkább a valódi hálózat szerkezete határozza meg a rangokat. Ugyanakkor a 3.2.5. és 3.3.5. tételek alapján a c ≈ 1 választás számítási szempontból előnytelen, hiszen ekkor egyrész nagymértékben lassul a hatványmódszer konvergenciája, másrészt a feladat kondíciószáma túlzottan nagy lesz, tehát lényegében többet vesztünk a kiszámítás pontosságán, mint amennyit nyerünk a valósághoz közelebb álló hálózatra építve a modellt. Hasonlóan, a c ≈ 0 választás sem célszerű, hiszen ekkor szinte teljesen véletlen bolyongást végzünk a hálózaton, ami alig ad használható információt a csúcsok fontosságáról. Látható, hogy valahol 0 és 1 között célszerű megválasztani c értékét. Elfogadott, hogy a c = 0.85 választás általában ideális a fenti szempontok szerint, ekkor ugyanis a modell lényegében az S mátrixra támaszkodva végzi a bolyongást, viszont kedvezőnek mondható mind a hatványmódszer szükséges lépésszáma, mind a κ ≈ 12 kondíciószám ([4]).

36

3.4.2. A H hiperlink mátrix A 2.2. szakaszban láttuk, hogyan készíthető el a H hiperlink mátrix egy gráf alapján. A módszer azt feltételezi, hogy a sztochasztikus szörföző egyforma valószínűséggel, „minden mindegy” alapon dönt a következő meglátogatandó oldalról. Ez a valóságban nem feltétlenül van így. Jobb esetben egy intelligens szörföző ül a gép előtt, aki több szempontot is figyelembe vesz, amikor döntést hoz a következő meglátogatandó oldalról: van valami, ami miatt jobbnak tűnik egy bizonyos linket választani? Például rendelkezésre áll-e valamilyen rövid leírás (úgynevezett anchor text) a hivatkozáson? Az egyik hivatkozás minőségibb tartalmat kínáló oldalra juttat ? Ha ez így van, akkor valószínűbb, hogy a szörföző ilyen oldalakat fog választani, ami kissé megváltoztatja H struktúráját. Nézzük meg ezt a 2.2. ábra példáján kereszül. A sztochasztikus szörföző számára létező mátrix a korábbi   0 1 0 0 0   0 0 1/2 1/2 0      H1 = 0 1/3 0 1/3 1/3 ,   0 0 1/2 0 1/2   0 0 0 0 0 míg egy intelligens szörföző számára lehet, hogy ez a   0 1 0 0 0   0 0 3/4 1/4 0      H2 = 0 1/3 0 1/3 1/3   0 0 1/3 0 2/3   0 0 0 0 0 mátrix lesz, mivel valamiért úgy ítéli meg, hogy például értékesebb a 2-es csúcsból a 3-as csúcsba navigálni, mint a 4-esbe. Különféle módszerek léteznek arra, hogyan lehet a H hiperlink mátrixot előállítani a rendelkezésre álló hálózat jellemzői alapján, erről többet olvashatunk például [4]-ben.

3.4.3. Az E teleportációs mátrix A (2.5)-ben definiált G mátrix egyik komponense az E = evT teleportációs mátrix, melynél ott azt feltételeztük, hogy v = (1/n, 1/n, . . . , n)T . Ha azonban v koordinátáit nem egyformára választjuk, az lehetőséget biztosít egyféle perszonalizációra a következő értelemben. Eddig a sztochasztikus szörföző a teleportációi célpontjait egyenletes eloszlás szerint választotta, egyforma esélyt adva bármely oldalnak a weben. Ha azonban rendelkezik egyféle személyes érdeklődéssel, akkor kialakíthat magának egy olyan perszonalizációs vektornak nevezett vT valószínűségi vektort, amely az érdeklődési körének jobban megfelelő oldalakra nagyobb valószínűséggel navigálja. 37

Ez egy igen előnyös lehetőség, tekintve a web méretét és a különböző nemzetiségű emberek érdeklődését. Egy magyar szörföző által megadott keresőszóra miért ne rangsoroljuk például előkelőbb helyre a magyar nyelvű találatokat ? Vagy akár miért ne készíthetné el mindenki a saját érdeklődésének megfelelő vT vektort a legjobb relevancia eléréséért? Ennek természetesen technikai korlátai vannak, mivel a PageRang értékek kiszámítása nem valós időben történik, és jelenleg nem lehetséges mindenki számára egy egyéni G mátrix eltárolása. Azonban ennél nagyobb léptékű, területekre kiterjedő perszonalizáció jelenleg is működik például a Google keresőjében.

3.5. Perturbált adatok hatása a modellre Alkalmazások szempontjából az egyik legkényesebb pontja egy matematikai modellnek a következő tulajdonság: ha a bemenő adatokban bekövetkezik valamekkora változás, akkor az a végeredmény szempontjából mennyire lényeges? Elvárásunk szerint ha az ideális bemenő adatok kicsit megváltoznak (perturbálódnak), akkor a végeredmény ne változzon meg nagyon az ideálishoz képest. Vizsgáljuk először a kérdést egy példán keresztül. 3.5.1. Példa. A 2.2.2. példában kiszámítottuk a 2.2. gráf csúcsainak PageRang értékeit. Nézzük, jelentősen megváltozik-e ez a rangsor, ha a gráfban például törlünk egy élet1 . Távolítsuk el a 3-as csúcsból a 4-es csúcsba futó élet. Legyen H az eredeti hálózat hiperlink ˜ pedig a perturbált hiperlink mátrix. mátrixa, H     0 1 0 0 0 0 1 0 0 0     0 0 1/2 1/2 0  0 0 1/2 1/2 0         ˜ = H = 0 1/3 0 1/3 1/3 H 0 1/2 0 0 1/2     0 0 1/2 0 1/2 0 0 1/2 0 1/2     0 0 0 0 0 0 0 0 0 0 Úgy is elképzelhetjük, hogy a H mátrixhoz egy a P perturbáló mátrixot adtunk hozzá, így ˜ ˜ − H, esetünkben kaptuk H-ot. Ezek alapján P = H   0 0 0 0 0   0 0 0 0 0      P = 0 1/6 0 −1/3 1/6 .   0 0 0 0 0    0 0 0 0 0 ˜ mátrix alapján konstruáljuk meg az S ˜ sztochasztikus mátrixot, majd a Ha most a H ˜ = cS+(1−c)E ˜ ˜ megfelelő domináns G mátrixot c = 0.85 paraméterrel, majd kiszámítjuk G sajátvektorát, akkor a π ˜ T = (0.07 0.24 0.25 0.18 0.26) 1

Az utolsó fejezetben látni fogjuk, hogy sokszor hasonló helyzetbe kerülünk, például ha valamilyen hálózatban nem tudjuk egyértelműen eldönteni, hogy két csúcs között van-e kapcsolat vagy nincs.

38

vektor adódik. Ennek alapján a perturbált gráf csúcsai fontossági sorrendben : (5, 3, 2, 4, 1). Az eredetileg adódó (3, 5, 4, 2, 1) sorrenddel összevetve azt tapasztaljuk, hogy az él törlése megváltoztatta a csúcsok PageRang-ját a gráfban, s ezzel a kialakuló fontossági sorrendet is. Felmerül a kérdés, hogy általánosságban mit mondhatunk, ha perturbáljuk a H mátrixot. Tetszőlegesen választott élek törlése vagy hozzáadása felborítja az eredeti sorrendet, vagy ez csak bizonyos, jól kiszemelt élekkel érhető el? Legfeljebb mennyire változtathatunk H-n, ha nem akarjuk lényegesen megváltoztatni a kialakuló rangokat? ˜ A következő tétel felső korlátot ad a G-hez tartozó π, és a G-hoz tartozó π ˜ vektorok eltérésére, azaz a perturbáció rangokra gyakorolt hatására. 3.5.2. Tétel. (Lee–Borodin, [5]) Legyen S egy n × n-es sztochasztikus mátrix, továbbá c ∈ (0,1) valós szám. Legyen E = evT , ahol e csupa egyesekből álló n hosszú vektor, v pedig egy valószínűségeloszlást reprezentáló n hosszú vektor. ˜ = Legyen a G = (cS + (1 − c)E)T mátrix domináns sajátvektora π, továbbá a G  T ˜ + (1 − c)E = cS perturbált mátrix megfelelő domináns sajátvektora π ˜ . Ekkor kπ − π ˜ k1 ≤

2c X πi, 1−c i∈U

ahol U a perturbált csúcsok halmaza. ˜ − S. A tétel bizonyításához felhaszLegyen most is P a perturbáló mátrix, azaz P = S náljuk az alábbi lemmákat. 3.5.3. Lemma. ET (π − π ˜ ) = 0. Bizonyítás. E = evT , ezért ET minden oszlopa megegyezik. Mivel π és π ˜ mindketten valószínűségi vektorok, vagyis kπk1 = k˜ π k1 = 1, valamint ET (π − π ˜ ) = ET π − E T π ˜, ezért ET π = ET π ˜ , amiből a lemma állítása következik. X

3.5.4. Lemma. PT π 1 ≤ 2 πi.



i∈U

Bizonyítás. Rendezzük át úgy PT oszlopait úgy, hogy a perturbálatlan (azonosan nulla elemeket tartalmazó) oszlopok a mátrix bal oldalára kerüljenek, π elemeit pedig úgy, hogy illeszkedjenek ehhez a sorrendhez. Ekkor π0 a perturbálatlan csúcsok rangjaiból áll, !
π 0 PT π = 0 P1 T = P1 T π1 . π1

39

Vegyük az egyenlet oldalainak oszlopösszegnormáit.

 T



T

P π = P1 T π1 = S ˜ 1 − S1 π1

1 1 1

  T

˜ ≤

S1 − S1 kπ1 k1 1 

T 

˜T ≤ S1 + S1 1 kπ 1 k1 1



˜T Mivel S1 T 1 = S 1 = 1, valamint π1 tartalmazza a perturbált csúcsokhoz tartozó 1

rangokat, ezért valóban X

T

P π ≤ 2 πi. 1



i∈U

˜ mátriA 3.5.2. tétel bizonyítása. Mivel π és π ˜ rendre domináns sajátvektorai a G és G xoknak, ezért Gπ = π

és

˜π = π G˜ ˜.

Ebből következően ˜π π−π ˜ = Gπ − G˜  T ˜ + (1 − c)E π = (cS + (1 − c)E)T π − cS ˜ ˜T π = cST π + (1 − c)ET π − cS ˜ − (1 − c)ET π ˜   ˜T π = c ST π − S ˜ + (1 − c)ET (π − π ˜) . A 3.5.3. lemmát, valamint P definícióját felhasználva   ˜T π π−π ˜ = c ST π − S ˜ ˜T π = cST π − cS ˜ ˜ T (π + π = cST π − cS ˜ − π) ˜ T π − cS ˜ T (˜ = cST π − cS π − π)   ˜ T (π − π ˜ T π + cS ˜) = c ST − S ˜ T (π − π = cPT π + cS ˜) .

A kapott egyenletet π − π ˜ -re megoldva kapjuk, hogy  −1 ˜T π−π ˜ = c I − cS PT π. A két oldal normáit véve a norma tulajdonságaiből következik

 −1

T T

P π . ˜ kπ − π ˜ k1 ≤ c

I − cS

1 1

A 3.3.7. és 3.5.4. lemmák alapján kapjuk a tétel állítását, 2c X πi. kπ − π ˜ k1 ≤ 1−c i∈U

40



A 3.5.2. tétel szerint tehát a perturbáció hatása kicsi marad, ha nem túl nagy rangú csúcsok perturbálódnak, valamint a c konstans értéke nem esik közel egyhez. Utóbbi szükségességét már korábban is láttuk. A tétel alapján érthető, miért változott számottevően a 3.5.1. példabeli rangsor: éppen az egyik legnagyobb rangú csúcshoz tartozó élet töröltük. A tételnek az alkalmazásokat tekintve is fontos következménye, hogy ha csak viszonylag kevés számú hiányzó vagy pontatlan adat van a hálózatban, akkor annak nincs számottevő hatása a csúcsok PageRang-jára, ilyen értelemben a módszer kellően hibatűrő. Többek között ez a tulajdonsága tette igen népszerűve a különböző tudományterületeken dolgozók számára.

41

4. fejezet

A PageRang alkalmazása hálózatok összehasonlítására 4.1. Protein-protein interakciós hálózatok A biológia tudományának egyik legfiatalabb ága a hálózatbiológia. Vizsgálatainak tárgya az élő sejten belüli molekuláris alkotók (úgymint DNS vagy fehérjék) közötti kapcsolatok feltárása és összefüggéseik elemzése. Az elmúlt közel két évtized kutatásai nyomán ma már nagy mennyiségű adat áll rendelkezésre, többek között az egyszerűbb egysejtű élőlények genomján át egészen a humán genomig. Ez az adattömeg alkalmas lehet arra, hogy a belőle kinyerhető információ és korábbi tudományos ismeretek összekapcsolásával megismerhetővé és leírhatóvá váljon a sejt molekuláris szintű működése, mely a hálózatbiológia egyik alapvető célja. A sejtek leglényegesebb alkotói között kell említenünk a fehérjéket, másnéven proteineket. Szerepük van a jelátvitelben, enzimműködések szabályozásában, sejtfunkciók irányításában. Ezek érdekében egymással, valamint más molekulákkal, például DNS-sel lépnek kölcsönhatásba. Bizonyos proteinek állandóan jelen vannak a sejtben, míg mások csak ideiglenesen, valamilyen sejtfolyamat alatt jönnek létre, majd felhasználódnak. Funkcióiékért bizonyos részeik, úgynevezett domének felelősek. Egy-egy fehérje működését ilyen domének különböző kombinációi határozzák meg. Egy protein működése lényegében annyit jelent, hogy az közvetlen fizikai kapcsolatba kerül más proteinekkel. Ezt a folyamatot proteinprotein interakciónak, röviden PPI-nek hívjuk. Egy szervezet genomja meghatározza azt, hogy milyen proteineket képes előállítani. Egy bizonyos szervezet által előállítható proteinek összességét proteomának hívjuk. Ha valahogyan sikerül feltérképeznünk, hogy a proteinek működésük során mely más proteinekkel kerülnek kölcsönhatásba, akkor az adatokból létrehozhatunk egy protein-protein interakciós térképet, röviden PPI-hálózatot. PPI hálózatokat matematikailag irányítatlan gráfként modellezhetünk. Az egyes proteineknek a gráf csúcsait, a köztük lévő közvetlen fizikai kölcsönhatásnak pedig a csúcsok között futó élet feleltethetjük meg. Különböző

42

szervezetek PPI hálózatainak összehasonlítása hasznos összefüggéseket fedhet fel, például olyan hasonló részstruktúrákat találhatunk, melyek a természetes szelekció folyamata közben változatlanok maradtak, így igen stabilnak tekinthetők. Egy faj biológiai jellemzőit annak genomja határozza meg, mely a törzsfejlődés során valamelyes változik, a lényeges, stabil elemek azonban megőrződnek. Két olyan biológiai jellemző közötti kapcsolatot, mely közös ősre vezethető vissza, homológiának nevezünk. Ilyen értelemben beszélhetünk arról, hogy két gén vagy protein homológ. Két gént ortológnak hívunk, amennyiben közös ősből alakultak ki a törzsfejlődés során. Általában fajtól függetlenül azonos funkciójuk van, mely az ős prekurzor génjétől származik. Elfogadott nézet az, hogy ortológ gének termékei felelősek az alapvető sejtfolyamatokért. Ezek alapján érthető az a törekvés, mely különböző szervezetek PPI hálózatai között próbál hasonló struktúrákat találni: ha ismerjük egy egyszerűbb szervezetben egy erősen összekapcsolódó proteincsoport (protein komplex ) működését, akkor feltételezhetjük, hogy a bonyolultabb szervezetben is hasonló funkciót lát el. Ez az ismeret hasznosnak bizonyul a működés megértése szempontjából, például lehetőséget nyújt a sejtekben bekövetkező káros elváltozások elleni célzott hatóanyagok kifejlesztésére.

4.2. Az IsoRank eljárás Az előbb felvázolt cél tehát, hogy különböző szervezetek PPI hálózatai között hasonlóságokat találjunk. Ez lehetséges úgy, hogy izomorf részgráfokat keresünk a két hálózatban, vagyis az egyik hálózat bizonyos csúcsait megfeleltetjük a másik hálózat bizonyos csúcsainak, vagyis találunk egy izomorf leképezést a két PPI hálózat gráfja között. Tekintettel arra, hogy a PPI hálózatokban található kapcsolatok valamilyen kísérlet vagy mérés eredményei, általában tartalmaznak valamekkora bizonytalanságot, vagyis egy hálózatbeli él nem jelenti 100%-os biztonsággal a két protein interakcióját, illetve előfordulhat, hogy egy létező interakciót nem tartalmaz a gráf. Épp ezért a klasszikus részgráf-izomorfizmust megoldó problémák alkalmazása célszerűtlen ebben az esetben, és itt valójában nem is izomorf részgráfokat, inkább valamilyen értelemben hasonló részgráfokat keresünk. A módszer leírását [10] alapján adom meg.

4.2.1. Az IsoRank-modell Legyen adott a két gráf, GA (VA , EA ) és GB (VB , EB ). Az IsoRank eljárás a két gráf legnagyobb hasonló közös részgráfját (MCS1 ) állítja elő a következő intuíció alapján: a közös részgráf olyan csúcspárokból áll, melyek hasonló tulajdonságúak a két gráfban, egy nA ∈ ∈ GA és nB ∈ GB csúcspárt pedig akkor tekint hasonlónak, ha hasonló szomszédaik vannak az eredeti gráfokban. A csúcspárok hasonlósága a GA és GB gráfok csúcsaiból összekombinált GC = GA × GB gráfon értelmezett. GC tehát a két eredeti gráf direkt szorzataként 1

Az angol maximum common subgraph rövidítése.

43

áll elő, vagyis csúcsai olyan (ai , bi ) párok, ahol ai ∈ VA és bi ∈ VB , egy (ei , ej ) pár pedig pontosan akkor éle GC -nek, ha (ai , aj ) ∈ EA és (bi , bj ) ∈ EB . Az eljárás egy hozzárendelést próbál megadni a GA és GB gráfok csúcsai között azok hasonlósági pontszámai alapján. Ezek a pontszámokat az alábbi képlet adja : X X 1 Ruv , i ∈ VA , j ∈ VB , Rij = |N (u)| |N (v)| u∈N (i) v∈N (j)

ahol N (a) jelöli a gráf a csúcsának szomszédaiból álló halmazt, vagyis |N (a)| épp az a csúcs szomszédainak számát adja meg. A PageRang-hoz hasonlóan ez is egy rekurzív megadása a csúcspárok pontszámainak. A 2.2.1. alszakaszban leírtakhoz hasonlóan a fenti egyenlet is felírható mátrixos alakban. Ehhez legyen  1   |N (u)| |N (v)| Cij,uv =  0

ha (i, u) ∈ EA és (j, v) ∈ EB , (4.1) egyébként.

Látható, hogy a C mátrix dupla indexeléssel rendelkezik, aminek az az oka, hogy két mátrix direkt szorzataként áll elő. A következő definíció és példa segít ennek pontosításában. 4.2.1. Definíció. (Meyer, [6]) Az Am×n és Bp×q mátrixok tenzorszorzatán (vagy direkt szorzatán, esetleg Kronecker-szorzatán) a következő mp × nq méretű mátrixot értjük :   a11 B a12 B · · · a1n B    a21 B a22 B · · · a2n B    A⊗B= . . .. ..  ..  ..  . . .   am1 B am2 B · · · amn B 4.2.2. Példa. Legyen A =

1 2 3 4

!

5 6

és B = 

5

7

!

8 9 10

6

7

. Ekkor

10 12 14



   8 9 10 16 18 20   A⊗B= . 15 18 21 20 24 28   24 27 30 32 36 40 Vezessük be még a |VA | × |VB | méretű r vektort, amely a csúcspárok hasonlósági pontszámait tartalmazza. A (4.1) egyenlőséggel definiált mátrixot felhasználva a hasonlósági pontszámok kiszámítása a PageRang problémához hasonlóan egy sajátérték-feladathoz vezetnek: rT = rT C, rT e = 1. A modellt tovább finomíthatjuk úgy, hogy a hasonlósági pontszámok kiszámításához nem csak a C mátrixot, vagyis a két hálózat szomszédsági adatait, hanem valamilyen más 44

forrásból rendelkezésünkre álló információt is felhasználunk2 . Ez az információ felfogható a 3.4.3. alfejezetben bemutatott perszonalizációs vektorként, melynek segítségével az E teleportációs mátrixot létrehoztuk. Ezek felhasználásával lényegében egy PageRang-problémával van dolgunk. rT = rT (cC + (1 − c)E) , ahol most is egy c paraméterrel befolyásolhatjuk, hogy mekkora hatása legyen a gráfoknak, illetve az előzetes információknak a csúcspárok hasonlósági pontszámaira.

4.2.2. A hasonló részgráf előállítása Tegyük fel, hogy sikerült megtalálnunk egy alkalmas rT sajátvektort. Vezessük be a következő transzformációkat. 4.2.3. Definíció. Az Am×n mátrix vektorizáltján a következő mn méretű vektort értjük: vec(A) = (a11 , . . . , am1 , a12 , . . . am2 , . . . , a1n , . . . amn )T , vagyis a mátrix oszlopainak egymás alá rendezéséből keletkező vektort. Ennek inverz művelete a vec−1 (v) művelet, amely a v vektorból egy mátrixot állít elő a vektor szeleteinek mátrixba rendezésével. A csúcspárok közötti hasonlósági értékek kinyerése többféleképpen történhet, ahogyan azt [10]-ben olvashatjuk. Egyszerűen megvalósítható, mégis hatékony a következő mohó eljárás. Tegyük fel, hogy előállítottuk az eredeti mátrixok méretéhez illeszkedő R = vec−1 (r) mátrixot, melynek elemei a két gráfból származó csúcspárok hasonlósági értékei. Rendeljük a GA gráf i-edik csúcsához a GB gráf j-edik csúcsát úgy, hogy megkeressük R (egyik) maximális rij értékét, majd nullázzuk a hozzá tartozó oszlop és sor összes többi elemét. A többi egymásnak megfeleltetett csúcspár megkereséséhez ismételjük az előző lépéseket, amíg lehetséges. Nyilván legfeljebb a kisebbik gráf csúcsszámának megfelelő mennyiségű párt találhatunk. Előfordulhat, hogy egy lépésben több maximumot is találunk R-ben. Ekkor tetszőlegesen választhatunk, a hasonlósági hozzárendelés nem lesz egyértelmű. Most, hogy rendelkezünk a hasonló csúcspárok közötti megfeleltetéssel, szeretnénk ennek segítségével az MCS-t megadni a GA és GB gráfok között. A csúcsokkal már rendelkezünk, az élekre van már csak szükségünk. Amennyiben az eljárás egy i1 ∈ VA és i2 ∈ VB csúcspárt, valamint egy j1 ∈ VA és j2 ∈ VB csúcspárt egymáshoz rendelt, akkor a közös részgráfban pontosan akkor lesz az (i1 , i2 ) és (j1 , j2 ) csúcsok között él, ha az eredeti gráfokban is volt köztük él, azaz ha (i1 , j1 ) ∈ EA és (i2 , j2 ) ∈ EB teljesül. Ezzel előállítottuk a két megadott gráf hasonló részgráfját. 2

Ezek lehetnek például valamilyen kísérletből, vagy korábbi algoritmussal meghatározott értékek. Ebben az esetben egy-egy csúcspár hasonlósági értéke szándékosan növelhető vagy csökkenthető aszerint, hogy arról milyen előzetes információval rendelkezünk, lásd [10].

45

4.2.3. Az IsoRank megvalósítása MATLAB környezetben Az előzőekben leírt módszert MATLAB környezetben valósítottam meg. A létrehozott forráskódok megtalálhatóak a Függelékben, ezek a következők: – normalize(A): egy szomszédsági mátrix sztochasztikussá alakítását végzi. Egyetlen paramétere a normalizálandó mátrix, visszatérési értéke pedig a megfelelő soronként sztochasztikus mátrix. – unvec(v, cols): a korábban definiált vec−1 (v) műveletet végzi el az egyik paraméteréül adott vektoron. Másik paramétere az elkészítendő mátrix sorainak száma. – power_method(A, x, tlevel, maxit): a hatványmódszert megvalósító eljárás. Paraméterei egy A mátrix (melynek domináns sajátértékéhez tartozó sajátvektorát adja visszatérési értékül), egy kiinduló v vektor, valamint két leállási kritérium : egy hibahatár és egy maximális iterációszám. – isorank(M1, M2, c, v): az IsoRank eljárást megvalósító függvény. Paraméterei a két összehasonlítandó gráf szomszédsági mátrixa, M1 és M2 , valamint a korábban ismertetett c súlyérték és a v perszonalizációs vektor. Visszatérési értéke a közös részgráf szomszédsági mátrixa. A módszer teszetlését az alábbi szkript végzi. Graph1 = SFNG(n, 1, seed1); Graph2 = SFNG(m, 1, seed2); A = isorank(Graph1, Graph2, 0.6, ones(n^2,1)/n^2); A tesztadatok véletlenszerűen generált skálafüggetlen hálózatok voltak, mivel tapasztalatok szerint3 sok valódi hálózat ilyen szerkezetű. Ezeket az SFNG() függvény4 állítja elő. A c súlyparaméter választott értéke 0.6, a választás indoklása megtalálható [10]-ben. Az eljárás végeredménye a hasonló részgráf szomszédsági mátrixa, A.

4.2.4. Teszteredmények Az eljárást először egy 15 csúcspontból álló, véletlen gráfon próbáltam ki, önmagával összehasonlítva azt. Ahogyan az várható volt, az előálló legnagyobb hasonló részgráf egy, az eredeti gráffal izomorf gráf. A hozzárendelés nem minden esetben egyértelmű, ha léteznek egyező hasonlósági pontszámú csúcspárok. Ha ilyenek nincsenek, akkor az eredeti gráfot kapjuk vissza, ahogyan esetünkben is történt (4.1. ábra). Ezt követően két, egymással izomorf, de nem megegyező gráfon teszteltük az eljárást. Ebben az esetben is az eredmény a bemenő gráfokkal izomorf gráf lett, de a csúcsok egymáshoz rendelése már nem volt egyértelmű (4.2. ábra). 3

4

Könnyed és olvasmányos módon tárgyalja a skálafüggetlen hálózatok gyakori jelenlétét és ennek okait Barabási Albert-László Behálózva című könyve. http ://www.mathworks.com/matlabcentral/fileexchange/11947

46

Lényegesen változik a hasonló részgráf mérete és szerkezete, ha nem izomorf gráfokat adunk meg. A 4.3. ábrán látható az az eset, amikor egy gráfot és annak egy valódi részgráfját hasonlítjuk az eljárással. Az előbb felhasznált 5 csúcsú gráfot, és annak egy olyan részgráfját hasonlítottam össze, ahol az 5-ös csúcshoz vezető élet eltávolítottam. Mivel ez nem csak erre az egy élre volt hatással, így megváltoztatta a gráf csúcsainak szomszédsági viszonyait, ami az algoritmus által előállított megfeleltetés, és a visszaadott közös részgráf változását okozta. Hangsúlyozom, hogy az előálló hasonlósági pontszámokból mohó eljárással készítettük el a csúcsok közötti megfeleltetést, így előfordulhat, hogy az nem globálisan optimális megfeleltetés, ahogyan ebben az esetben is történt. Látható, hogy ebben az esetben például az 1–2, 2–1, 3–3, 4–4, 5–5 leképezés lenne optimális. Végül egy nagyobb méretű, 50 csúcsból álló véletlen, skálafüggetlen hálózatot hasonlítottam össze egy 45 csúcsból álló, szintén véletlen skálafüggetlen hálózattal (4.4. ábra). Mivel az eljárás megvalósításánál feltételeztem, hogy a szomszédsági mátrixok egyforma méretűek, így a kisebbik gráfot üres („dummy”) csúcsokkal töltöttem fel, hogy a mátrixműveletek elvégezhetőek legyenek. A hálózatok skálafüggetlen tulajdonságágból várható volt, hogy még egymástól független, véletlen hálózatok esetén is lesznek hasonló csúcspárok a két gráfban, amit a kapott eredmények is alátámasztottak (4.4c. ábra).

4.2.5. Összegzés, következtetések A teszteredmények alapján elmondható, hogy az IsoRank módszer még ebben a naiv megvalósításban is használható eredményeket szolgáltatott. Ezt leginkább intuitív alapon, a kapott hasonló gráfok szemügyrevételével, sem mint precíz mérési eredményekkel alátámasztva állítom. Ilyen mérési eredmények elkészítése és elemzése meghaladná a dolgozat kereteit, a kapcsolódó cikkekben azonban található róla információ. A MATLAB környezetben megvalósított IsoRank egyik legnagyobb gyengesége a futásidő volt. Érdekes módon ezt elsősorban a másodlagosnak tekinthető normalize() eljárás okozta, mely a teljes számítási igény mintegy 75%-át adta. Ezt a benne található ciklus és elágazások okozzák, melyek gyors elvégzése nem erőssége a MATLAB-nak. Amennyiben megoldódna ennek a függvénynek a gyorsítása, úgy jó eredménnyel alkalmazható a módszer MATLAB-os megvalósítása akár ezres nagyságrendű csúcsszám esetén is, szemben a mostani maximálisan néhány tíz csúccsal. A módszer teljesítményének értékelése miatt jegyzem meg, hogy a tesztelést egy Intel Atom N270 processzoral szerelt számítógépen végeztem, melyen a módszer teljes futásideje az 50 csúcsú véletlen gráf esetén nagyjából fél percet tett ki.

47

5

5

4

6

5/5

4

6 3

7

3/3

7

7/7

2

2

8

2/2

8

8/8

1 9

1 9

1/1 9/9

15 10

15 10

15/15 10/10

14

14

11

14/14

11 12

4/4

6/6

3

13

11/11 12

(a) Graph1

13

12/12

(b) Graph2

13/13

(c) Hasonló részgráf

4.1. ábra. Gráf önmagával vett legnagyobb közös részgráfja IsoRank eljárással.

2

2

3

2/1

3

3/3

1

4

1

4

1/2

4/4

5

5

(a) Graph1

5/5

(b) Graph2

(c) Hasonló részgráf

4.2. ábra. Izomorf gráfok legnagyobb közös részgráfja IsoRank eljárással.

2

2

3

2/1

3

3/4

1

4

1

4

4/3

5

(a) Graph1

1/5

5

(b) Graph2

5/2

(c) Hasonló részgráf

4.3. ábra. Nem izomorf gráfok legnagyobb közös részgráfja IsoRank eljárással.

48

18

17

14 13 12 11 16 15

10

16

9 8

19 20 21 22 23

6

24 25

2

26

1

27

5 4 3 2

23

1

24

45

25

49

44

26

48 47 46 45

43

27

42 41

28 29

44 42

6

22

50

28

36 37 41 38 39 40

7

21

3

29 30 31 32

8

20 4

35

9

19 5

34

14 13 12 11 10

18

7

33

15

17

40

30

43

31

(a) Graph1

32

33 34 35 36 37

38

39

(b) Graph2 16/24

15/32 14/41 13/19 12/18

17/9 18/17

11/34 10/40 9/20

19/6

8/21

20/11

7/25

21/12

6/8

22/36

5/47

23/13

4/46

24/14

3/4

25/2

2/1

26/48

1/3

27/44 28/49 29/5 30/26 31/10 32/33

45/37

33/15 34/16 35/29 36/23

44/39

37/22 38/30 39/50 40/35

43/43 42/31 41/28

(c) Hasonló közös részgráf

4.4. ábra. Nagyobb, véletlen skálafüggetlen gráfok hasonló részgráfja.

49

Összefoglalás A dolgozatban egy központisági mértéket, a PageRank algoritmust tanulmányoztam. Bemutattam néhány hasonló megközelítésen alapuló mérőszámot, melyek egy csúcs szomszédainak központiságára építve mérik a centralitást. A Markov-láncok elméletére alapozva bemutattam, hogyan konstruálható olyan állapotátmenet-mátrix, melynek domináns sajátvektora a gráf megfelelő csúcsainak PageRank-értékeiből áll. Két lehetséges megközelítésben tárgyaltam a PageRank problémát : sajátérték-feladatként és lineáris egyenletrendszerként. Megmutattam, hogy a hatványmódszer hatékonyan alkalmazható a PageRank-vektor megtalálására, és bemutattam annak bizonyítását, hogy a módszer konvergenciasebessége az állapotátmenet-mátrix második sajátértékétől függ. Láttuk, hogyan fogalmazható át a sajátérték-probléma egy lineáris egyenletrendszerré, és igazoltuk, hogy annak megoldása valóban a PageRank-vektor. Megmutattam, hogy a modellben szereplő paraméter megfelelő választásával az átmenetmátrix kondíciószáma relatív kicsi, így a módszer stabil. Szintén megmutattam, hogy a bemeneti adatok kis mértékű perturbációja esetén a PageRank vektor is csak kicsit perturálódik, ezáltal eredményesen alkalmazható bizonytalanságot tartalmazó adathalmazokon is. Alkalmazásként áttekintettük az IsoRank módszer, mely két hálózat legnagyobb hasonló részgráfját állítja elő a hasonló csúcspárok kiválasztásával. A módszert MATLAB környezetben valósítottam meg, megadtam néhány teszteredményt, és röviden elemeztem is azokat.

50

Summary In this thesis I have studied a link-based ranking method, the PageRank algorithm. Like other such centrality measures it determines a scoring on the nodes from its neighborhood topology. Using Markov chains, I have shown how to construct a transition probability matrix, whose dominant eigenvector contains the PageRank values of the graph nodes. The PageRank problem was discussed in two different viewpoints : as an eigenvalue problem, and as a system of linear equations. I have showed that the power iterations method can be used efficiently to find the PageRank vector, and also that the rate of convergence depends on the second eigenvalue of the transition matrix. After that, we have seen how the eigenvalue problem can be transformed into a system of linear equations, then we have proved that the solution is the PageRank vector itself. As demonstrated, the proper choice of a parameter implies a relatively small condition number of the problem, so the model is stable. We have also seen, that small perturbation in the input causes only small perturbation of the PageRank vector, so the algorithm can be used efficiently on inaccurate data sets. As an application, the IsoRank method has been introduced, which produces the maximal common subset of two graphs by determinig similar nodepairs. The method has been implemented in MATLAB. Finally, test results and their short analysis have been given.

51

Köszönetnyilvánítás Szeretném megköszönni témavezetőmnek, Grolmusz Vincének a téma feldolgozásához nyújtott segítségét és tanácsait. Köszönettel tartozom családomnak, barátnőmnek és szüleinek, továbbá barátaimnak és kollégáimnak, akik megértésükkel és támogatásukkal mindannyian hozzájárultak a dolgozat elkészüléséhez.

52

Irodalomjegyzék [1] Faragó István – Horváth Róbert : Numerikus módszerek. BME TTK (Typotex Kiadó), Budapest, 2011. [2] Taher Haveliwala – Sepandar Kamvar: The second eigenvalue of the google matrix. Technical report, 2003, Stanford InfoLab. [3] Sepandar Kamvar – Taher Haveliwala: The condition number of the pagerank problem. Technical report, 2003, Stanford InfoLab. [4] Amy N. Langville – Carl D. Meyer: Google’s PageRank and Beyond : The Science of Search Engine Rankings. Princeton University Press, 2009. [5] Hyun Chul Lee – Allan Borodin: Perturbation of the hyper-linked environment. In Proceedings of the 9th annual international conference on Computing and combinatorics (konferenciaanyag). Berlin, Heidelberg, 2003, Springer-Verlag, 272–283. p. [6] Carl D. Meyer: Matrix Analysis and Applied Linear Algebra. SIAM, 2004. [7] Michelberger Pál – Szeidl László – Várlaki Péter : Alkalmazott folyamatstatisztika és idősor-analízis. Typotex Kiadó, Budapest, 2001. [8] M. E. J. Newman: Networks : An Introduction. Oxford University Press, 2010. [9] Lawrence Page – Sergey Brin – Rajeev Motwani – Terry Winograd: The pagerank citation ranking: Bringing order to the web. Tech report, 1999, Stanford InfoLab. [10] Rohit Singh – Jinbo Xu – Bonnie Berger: Pairwise global alignment of protein interaction networks by matching neighborhood topology. In Proceedings of the 11th annual international conference on Research in computational molecular biology, RECOMB’07 konferenciasorozat. 2007, Springer-Verlag. [11] Wettl Ferenc : Lineáris algebra. BME TTK (Typotex Kiadó), Budapest, 2011.

53

Függelék

54

function S = normalize(A) dim = size(A); rows = dim(1); cols = dim(2); S = zeros(rows,cols); for i = 1:rows, n = norm(A(i,:), 1); if (n ~= 0) S(i,:) = A(i,:) / n; else S(i,:) = ones(1,cols) / cols; end end

function M = unvec(v, cols) dim = size(v); M = v(1 : cols); for i = 1 : dim(1) / cols-1, M = horzcat(M, v(i * cols + 1 : (i + 1) * cols)); end

function y = power_method(A, x, tlevel, maxit) y = x / norm(x, 1); nu = y’ * A * y; err = 1; iter = 0; while (err > tlevel) & (iter < maxit) iter = iter + 1; y = A * y; y = y / norm(y, 1); nuold = nu; nu = y’ * A * y; err = abs(nu - nuold); end 55

function A = isorank(M1, M2, c, v) dim = size(M1); dim = dim(1); C = kron(M1, M2); C = Normalize(C); E = ones(dim^2, 1) * v’; G = c * C + (1-c) * E; r = ones(dim^2, 1); r = r / norm(r, 1); r = power_method(G’, r, 0.0001, 100); R = unvec(r, dim); nodes = min(size(R, 1), size(R, 2)); map = zeros(nodes, 2); for i = 1 : nodes, maxindx = find(R == max(max(R))); maxindx = maxindx(1); col = ceil(maxindx / nodes); row = maxindx - (col - 1) * nodes; R(row, :) = zeros(1, nodes); R(:, col) = zeros(nodes, 1); map(i,:) = [col, row]; end A = zeros(nodes, nodes); for i = 1 : nodes, for j = 1 : nodes, if (M1(map(i, 1), map(j, 1)) == 1) & (M2(map(i, 2), map(j, 2)) == 1) A(map(i, 1), map(j, 1)) = 1; A(map(j, 1), map(i, 1)) = 1; end end end

56

NYILATKOZAT

Név : Kiss Dániel ELTE Természettudományi Kar, szak : Matematika BSc ETR azonosító : KIDMABT.ELTE Szakdolgozat címe : A PageRank és alkalmazása

A szakdolgozat szerzőjeként fegyelmi felelősségem tudatában kijelentem, hogy a dolgozatom önálló munkám eredménye, saját szellemi termékem, abban a hivatkozások és idézések standard szabályait következetesen alkalmaztam, mások által írt részeket a megfelelő idézés nélkül nem használtam fel.

Budapest, 2013. január 7. a hallgató aláírása