Efficiente benadering van Google s PageRank (Engelse titel: Efficient approximation of Google s PageRank)

Technische Universiteit Delft Faculteit Elektrotechniek, Wiskunde en Informatica Delft Institute of Applied Mathematics

Efficiente benadering van Google’s PageRank (Engelse titel: Efficient approximation of Google’s PageRank)

Verslag ten behoeve van het Delft Institute for Applied Mathematics als onderdeel ter verkrijging

van de graad van

BACHELOR OF SCIENCE in TECHNISCHE WISKUNDE

door

Erik Berkhof Delft, Nederland Juli 2009

c 2009 door Erik Berkhof. Alle rechten voorbehouden. Copyright

BSc verslag TECHNISCHE WISKUNDE

“Efficiente benadering van Google’s PageRank” (Engelse titel: ”Efficient approximation of Google’s PageRank”)

Erik Berkhof

Technische Universiteit Delft

Begeleider Prof.dr.ir. C. Vuik

Overige commissieleden Dr.ir. H.X. Lin

Dr. J.G. Spandaw

Drs. A. Verweij

Juli, 2009

Delft

Voorwoord Dit verslag is gemaakt in het kader van het bachelorproject van de studie Technische Wiskunde aan de Technische Universiteit Delft. Van alle richtingen die er zijn in de wiskunde, trok de numerieke wiskunde mij het meest aan, zeker toen ik zag dat het onderwerp ”Hoe werkt Google?”bij de lijst van keuzen voor het project zat. Een uitgesproken moment om er achter te komen hoe de zoekmachine werkt waar ik wekelijks in zoek. Dankzij de duidelijke artikelen van Jan Brandts, werd het voor mij snel duidelijk wat het idee achter de Google lijst is. Tijdens colleges van numerieke wiskunde vakken wordt er voldoende tijd besteed aan verschillende methoden om vergelijkingen van matrices op te lossen. Op het moment dat je verschillende methoden kan toepassen in een onderzoek, krijg je een beter beeld wat de methoden doen en betekenen. De PageRank methode is een praktisch en leuk onderwerp om verschillende methoden op uit te testen. Ten slotte wil ik Prof.dr.ir. K. Vuik bedanken voor het begeleiden tijdens het project en het tot stand komen van dit verslag.

4

Inhoudsopgave 1 Inleiding 1.1 Opbouw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Doelstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 7

2 Voorkennis

7

3 PageRank model 3.1 PageRank . . . . . . . . . . . 3.2 Problemen in het model . . . 3.3 Creëren van de Google-matrix 3.4 PageRank vector . . . . . . . 4 Verschillende Methoden 4.1 De Power Methode . . 4.2 De Arnoldi Methode . 4.3 Jacobi en Gauss-Seidel 4.4 Methoden Combineren

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

8 8 11 13 17

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

20 20 21 23 24

5 Numerieke Experimenten 5.1 Gebruikte Data . . . . . . . . . . . . . . . . . . . . . 5.2 Internet Programma . . . . . . . . . . . . . . . . . . 5.3 Vergelijken Resultaten van Methoden . . . . . . . . . 5.3.1 Resultaten Power Methode . . . . . . . . . . 5.3.2 Resultaten Arnoldi Methode . . . . . . . . . 5.3.3 Resultaten Jacobi en Gauss-Seidel . . . . . . 5.4 Testen van de Stop Criteria . . . . . . . . . . . . . . 5.5 Combineren Power Methode en Arnoldi Methode . . 5.5.1 Arnoldi Methode tot een gegeven . . . . . . 5.5.2 Vast aantal stappen met de Arnoldi Methode 5.5.3 Verklaren Resultaten Combinatie Methode .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

25 25 25 29 29 30 31 33 34 34 35 37

6 Conclusie & Discussie 6.1 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Discussie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 37 38

7 Bijlagen 7.1 Creëren van een eigen matrix . . . . . . . . . . . . . 7.2 Maken van de Google matrix . . . . . . . . . . . . . 7.3 PageRank met de Power Methode . . . . . . . . . . 7.4 PageRank met de Arnoldi methode . . . . . . . . . . 7.5 PageRank met de Jacobi methode . . . . . . . . . . 7.6 PageRank met de Gauss-Seidel methode . . . . . . . 7.7 Combinatie Arnoldi methode en Power methode met 7.8 Combinatie Arnoldi methode en Power methode met

40 40 41 42 43 44 46 47 49

. . . . . . . . . . . . Methode . . . . . .

. . . .

. . . .

. . . .

5

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . error . . . . . . . . . vast aantal iteraties

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

1

Inleiding

De oorsprong van het internet, het ARPANET, komt uit 1969 en werd gebruikt door het Amerikaanse leger. In 1983 ging het ARPANET over op het internet zoals wij het kennen. Maar pas in de jaren negentig werd het bekend bij het grote publiek en was het voor iedereen toegankelijk. Iedereen kon er zijn of haar informatie op kwijt, waardoor het overzicht al snel verdwenen was. Larry Page en Sergey Brin (twee studenten van Stanford University in de VS) maakten gebruik van de structuur van het internetweb om van deze onoverzichtelijke hoeveelheid informatie een lijst te creëren waarbij de pagina’s gesorteerd worden op belangrijkheid. Dit bedrijf heet Google en werd in 1998 opgericht. In 1920 is het woord Googol ontstaan door de 9-jarige Milton Sirotta die van zijn vader de vraag kreeg om een term te verzinnen voor het getal 10100 . Larry Page en Sergey Brin maakten voor hun lijst gebruik van een enorme matrix, namelijk het internetweb. Voor deze enorme berekening wilde ze ook een term gebruiken van een enorm getal, het getal Googol. Maar door een schrijffout is dit Google geworden en dit hebben ze zo gelaten. Het web wordt steeds groter en er zijn momenteel meer dan 10 miljard pagina’s te vinden. Dit geeft grote berekeningen om de lijst samen te stellen. Een ander probleem is ook dat het web erg dynamisch is; bij ongeveer 40 procent van de pagina’s verandert de inhoud binnen een week en 23 procent zelfs dagelijks. Hierdoor moet de lijst regelmatig vernieuwd worden. Google is momenteel één van de grootste zoekmachines op het internet en wordt wereldwijd goed bezocht. Voor bedrijven is het een goede advertentie om snel zichtbaar te zijn in de lijst en wenselijk om zo hoog mogelijk te staan. Larry Page en Sergey Brin kwamen er achter dat de lijst (PageRank) gemanipuleerd werd door bedrijven, waardoor niet meer de belangrijkste site bovenaan kwam. Dit ging ten koste van de geloofwaardigheid van Google, waardoor ze besloten hebben om elke andere aanpassing van Google achter gesloten deuren te houden. In mijn verslag gaan we uit van de PageRank methode die de twee studenten uit Stanford ooit bekend hebben gemaakt.

1.1

Opbouw

Google maakt gebruik van de PageRank methode. Hiervoor hebben we een vierkante matrix nodig die aan geeft hoe de pagina’s naar elkaar linken via een hyperlink. Allereerst zullen we het model uitleggen van de PageRank. De matrix wordt opgesteld door middel van twee principes. Deze matrix heeft een paar vervelende eigenschappen, die we kunnen omzeilen door er een zogenoemde Google-matrix van te maken. De Google-matrix is een volle, stochastische, vierkante matrix, die we kunnen gebruiken als een Markov-keten. We kunnen hier de powermethode op toepassen om de gewenste vector (de lijst) te verkrijgen. Dit principe zal uitlegd worden in hoofdstuk 3. Bij de methode wordt gebruik gemaakt van de Power methode. Dit is een lineair convergerende methode die gebruik maakt van de eigenwaarden van de matrix. Er zijn meerdere methoden om het probleem van de PageRank op te lossen. De Arnoldi-methode is ook een methode die gebruik maakt van de bijbehorende eigenwaarden en heeft de eigenschap sneller te convergeren dan de powermethode. Ondanks deze eigenschap is het geen methode om toe te passen op onze enorme matrix. Voor ons probleem zijn er ook methoden om lineaire stelsels op te lossen, Gauss-Seidel en Jacobi. Al deze methoden zullen we toelichten in hoofdstuk 4.

6

Vervolgens zullen we een aantal methoden combineren om de berekening van de PageRank te versnellen. Hiervan worden de resultaten gegeven.

1.2

Doelstellingen

Voor het creëren van de Google-matrix maken we gebruik van verwijzingen tussen pagina’s en teleportatie (dit wordt uitgelegd in hoofdstuk 3). Hierin is α de kans dat er gebruik wordt gemaakt van verwijzingen. Deze α heeft effect op de convergentie van de Power methode. Dit zal mijn eerste deelvraag zijn: Welk effect heeft de waarde van α op de convergentie op de methode? De Google-matrix heeft eigenschappen die prettige voordelen hebben voor de methode. Eén van deze eigenschappen is dat de matrix een eigenwaarde van 1 heeft. Dit is mijn tweede doelstelling: Bewijs dat de maximale eigenwaarden van de Google-Matrix gelijk is aan 1. Mijn uiteindelijke doel is om de methode sneller te laten werken. Dit zou kunnen met een andere methode, maar misschien ook door methoden te combineren. Hier volgt mijn doelvraag: Is er een andere methode of een combinatie van methoden zodat de PageRank sneller gevonden kan worden?

2

Voorkennis

Voordat we starten met de uitleg van de PageRank methode, zijn er een paar stellingen en difinities die we moeten kennen. Stelling 1 (Gerˇsgorin Cirkel). [3](blz 106) Laat A een n × n-matrix. De eigenwaarden van matrix A liggen in de vereniging van de cirkels |z − aii | ≤

n X

|aij | waarbij z ∈ C

j=1,j6=i

Stelling 2 (Dekpunt). [5] (blz 277) Als f is gedefinieerd op een interval I = f : [a, b] → R en de volgende twee condities gelden: 1. f(x) behoort tot I wanneer x behoort tot I. 2. Er bestaat een constante K met 0 < K < 1 zodat voor elke u en v in I geldt |f (u) − f (v)| ≤ K|u − v| Dan heeft f een dekpunt r in I, f(r)=r. Als we starten met x0 in I, dan convergeert de iteratie xi+1 = f (xi ) naar r als i → ∞. Definitie 1 (Convexe Verzameling). [6] (blz 421) Een verzameling F ⊆ H heet convex wanneer geldt dat als x, y ∈ F , dan (1 − t)x + ty ∈ F voor alle 0 ≤ t ≤ 1. Definitie 2 (Stochastische Matrix). [4] (blz 219) Stel A is een n × n matrix. A is stochastisch als de som van elke kolom gelijk is aan 1. Definitie 3 (Irreducibele- en reducibele Matrix). Laat A een stochastische n × n- matrix. A is irreducibel als de limn→∞ An voor elk element Anij > 0 met 1 ≤ i, j ≤ n. Dit wil zeggen dat je van elk punt in de matrix een kans groter dan nul hebt om in elk ander punt te komen. A is reducibel als de limn→∞ An voor minstens één element Anij = 0 met 1 ≤ i, j ≤ n. 7

Definitie 4 (Primitieve Matrix). [1] (blz 173) Een matrix A is een primitieve matrix wanneer A is een niet-negatieve irreducibele matrix is die alleen één eigenwaarde r = ρ(A) op de spectrale cirkel heeft. Definitie 5 (Reccurente state). [7] (blz 134) Een state i ∈ S heet recurrent als fi = P (Xn = i voor een n ≥ 1X0 = i) = 1. Definitie 6 (Periodieke en Aperiodieke Matrix). [7] (blz 150) Stel i is een recurrente state. De periode d(i) van de state i is de grootst gemeenschappelijke deler van de set [n]

Ti = {n ≥ 1; pii > 0}. Een reccurente state met periode 1 heet aperiodiek. Stelling 3. [4] (blz 318) Als P een n ×n stochastische matrix is, dan is 1 een eigenwaarde van P. Nu we deze stellingen en definities gezien hebben kunnen we beginnen met de uitleg van het PageRank model.

3

PageRank model

Het doel van de PageRank methode is om een lijst te maken van belangrijke naar onbelangrijke pagina’s. In de lijst heeft de belangrijkste pagina de hoogste PageRank waarde en de onbelangrijkste pagina de laagste PageRank waarde. Maar hoe komt een pagina aan de waarde?

3.1

PageRank

De belangrijkheid van een pagina hangt af van de volgende twee principes: Een bladzijde is belangrijk als er naar wordt verwezen door een andere belangrijke bladzijde. Als een bladzijde naar veel bladzijden verwijst, dan hebben zijn verwijzingen minder waarde dan als hij maar naar enkele bladzijden verwijst. Voor een pagina geeft een verwijzing van een belangrijke pagina, die maar weinig verwijzingen weggeeft, een grotere verhoging van de PageRank waarde. Een pagina is belangrijk als hij linken krijgt van andere belangrijke pagina’s, maar die zijn weer belangrijk als ze weer linken krijgen van andere belangrijke pagina’s. Dit leidt tot een cirkelredenatie en geeft nog geen waarden. Hieronder volgt de definitie van de PageRank. Definitie 7 (PageRank). Veronderstel dat bladzijde Bi naar Li verschillende bladzijden verwijst. De PageRank van pagina Bi noemen we pi . Als Bi verwijst naar Bj , dan draagt Bi een hoeveelheid Lpii bij aan de PageRank van Bj , met 1 ≤ i, j ≤ n, waar n het totaal aantal bladzijden is. Voor pi geldt n X pk pi = c Lk k=1

c = 1 als Bk een verbinding heeft met Bi , zo niet dan c=0. Als Bi niet verwijst naar Bj , dan draagt Bi niks bij aan de PageRank van Bj .

8

Figuur 1: Een voorbeeld web met vier bladzijden Hoe dit werkt kunnen we het beste laten zien met een voorbeeld. Neem een web met maar vier bladzijden. Deze bladzijden linken met elkaar zoals hieronder. Als we kijken naar bladzijde B1 , dan krijgt hij een verwijzing van bladzijden B3 en B4 . Omdat bladzijde B3 naar totaal drie bladzijden verwijst, krijgt B1 een derde deel van de PageRank van bladzijde B3 . Bladzijde B4 verwijst naar twee bladzijden, dus krijgt B1 de helft van de PageRank van bladzijde B4 . De PageRank p1 van B1 bepalen we als volgt: p1 = p33 + p24 Op dezelfde manier bepalen we de PageRank van de andere drie pagina’s. p2 = p21 + p33 + p24 , p3 = p21 , p4 = p12 + p33 Om deze gelijkheden op te lossen moeten we een matrix creëren, deze matrix noemen we de hyperlink matrix H, zodat er geldt: Hp = p De definitie voor de matrix H is als volgt. Definitie 8 (Hyperlink matrix H). Hyperlink matrix H is een n×n-matrix , waarbij n het totaal aantal bladzijden is. Hij is de bijdrage van bladzijde Bi aan bladzijde Bj . Dit wordt als volgt gedefinieerd 1 Hij = Li als bladzijde Bi een verbinding heeft met bladzijde Bj . Met Li het aantal linken die bladzijde Bi geeft aan andere bladzijden. Zo niet dan Hij = 0. Een bladzijde mag naar zichzelf verwijzen, dus Hii hoeft niet gelijk te zijn aan 0. Eigenschappen matrix H P 1. De som van elke kolom van H is 1 of 0. nj=1 Hij = 1 met 1 ≤ i ≤ n als Bi geen Dangling node (dit begrip wordt in de volgende paragraaf uitgelegd). 2. De grootste eigenwaarde van H is maximaal 1. 3. H is een sparse matrix als n groot is. In de meeste gevallen verwijzen pagina’s naar een handje vol andere bladzijden, waardoor het grootste deel van de matrix uit nullen zal bestaan.

9

Bewijs eigenschappen van matrix H 1. We hebben aangenomen dat bladzijde Bi geen Dangling node is. Li is het aantal verbindingen die vanuit Bi vertrekken. Dit betekend dat er een Li aantal bladzijden Bj zijn die een link hebben vanuit Bi met 1 ≤ i, j ≤ n. Als we kijken naar matrix H dan geldt Hij = L1i als bladzijde Bi en bladzijde Bj een link heeft, anders is Hij = 0. Als we een P kolom j van H optellen dan geldt dat ni=1 Hkj = Li L1i = 1. Dus elke kolom van matrix H is gelijk aan 1 (Voor elke bladzijde die geen dangling node is). 2. Vanuit de lineaire algebra weten we dat det(A) = det(AT ) [4] (blz 269). Dan geldt ook dat de karakteristieke polynomen van A en AT gelijk zijn en zo ook de eigenwaarden van A en AT . We zoeken naar het gebied waar de eigenwaarden van H T zich bevinden. Hiervoor gebruiken we de stelling van Gerˇsgorin. We onderscheiden hier twee mogelijkheden. Als eerste kijken we als Hii = 0 en daarna als Hii 6= 0. We hebben een n × n-matrix. De stelling luidt nu als volgt: n X

|z − Hii | ≤

|Hij | waarbij z ∈ C

j=1,j6=i

Neem Hii = 0. We hebben gezien dat elke som van een kolom van H gelijk is aan 1 of T 0, Pnzodat geldt dat de rij van H gelijk is aan 1 of 0. Dan zien we met Gerˇsgorin dat j=1,j6=i |Hij | gelijk is aan 1 of 0. P Neem Hii = c met 0 < c ≤ 1. In dat geval geldt: nj=1,j6=i |Hij | = 1 − c. Als we Gerˇsgorin invullen: |z − c| ≤

n X

|Hij | = 1 − c

j=1,j6=i

|z| ≤ 1 Dus de eigenwaarden van H zijn kleiner of gelijk aan 1 en dus is de grootste eigenwaarden maximaal 1. 3. Dit is geen eigenschap die per definitie geldt voor de PageRank, maar in ons web van het internet is dit het geval. Nu we de theorie van de hyperlink matrix H hebben gezien, gaan we een voorbeeld hiervan geven. Als we ons voorbeeldweb beschouwen, dan komt de hyperlink-matrix H er als volgt uit te zien:   0 0 13 21  1 0 1 1  2 3 2  H=  1 0 0 0  2 0 1 31 0 Kies een vector p = [p1 , p2 , p3 , p4 ]T , met p 6= 0. Als we nu de gelijkheid Hp = p lineair oplossen, dan krijgen we de volgende waarden voor p:   6  9   p=k·  3  10 10

met de scalar k ∈ R. In ons voorbeeld is bladzijde vier de belangrijkste pagina, gevolgd door bladzijde twee, en de onbelangrijkste pagina is bladzijde drie. Hier is te zien dat bladzijde vier belangrijker is dan twee, ondanks het feit dat bladzijde twee meer linken krijgt. Dit komt doordat bladzijde twee, een belangrijke site, een link geeft aan bladzijde vier, zodat hij hoog komt te staan. Het voorbeeld kan goed opgelost worden door de ‘veeg methode’ die we kennen uit de lineaire algebra. Er gaat veel tijd in zitten om de vergelijking Hp = p op te lossen als de matrix groter wordt. We kunnen hier gebruik maken van de eigenwaarden en eigenvectoren van de matrix. Eerst een bekende definitie: Definitie 9. [4] (blz 249) Laat H een n×n matrix zijn. Een scalar λ is een eigenwaarde van H als er een vector p bestaat ongelijk aan 0, zodat Hp = λp. De vector p is een eigenvector van H corresponderend met eigenwaarde λ. Als de matrix H een eigenwaarde gelijk aan 1 heeft ,wat in ons voorbeeld zo is, dan hoeven we alleen de eigenvector horend bij deze eigenwaarde te vinden. In dat geval is λ = 1 en geldt er Hp = p. Matrix H heeft als eigenschap dat zijn maximale waarde 1 is, dus de grootste eigenwaarde kan ook kleiner zijn dan 1. Maar nu is de vraag of onze matrix altijd een eigenwaarde heeft van 1? Omdat de matrices te groot zijn om exact op te lossen, gebruiken een dekpunt iteratie. Bij het standaard model gebruiken we als dekpunt iteratie de Power methode.

3.2

Problemen in het model

Het voorbeeld uit de vorige paragraaf is een voorbeeld wat een mooi resultaat heeft. Maar het PageRank model wat we nu hebben heeft te maken met de volgende problemen: 1. Het web is onsamenhangend. In dit geval is H een reducibele matrix. 2. De dekpunt iteratie convergeert niet naar een oplossing. 3. De gelijkheid Hp = p heeft als enige oplossing de triviale oplossing p = 0. Bij het eerste punt is voornamelijk de startvector het probleem. Op het moment dat een web onsamenhangend is, is de oplossing afhankelijk van je startvector. In het web zijn er op dat moment twee of meer subwebben, die niet met elkaar corresponderen. Dit punt kan eenvoudig verholpen worden, maar is zeker een punt om rekening mee te houden. Het tweede probleem is iets wat bij grote matrices niet veel zal voorkomen, maar voornamelijk bij hele kleine matrices. Neem als web twee punten die alleen naar elkaar verwijzen. Dan zal de vergelijking er als volgt uitzien: 0 1 p=p 1 0 Neem als startvector p0 = [1, 3]T , die we toepassen op de Power methode (deze methode wordt in Hoofdstuk 4 uitgelegd). Dan is de volgende vector p1 = [3, 1]T en de vector erna is p2 = [1, 3]T . Dit blijft zo doorgaan, waardoor de dekpunt iteratie niet convergeert naar een oplossing.

11

De eerste twee problemen zijn beide voor onze enorme Google lijst niet zo’n groot probleem. Het derde probleem daarentegen is wel een groot probleem. We zijn opzoek naar een oplossing voor Hp = λp, waar de eigenwaarde λ = 1, zodat er geldt Hp = p. Op het moment dat er geen eigenwaarde gelijk aan 1 aanwezig is, dan is de enige oplossing de triviale oplossing. Dit probleem komt voort uit Dangling nodes. Definitie 10 (Dangling nodes). Een Dangling node is een bladzijde die naar geen andere bladzijde verwijst. Als Bi een Dangling node is, dan zijn al zijn bijdragen aan andere pagina’s gelijk aan 0. In het world wide web zijn zo’n 80% van de bladzijden Dangling nodes. Hierbij moet je denken aan pdf bestanden of plaatjes waarnaar verwezen kan worden, maar die zelf niet kunnen verwijzen. Dit betekent niet dat deze pagina’s niet belangrijk zijn. In een pdf bestand staat vaak nuttige informatie, maar zou vanwege het feit dat het pdf bestand niet kan verwijzen geen belangrijke pagina zijn. Omdat een Dangling node nergens naar verwijst, betekent dit dat de kolom van deze pagina helemaal nul is. Dit betekent dat het geen stochastische matrix meer is en dat hij niet meer vanzelfsprekend een eigenwaarde heeft van 1. Dit zou betekenen dat onze vergelijking alleen de triviale oplossing heeft. Hieronder geven we een voorbeeld. Neem het volgende web:

Figuur 2: Voorbeeld web met vier bladzijden, waarvan één dangling node In het voorbeeld zien we dat bladzijde twee geen verwijzingen heeft naar een andere bladzijde, bladzijde twee is een Dangling node. De matrix H is als volgt:   0 0 12 31  1 0 1 1  2 2 3  H=  0 0 0 1  3 1 0 0 0 2 De tweede kolom bestaat uit alleen nullen, waardoor je aan de matrix ziet dat we te maken hebben met een Dangling node. Voor dit probleem hebben we een oplossing gevonden.

12

3.3

Cre¨ eren van de Google-matrix

De hyperlink-matrix H kunnen we zien als een kansmatrix hoe we ons door het web bewegen. Neem aan dat bladzijde Bi naar Li andere bladzijden verwijst, waaronder bladzijde Bj . Als we op bladzijde Bi zijn aangekomen, dan is er de kans L1i dat we naar bladzijde Bj gaan. Stel dat bladzijde Bj een Dangling node is, dan zou in het geval van matrix H de weg ophouden. Als je op internet op zo’n pagina bent aangekomen is de enige mogelijkheid om weg te gaan, door in de navigatiebalk een ander adres in te vullen. Dit noemen we teleportatie. Definitie 11 (Teleportatie). Als er niet via een verwijzing, maar via de navigatiebalk naar een andere pagina gaat, wordt dat teleportatie genoemd. Laat n het totaal aantal webpagina’s. De kans dat een pagina naar een willekeurige pagina gaat is n1 voor elke pagina, inclusief naar zichzelf. We gaan er op dit moment vanuit dat er altijd gebruik wordt gemaakt van verwijzingen, behalve als we op een Dangling node terecht komen. Als we dit toepassen op ons web, dan betekent dit dat matrix H aangepast moet worden. De aangepaste matrix noemen we S. Definitie 12 (Matrix S). Matrix H bevat kolommen waar de som gelijk is aan nul. In dit geval is er sprake van een Dangling node. Laat n het totaal aantal webpagina’s zijn. Matrix S wordt als volgt gedefinieerd: n 1X S=H+ β i eT n i=1

waarbij β i = 1 vector als Bi een Dangling node is, anders is β i = 0 vector met 1 ≤ i ≤ n. Eigenschappen matrix S 1. De som van elke kolom van S is 1.

Pn

j=1 Sij

=1

2. Matrix S is een stochastiche matrix. 3. De grootste eigenwaarde van S is 1. Bewijs eigenschappen van matrix S 1. We hebben gezien dat de som van elke kolom van H gelijk is aan 1 als deze kolom niet hoort bij een Dangling node. Deze rijen zijn in S onveranderd gebleven en hebben nog steeds een som van 1. De enige kolommen die zijn aangepast zijn die behoren aan Dangling nodes. De som van deze kolommen is in H gelijk aan 0. In matrix S is elk element in deze kolom veranderd in n1 . Omdat er naar n aantal pagina’s wordt verwezen is de som van deze kolom n n1 = 1. Dus de som van elke kolom van S is 1. 2. Dit is een gevolg van eigenschap 1. Kijk hiervoor in de definities van Hoofdstuk 2. 3. Allereerst laten we zien dat de eigenwaarde maximaal 1 kan zijn. Dit gaat op exact de zelfde wijze als bij matrix H. We weten dat geldt dat de karakteristieke polynomen van A en AT gelijk zijn en ook de eigenwaarden van A en AT . We zoeken naar het gebied waar de eigenwaarden van S T zich bevinden. Hiervoor gebruiken we de stelling van Gerˇsgorin. We hebben een n × n-matrix. De stelling luidt nu als volgt: |z −

SiiT |

≤

n X j=1,j6=i

13

T |Sij | waarbij z ∈ C

We hebben gezien dat elke som van een kolom van S gelijk is aan 1, geldt dat de rij T van is aan 1. Neem SiiT = c met 0 ≤ c ≤ 1 en c ∈ Q. In dat geval geldt: Pn S gelijk T j=1,j6=i |Sij | = 1 − c. Als we Gerˇsgorin invullen: |z − c| ≤

n X

T |Sij |=1−c

j=1,j6=i

|z| ≤ 1 Dus de eigenwaarden van S zijn kleiner of gelijk aan 1 en dus is de grootste eigenwaarden maximaal 1. Maar nu de vraag of 1 ook een eigenwaarde is van S, want in dat geval is 1 ook gelijk de grootste eigenwaarde. We weten dat S een stochastische matrix is en dat elke kolom optelt tot 1. Neem een willekeurige vector x. Laat s(x) de som zijn van alle elementen van x. We maken de volgende vermenigvuldiging Sx = y. Als we kijken naar het ide element van x, dan wordt de waarde van dit element verdeelt over de elementen van y. Dit komt omdat de som van elke kolom optelt tot 1. Dit gebeurt bij elk element van x. Omdat alle kolommen van S optellen tot 1, betekent dit dat de waarde van s(x) exact hetzelfde is als s(Sx). Dus er geldt s(x) = s(Sx). We weten dat er Sx = λx met λ een eigenwaarde van S en x de bijbehorende eigenvector. Dan geldt er: s(Sx) = s(λx) = λs(x) We willen weten wanneer s(x) = s(Sx) geldt. Invullen geeft s(x) = λs(x). Deze vergelijking klopt als λ = 1 of als s(x) = 0. We hebben gezien dat s(x) = 1, dus moet λ = 1 zijn. Alle eigenwaarden λ ≤ 1 en er is een eigenwaarde gelijk aan 1, dus 1 is de grootste eigenwaarde. Als we dit toepassen op ons voorbeeld, dan krijgen we de volgens matrix S:   0 14 21 13  1 1 1 1  2 4 2 3  S=  0 1 0 1  4 3 1 1 0 0 2 4 In ons model gaan we er van uit dat we de verwijzingen gebruiken als deze er zijn. Een surfer zal niet alleen in het geval van Dangling nodes gebruik maken van de navigatiebalk. Er bestaat bij elke pagina een kans dat een persoon naar een andere willekeurige bladzijde gaat. Dit noemen we globale teleportatie. Definitie 13 (Globale Teleportatie). Laat 0 < α < 1 de kans zijn dat er gebruik wordt gemaakt van links naar andere sites (behalve als we te maken hebben met een Dangling node). Dan is (1 − α) de kans dat er gebruik gemaakt wordt van de navigatiebalk. Om de globale teleportatie in ons model te verwerken hebben we nog een matrix nodig die weergeeft dat er alleen gebruik wordt gemaakt van teleportatie. Deze matrix noemen we de pure teleportatie matrix. 14

Definitie 14 (Pure Teleportatie-matrix T). Matrix T is een n × n -matrix. In deze matrix wordt alleen gebruik gemaakt van teleportatie. Matrix T is als volgt gedefineerd:   1 ... 1 1 1  T = eeT =  ... . . . ...  n n 1 ... 1 Matrix T is een stochastische matrix. Als we weer kijken in ons voorbeeld, dan ziet onze teleportatie-matrix T er als volgt uit:  1 1 1 1   T = 

4 1 4 1 4 1 4

4 1 4 1 4 1 4

4 1 4 1 4 1 4

4 1 4 1 4 1 4

  

Nu hebben we alle gegevens om ook de globale teleportatie in de matrix toe te voegen. De matrix die we hier vervolgens uit krijgen noemen we de Google matrix G. Definitie 15 (Google matrix G). Stel G is een n × n -matrix. Laat α de kans zijn dat er via verwijzingen door het web wordt gelopen en dat (1 − α) de kans is dat dit gaat er door middel van teleportatie met 0 < α < 1. Matrix G is als volgt gedefinieerd: n

G = αS + (1 − α)T = α(H +

1X β i eT ) + (1 − α)T n i=1

waarbij β i = 1 vector als Bi een Dangling node is, anders is β i = 0 vector met 1 ≤ i ≤ n. Hieronder geven we een aantal eigenschappen van matrix G, die daaronder aangetoond worden. Eigenschappen van de Google matrix G Pn 1. De som van elke kolom van G is 1. j=1 Gij = 1. Hierdoor is G ook een stochastische matrix. 2. Het is een convexe combinatie van twee stochastische matrices S en T . 3. G is irreducibel. 4. G is aperiodiek. 5. G is primitief, want Gk > 0 voor een k (dit geldt namelijk voor k = 1). Dit impliceert dat er een unieke p bestaat en de Power methode uitgevoerd op G garandeerd convergeerd naar deze vector. 6. G is een volle matrix. 7. De grootste eigenwaarde van G is 1.

15

Bewijs eigenschappen van matrix G 1. We hebben gezien dat de som van elke kolom van S gelijk is aan 1. De kolommen van matrix T tellen ook op tot 1. Matrix S wordt in de Google matrix vermenigvuldigd met de scalar α. Als we kijken naar de ide vector van matrix S, dan is deze na de vermenigvuldiging opgeteld α. Matrix T wordt in de Google matrix vermenigvuldigd met de scalar (1 − α). Als we kijken naar de ide kolomvector van matrix S, dan is deze na de vermenigvuldiging opgeteld (1 − α). In de Google matrix worden deze twee weer bij elkaar opgeteld, zodat de ide kolomvector opgeteld weer 1 is. Dus elke kolom van matrix G is opgeteld 1 en G is dus een stochastische matrix. 2. Dit is volgens de definitie Convex, die staat in Hoofdstuk 2. 3. Elke pagina is doormiddel van teleportatie verbonden met elke andere pagina. Hierdoor is de matrix irreducibel. 4. Door de teleportatie matrix T heeft elk element uit G ook een lus naar zichzelf. Hierdoor is Gii > 0 voor alle i. 5. Zie de stelling van primitieve matrix in Hoofdstuk 2. 6. Matrix T zorgt ervoor dat er vanaf elke bladzijde naar elke andere bladzijde kan worden gegaan. Matrix T is dus een volle matrix. Hierdoor is matrix G ook een volle matrix. 7. Allereerst laten we zien dat de eigenwaarden maximaal 1 kan zijn. Dit gaat op exact dezelfde wijze als bij matrix H. We weten dat geldt dat de karakteristieke polynomen van A en AT gelijk zijn en ook de eigenwaarden van A en AT . We zoeken naar het gebied waar de eigenwaarden van GT zich bevinden. Hiervoor gebruiken we de stelling van Gerˇsgorin. We weten dat matrix G irreducibel is en dat er dus geldt Gii 6= 0. We hebben een n × nmatrix. De stelling luidt nu als volgt: |z −

GTii |

≤

n X

|GTij | waarbij z ∈ C

j=1,j6=i

Neem GTii = c met 0 < c ≤ 1 met c ∈ Q. In dat geval geldt: Als we Gerˇsgorin invullen: |z − c| ≤

n X

Pn

T j=1,j6=i |Gij |

= 1 − c.

|GTij | = 1 − c

j=1,j6=i

|z| ≤ 1 Dus de eigenwaarden van G zijn kleiner of gelijk aan 1 en is dus de grootste eigenwaarden maximaal 1. Maar nu de vraag of 1 ook een eigenwaarde is van G, want in dat geval is 1 ook gelijk de grootste eigenwaarde. We weten dat G een stochastische matrix is en dat elke kolom optelt tot 1. Neem een willekeurige vector x. Laat s(x) de som zijn van alle elementen van x. We maken de volgende vermenigvuldiging Gx = y. Als we kijken naar het ide element van x, dan wordt 16

de waarde van dit element verdeelt over de elementen van y. Dit komt omdat de som van elke kolom optelt tot 1. Dit gebeurt bij elk element van x. Omdat alle kolommen van G optellen tot 1, betekent dit dat de waarde van s(x) exact hetzelfde is als s(Gx). Dus er geldt s(x) = s(Gx). We weten dat er Gx = λx met λ een eigenwaarde van G en x de bijbehorende eigenvector. Dan geldt er: s(Gx) = s(λx) = λs(x) We willen weten wanneer s(x) = s(Gx) geldt. Invullen geeft s(x) = λs(x). Deze vergelijking klopt als λ = 1 of als s(x) = 0. We hebben gezien dan s(x) = 1, dus moet λ = 1 zijn. Alle eigenwaarden λ ≤ 1 en er is een eigenwaarde gelijk aan 1, dus 1 is de grootste eigenwaarde.

3.4

PageRank vector

We weten nu dat matrix G een eigenwaarde heeft gelijk aan 1 en er een niet triviale oplossing moet zijn van de vergelijking Gp = p. De matrix die Google gebruikt is te groot om op te lossen door de “ veeg methode” . We kunnen gebruik maken van het feit dat de matrix een stochastische matrix is. Het probleem kunnen we als volgt schetsen. We verdelen een hoeveelheid mensen over alle pagina’s. Al deze mensen gaan elke seconde naar een andere (of eventueel naar dezelfde) pagina. De kans hoe deze mensen zich door het web bewegen zijn aangegeven in de matrix G. Omdat we te maken hebben met een stochastische matrix zal dit leiden tot een stabiele oplossing, deze oplossing is de vector die we zoeken. Deze manier kunnen weergeven als de volgende dekpunt iteratie: p(k+1) = Gp(k) met gegeven startvector p(0) en k een niet negatief geheel getal. Deze methode wordt de Power methode genoemd (het is een simpele vorm van de Power methode). De Power methode zal in het volgende hoofdstuk verder uitgediept worden. De vector p(k) zal na enige iteraties weinig veranderen en de vector p goed genoeg benaderd hebben, zodat we de PageRank vector p hebben gevonden. Definitie 16 (PageRank vector). De PageRank vector p ∈ R is de unieke vector die voeldoet aan Gp = p en eT p = 1 Deze vector heeft aan elke pagina een waarde toegekend. De pagina met de hoogste waarde is de belangrijkste pagina, tot aan de pagina met de laagste waarde die het onbelangrijkste is. Op dit moment hebben we onze lijst gevonden. We besteden nu aandacht aan de volgende vragen: 1. Heeft de matrix G maar één eigenwaarde gelijk aan 1? 2. Zijn er niet meer vectoren die voldoen aan de vergelijking Gp = p? 3. Welke waarde heeft α en wat voor invloed heeft deze waarde? Allereerst zullen we laten dat er maar één eigenwaarde 1 is in matrix G.

17

Stelling 4. [1](blz 46) Als het spectrum van de stochastische matrix S is {1, λ2 , λ3 , ..., λn }, dan is het spectrum van de Google matrix G = αS + (1 − α)T is {1, αλ2 , αλ3 , ..., αλn }. Bewijs [2] (blz 12). We kiezen een reële n × (n − 1)-matrix X. Laat e = [1 . . . 1]T ∈ Rn . Definieer Z = (e|X) een niet-singuliere matrix. Neem y ∈ Rn en een reële n × (n − 1)-matrix Y zodat geldt (Z −1 )T = (y|Y ). Nu volgt dat: T T y y e yT X 1 0 −1 = Z Z= (e|X) = 0 I YT Y Te Y TX Nu zien we dat er geldt dat y T e = 1 en Y T e = 0. We weten dat er geldt: G = αS + (1 − α)T . Matrix T is symmetrisch en is te schrijven als T = n1 eeT . Nu geldt dat: 1 Z −1 GT Z = αZ −1 S T Z + (1 − α)Z −1 T T Z = αZ −1 S T Z + (1 − α) Z −1 eeT Z n T Omdat bij de matrix S de kolommen optellen tot 1, geldt er dat S e = e. Dit gebruiken we om Z −1 S T Z te bepalen. T T T y y y T T T S (e|X) = (S e|S X) = (e|S T X) = YT YT YT T y e yT S T X 1 yT S T X = Y T e Y T ST X 0 Y T ST X We weten vanuit de lineaire algebra dat S T dezelfde eigenwaarden heeft als Z −1 S T Z [8] (blz 21). We zien hierboven dat er sowieso een eigenwaarde is gelijk aan 1, dus zien we dat Y T S T X de eigenwaarden λ2 , ..., λn heeft. Nu beschrijven we Z −1 T Z : T T 1 1 1 y y e 1 T T T (n|eT X) = ee (e|X) = (e e|e X) = T T n Y n Y e n 0 1 n eT X 1 n1 eT X = 0 0 0 0 n Nu vullen we dit in: 1 Z −1 GT Z = αZ −1 S T Z + (1 − α) Z −1 eeT Z = n 1 T T T 1 y S X 1 αy T S T X + n1 eT X 1 ne X α + (1 − α) = 0 0 0 Y T ST X 0 αY T S T X We hebben gezien dat Y T S T X de eigenwaarden λ2 , ..., λn heeft. Er geldt dat Sx = λx, dus αSx = αλx. Dus heeft αY T S T X de eigenwaarden αλ2 , ..., αλn . Nu geldt ook dat de eigenwaarden van G gelijk zijn aan de eigenwaarden van Z −1 GT Z. Aan de matrix Z −1 GT Z is te zien dat 1 een eigenwaarde is en de rest van de eigenwaarden zitten in αY T S T X. Dus de eigenwaarden van Z −1 GT Z zijn 1, αλ2 , ..., αλn . Dit zijn ook de eigenwaarden van G. Dit is precies wat we wilde bewijzen. We zien dat de tweede eigenwaarde van G αλ2 is. De eigenwaarden van S zijn maximaal 1, dus als de waarde van α > 0, dan is de tweede eigenwaarde van G kleiner dan 1. Dit betekent dat er maar één eigenwaarde is gelijk aan 1. Dat betekent ook dat er maar één eigenvector is, op een scalar na, die voldoet aan de vergelijking Gp = p. 18

Stelling 5. Laat 0 < α < 1 en Gp = p, waar G de Google matrix is. Neem als startvector p0 , waarvan alle elementen groter zijn dan 0, waar we de Power methode op toepassen. Dan zijn alle elementen van de Google vector p groter dan 0. Met andere woorden, elke bladzijde heeft een positieve PageRank. Bewijs We hebben al gezegd dat we dit probleem kunnen zien als een Markov keten. Op elke bladzijde beginnen we met een hoeveelheid personen, die zich door het web bewegen. Hoe de mensen verdeeld zijn is onze startvector p0 . Het kan niet zo zijn dat een element van de startvector negatief is. Een bladzijde kan met een waarde van 0 beginnen, maar we kiezen ervoor dat bij elk element een positieve waarde is. Matrix G is een irreducibele stochastische matrix, wat betekent dat we vanaf elke pagina naar elke andere pagina toe kunnen. Alle elementen van G zijn groter dan nul. Bij elke vector pk met k > 0 is elk element in ieder geval niet negatief. Maar omdat je vanaf elke pagina een kans hebt om naar elke andere pagina te gaan, zal elke pagina een positieve waarde hebben. Dus is elke element in vector p positief. Stelling 6. Gegeven de Google matrix G, waarvoor geldt dat Gp = p. Laat r = µp een meervoud zijn van p met scalar µ ∈ R. Dan voldoet r aan de vergelijking Gr = r. Bewijs Laat r = µp met µ ∈ R. Gp = p ⇐⇒ µGp = µp ⇐⇒ Gµp = µp ⇐⇒ Gr = r

Een veelvoud van p veranderd alle elementen met een scalar µ, maar er veranderd niets aan de volgorde van de waarden van hoog naar laag. Dit gebeurt wel als µ < 0, maar dit kunnen we verhelpen door de absolute waarde te gebruiken: G|r| = |r|. We zitten nog de vraag wat de waarde van α is. We gebruiken hier de Power methode, deze methode benadert de vector p. De covergentie snelheid van de Power methode is weer afhankelijk van de waarde van α. Stelling 7. Kies de parameter α zodanig dat 0 ≤ α < 1. Neem de dekpunt- iteratie waarvoor geldt p(k+1) = Gp(k) . Laat p(0) een willekeurige startvector zijn, waarbij de som van alle elementen 1 moet zijn. Dan geldt ||p − p(k) ||1 ≤ αk ||p − p(0) ||1 Bewijs De snelheid van convergentie voor de Power methode is van de orde O = | λλ21 |k met k het aantal iteraties die zijn uitgevoerd, λ1 de grootste eigenwaarde en λ2 de op een na grootste eigenwaarde [9] (blz 561). Bij matrix G is λ1 = 1 en λ2 ≤ α. Voor de orde van matrix G geldt dat O = | λλ21 |k ≤ ( α1 )k = αk . Dan geldt het volgende: ||p − p(k) ||1 ≤ α||p − p(k−1) ||1 ≤ α2 ||p − p(k−2) ||1 ≤ ... ≤ αk ||p − p(0) ||1 En dit is precies wat we wilde bewijzen.

19

We zien nu dat de waarde van α ons informatie geeft over de snelheid van convergeren. De waarde van α ligt tussen 0 en 1. Als we α heel klein nemen, dus heel dicht bij 0, dan convergeert onze methode snel. Dit heeft als nadeel dat de informatie waar we mee begonnen, namelijk de hyperlink matrix H, haast geen invloed meer heeft op het model, terwijl het juist om die matrix gaat. In dit geval zouden we voornamelijk rekenen met teleportie, terwijl de principes van de PageRank gaan over de verwijzingen. We kunnen de waarde van α ook niet heel dicht bij 1 nemen, want dan betekent het dat het heel lang kan duren voordat de methode de gewenste vector heeft gevonden. We moeten dus een compromis vinden tussen deze twee nadelen. Hier behoeven we verder niet naar te zoeken, want dit is door Google zelf al bekend gemaakt. Google heeft bericht dat ze voor de waarde van α ≈ 0.85 gebruiken [1](blz 59).

4

Verschillende Methoden

In het vorige hoofdstuk is te lezen dat de PageRank methode gebruik maakt van de dekpunt iteratie de Power methode. Hoe deze methode precies werkt zullen we in dit hoofdstuk uitgeleggen. Om de gewenste vector te vinden hebben ze er voor gekozen de Power methode toe te passen, maar er zijn meerdere methoden om dit probleem op te lossen. De Arnoldi methode maakt net als de Power methode gebruik van de eigenwaarden van de matrix. Deze methode zullen we ook beschrijven in dit hoofdstuk. De vergelijking Gp = p kunnen we ook oplossen door een methode te gebruiken die lineaire stelsels oplost. Er zullen hier twee methoden uitgelegd worden, Jacobi en Gauss-Seidel. Deze methoden kunnen ook gecombineerd worden, wat we verder zien in dit hoofdstuk.

4.1

De Power Methode

De Power methode is één van de oudste methoden om van een matrix de grootste eigenwaarde en bijbehorende eigenvector te vinden. Bij deze methode vermenigvuldigen we een startvector met de vierkante matrix zodat we een nieuwe vector krijgen. Met de nieuwe vector doen we dezelfde vermenigvuldiging zodat we weer een nieuwe vector krijgen. Het principe hierachter is dat de bijdrage van de eigenvectoren afhangen van de bijbehorende eigenwaarden. Hoe groter de eigenwaarde, hoe groter de bijdrage is van de bijbehorende eigenvector. Als we deze vermenigvuldiging meerdere keren toepassen, dan zal de eigenvector met de grootste eigenwaarde dominant worden, zodat we deze eigenvector benaderen en zo ook de grootste eigenwaarde. Hieronder het algoritme in R, omdat we hier niet met complexe getallen hebben te maken:

De Power Methode p0 ∈ Rn is een gegeven startvector. for k = 1, 2, ... z k = Gpk−1 pk = z k /||z k ||2 normaliseren van de vector (k) T λ = pk−1 z k end

20

Deze methode benaderd na elke iteratie de grootste eigenwaarde met de bijbehorende eigenvector. Als de fout klein genoeg is, is de benaderde grootste eigenwaarde λ(k) en de bijbehorende eigenvector pk . De gevonden vector heeft een fout van orde: (k)

|λ

k ! λ2 − λ1 | = O λ1

De power methode convergeert lineair. Het is handig om de start vector p0 een norm te geven van 1. Omdat we in ons geval de vector vermenigvuldigen met een stochastische matrix, zal elke vector die uit een volgende iteratie volgt weer een norm hebben van 1. Doordat we dit weten kunnen we de power methode sneller laten werken.

4.2

De Arnoldi Methode

Bij de Arnoldi methode [10] (blz 499)zijn we op zoek naar de Hessenberg herleiding QT GQ = H, waarbij G onze google matrix is en de Hessenberg matrix Hk de volgende vorm heeft:   h11 h12 . . . ... h1k  h21 h22 . . . ... h2k      . . . . . .  Hk =    0 h32  .. ..  . . . .  . . . .  0 . . . . . . hk,k−1 hkk met k ∈ N. Als Q is gegeven door de matrix Q = [q 1 , ..., q n ] en we vergelijken de kolommen van GQ = GH, dan geldt er: k+1 X Gq k = hik q i i=1

met 1 ≤ k ≤ n − 1. We halen de laatste term die in de sommatie is verkregen eruit: hk+1,k q k+1 = Gq k −

k X

hik q i ≡ rk

i=1

met hik = q Ti Gq k . Als rk 6= 0, dan: q k+1 = rk /hk+1,k waar geldt dat hk+1,k = ||rk ||2 . Hieronder het algoritme:

De Arnoldi Methode r0 = q1 h10 = 1 k=0 >0

zodat ||q 1 ||2 = 1

21

while (hk+1,k 6= 0) q k+1 = rk /hk+1,k k =k+1 rk = Gq k for i = 1 : k hik = q Ti rk rk = rk − hik q i end hk+1,k = ||rk ||2 end

Effectiever is |λ(k) − λ1 | < met λ1 de grootste eigenwaarde van hk

Wij bepalen λ(k) = maximale eigenwaarde van Hk

Hierbij vormen de Arnoldi vectoren, de kolommen van matrix Qk , een orthonormale basis voor de Krylov subspace K(G, q 1 , k): span{q 1 , ..., q k } = span{q 1 , Gq 1 , ..., Gk−1 q 1 }. Na de k de iteratie is de Arnoldi fractorizatie GQk = Qk Hk + rk eTk met Qk = [q 1 , ..., q k ] en eTk = Ik (:, k). Bij elke iteratie wordt de Hessenberg matrix groter. Laat matrix G een n × n-matrix, dan is Hk een k × k-matrix met k ≤ n. Toch kunnen we uit matrix Hk de gewenste eigenvector benaderen die hoort bij de grootste eigenwaarde van matrix G(in ons geval eigenwaarde 1). Laat rk = 0, dan geldt dat λ(Hk ) ⊆ λ(G). Als y ∈ Rk een eenheids 2-norm vector voor Hk is en Hk y = λy, dan: (G − λI)x = (eTk y)rk Waar x = Qk y. In andere woorden: we zoeken van de Hessenberg de eigenvector die hoort bij de grootste eigenwaarde, een vector y van lengte k. Deze vector vermenigvuldigen we met de n × k-matrix Q om vervolgens onze gewenste vector x te verkrijgen. In ons geval is dit de PageRank vector. Het voordeel van deze methode is dat hij stabiel is, dat we ons geen zorgen hoeven te maken om een break down (dat de methode halverwege niet meer verder kan) en dat hij erg snel convergeert. Het nadeel van deze methode is dat hij gebruik maakt van de Gram Schmidt orthogonalisatie, zodat het hoeveelheid werk kwadratisch toeneemt. Dat houdt in dat elke volgende iteratie er steeds langer over doet, dat is bij enorme matrices, zoals de Goolge matrix, een vervelende bijkomstigheid. We moeten er rekening mee houden dat het stop criterium (hk+1,k 6= 0) niet zo goed is, want in sommige gevallen bereik je deze nooit. Verstandiger is om er voor te kiezen dat het stop criterium is |λ(k) − λ1 | < , met λ(k) de maximale eigenwaarde van Hk , λ1 de maximale eigenwaarde van G, we weten dat deze waarde λ1 = 1 en > 0. Sowieso is het niet mogelijk dat k > n, want dan zou de basis van de Hessenbergmatrix groter zijn dan de basis van matrix G.

22

4.3

Jacobi en Gauss-Seidel Methode

Stel G ∈ Rn,n waar Gii 6= 0 met i = 1, ..., n. Stel een vector b ∈ Rn . We nemen als voorbeeld n = 3. G11 u1 + G12 u2 + G13 u3 = b1

(1)

G21 u1 + G22 u2 + G23 u3 = b2

(2)

G31 u1 + G32 u2 + G33 u3 = b3

(3)

Als we deze omschrijven tot een uitdrukking in u1 , u2 en u3 krijgen we u1 = (b1 − G12 u2 − G13 u3 )/G11

(4)

u2 = (b2 − G21 u1 − G23 u3 )/G22

(5)

u3 = (b3 − G31 u1 − G23 u2 )/G11

(6)

Dit kunnen we oplossen met de Jacobi methode en de Gaus-Seidel methode. [11] ( blz 43) Bij de Jacobi methode beginnen we met een willekeurige startvector u(0) . Vervolgens voeren we herhaaldelijk de volgende berekening uit: ui+1 m

=

1 Gmm

n X

(bm −

Gmk uik )

k=1,(k6=m)

met m = 1, ..., n. Hieronder volgt het algoritme:

De Jacobi Methode Dit is voor één iteratie

for m = 1 : n P qm = (bm − k6=m Gmk uk )/Gmm u=q end

Jacobi gebruikt de waarde van de startvector om vervolgens een nieuwe vector te verkrijgen. Deze nieuwe vector wordt gebruikt voor de volgende iteratie. Gauss-Seidel past tijdens de iteratie de startvector aan, waardoor er steeds gebruik wordt gemaakt van de jongste waarden. Gauss-Seidel werkt als volgt: ui+1 m =

1 Gmm

(bm −

m−1 X

Gmk ui+1 − k

k=1

n X k=m+1

met m = 1, ..., n. Hieronder volgt het algoritme:

23

Gmk uik )

De Gauss-Seidel Methode Dit is voor één iteratie

for m = 1 : n P um = (bm − k6=m Gmk uk )/Gmm end

Bij beide methoden maken we gebruik van het volgende stopcriterium [11] (blz 47): ||b − Gui ||2 ≤ ||b||2

Als we kijken naar onze vergelijking Gp = p, kennen we niet de waarden van de rechterkant van het ‘=’-teken, terwijl we deze wel nodig hebben in de methode. Dit kunnen we als volgt oplossen. Gp = p ⇐⇒ Gp − p = 0 ⇐⇒ (G − I)p = 0 met I de n × n identiteits matrix en p 6= 0. Laat G0 = G − I en b = 0, dan hebben we de vergelijking G0 p = 0. Deze vergelijking kunnen we oplossen met Jacobi en met Gauss-Seidel.

4.4

Methoden Combineren

De PageRank maakt gebruik van de Power methode om de vergelijking Gp = p op te lossen, dit ondanks het feit dat de Arnoldi methode sneller convergeert. We hebben ook gezien dat de Arnoldi methode bij elke volgende iteratie er steeds langer over doet, dit is niet zo bij de Power methode. Omdat we te maken hebben met enorme matrices (de echte Google matrix is een vierkante matrix die meer dan 10 miljard lang is), is de Arnoldi methode op ten duur erg lang bezig met één iteratie. Zowel de Power, Jacobi en Gauss-Seidel methode convergeren lineair. Het is een optie om de Arnoldi methode te combineren met de Power methode. Omdat de Arnoldi methode bij de eerste paar iteratie gebruik maakt van een kleine Hessenberg matrix, is hij waarschijnlijk sneller dan de Power methode. Dit is ook het principe om de twee methoden te combineren. Deze combinatie kunnen we op twee manier toepassen. We kunnen gebruik maken van het feit dat de Arnoldi methode kleiner begint dan de Power methode. Stel dat Google matrix G een n × n-matrix is met k < n met n, k ∈ N en we hebben een start vector p0 zodat ||p0 ||2 = 1. We beginnen met de Arnoldi methode, zodat hij met behulp van kleine berekeningen een start kan maken om de gewenste Google vector p te benaderen. Op het moment dat de Hessenberg matrix zodanig groot wordt dat de Arnoldi methode meer werk is dan dat de Power methode zou zijn, bepalen we de benaderde vector tot zover en gaan we verder met de Power methode. We weten dat de Arnoldi methode sneller convergeert dan de Power methode. Deze eigenschap kunnen we ook gebruiken om de twee methoden te combineren. Laat de Arnoldi methode zijn 24

werk doen totdat we onder een aangegeven error zijn gekomen. Vanaf daar bepalen we de vector pi en gaan we over op de Power methode.

5

Numerieke Experimenten

Voordat we kunnen beginnen met het toepassen van de methoden, hebben we een goede dataset nodig. Deze data hebben we gevonden op het internet, met het programma surfer.m. Voordat we beginnen met het maken van de programma’s, is het handig om te kijken welke programma’s er al bestaan, of er nuttige informatie uit te halen valt. Zo’n programma hebben we gevonden, waardoor we een goed beeld kregen hoe de methoden werken in de PageRank methode. In de derde paragraaf geven we de resultaten van onze eigen programma’s. we bekijken hoe de vier methoden, die we in hoofdstuk 3 hebben besproken, werken met de PageRank methode. We zullen zien dat de Power methode als beste naar voren komt. Vervolgens bespreken we twee manieren om de Arnoldi methode en de Power methode te combineren, met de bijbehorende resultaten.

5.1

Gebruikte Data

Kleine voorbeelden, zoals die in Hoofdstuk 2 zijn gegeven, zijn handig om een beeld te krijgen hoe de methode werkt, maar niet groot genoeg om mee te experimenteren. Hiervoor moesten we testdata vinden van webpagina’s hoe deze met elkaar linken, het liefst van bestaande bladzijden. Op het internet is een MATLAB bestand te vinden, surfer.m [12], die deze data kan bieden. Vanaf een willekeurige site wordt zichtbaar hoe linkende pagina’s weer naar andere pagina’s verwijzen. Hierbij kan worden aangegeven tot hoeveel bladzijden we willen gaan. We krijgen vervolgens een matrix V (in het bestand noemen ze deze matrix G, maar dat kan voor verwarring zorgen) die weer geeft welke pagina’s er met elkaar linken. Als bladzijde Bi een verwijzing krijgt van Bj , dan is Vij = 1. Krijgt bladzijde Bi geen verwijzing van Bj , dan is Vij = 0. Vanuit deze matrix kan de hyperlink matrix H gecreërd worden. Daarnaast geeft het programma een vector u, die weergeeft wat de naam is van elke pagina. De naam van bladzijde Bi is weer gegeven bij ui . Het nadeel van het bestand surfer.m is dat het lastig is om enorme matrices te creëren. Op het moment dat er een pagina voorbij komt die het programma niet goed kan zien, of er klopte iets niet aan de paginia, stopte het programma met het zoeken van de andere linken. Hierdoor hebben we matrices gekregen van maximaal 130 sites, waarmee we hebben kunnen experimenteren. Omdat het experimenteren met grotere matrices een beter beeld geeft van de methode, hebben we naast het programma surfer.m zelf random data laten creëren. Hierbij werd rekening gehouden dat sites maar naar een handje vol pagina’s verwijzen en dat er voor ongeveer 80% Dangling nodes aanwezig waren. Hiermee kunnen we een matrix V (net als in de eerste alinea van deze paragraaf) creëren, die vervolgens kan worden omgeschreven naar een hyperlink matrix H. We krijgen ook een vertor u, waarbij de namen worden weergegeven met cijfers van 1 t/m n.

5.2

Internet Programma

Het zelf schrijven van eigen programma’s zorgt ervoor dat we een goed beeld krijgen hoe de methoden werken, hoe we ze kunnen be¨ınvloeden en kunnen combineren. Daarnaast is handig 25

om bestaande programma’s te zoeken die een beeld geven van wat we kunnen verwachten van de gekozen methoden. Zo’n programma hebben we gevonden die werkt onder MATLAB, pagerank.m [13]. De data die we hebben verkregen met surfer.m en de data van ons eigen programma, kunnen we toepassen op pagerank.m. Dit programma voert de PageRank methode uit met vijf verschillende methoden: Power methode, Gauss-Seidel methode, Arnoldi methode, BiCGSTAB en GMRES8. De eerste drie methoden zijn besproken in hoofdstuk 3. De laatste twee methoden zullen we ons niet in verdiepen, maar dadelijk aan de resultaten is te zien dat deze methoden voor ons probleem niet nodig is om meer van te weten. Wil je hier meer over weten is dit te vinden in het boek van C.W.Oosterlee & C.Vuik [11]. Zowel de Power methode als de Arnoldi methode maken gebruik van de eigenwaarden van de matrix om zo de vergelijking Gp = λp met λ = 1 op te lossen. De andere drie methoden lossen het stelsel (G − I)p = 0 op. Als we kijken naar de uitkomsten van het programma, die hierna volgen, geeft het aan dat hij gebruik maakt van de Arnoldi8. Dit betekent dat één iteratie in het programma gelijk staat met acht iteraties zoals de Arnoldi methode in Hoofdstuk 4 staat beschreven. In sommige situaties geeft het programma aan dat de Arnoldi methode na één iteratie al klaar is, maar dit zijn eigenlijk acht iteraties. We moeten dit meenemen bij het bekijken van de resultaten. We voeren het programma uit op vier verschillende grootte matrices. Hiervan geven we van alle vijf de methoden weer hoe lang de methoden erover doen en hoeveel iteraties zij nodig hebben. De methoden stoppen als hun stop criterium < 10−8 is bereikt. We bekijken een 1000 × 1000matrix, 2000 × 2000-matrix, 3000 × 3000-matrix en 4000 × 4000-matrix, de gecreërd zijn met de random generator. De resultaten staan hieronder aangegeven in tabel 1 t/m 4. Naam Algoritme Power Methode Gauss-Seidel Arnoldi8 BiCGSTAB GMRES8

Tijd (sec) 0.01 0.02 0.03 0.17 0.15

Aantal Iteraties 5 11 1 6 6

Tabel 1: Toegepast op een 1000 × 1000-matrix Naam Algoritme Power Methode Gauss-Seidel Arnoldi8 BiCGSTAB GMRES8

Tijd (sec) 0.03 0.08 0.07 0.26 0.18


Tabel 2: Toegepast op een 2000 × 2000-matrix

26

Naam Algoritme Power Methode Gauss-Seidel Arnoldi8 BiCGSTAB GMRES8

Tijd (sec) 0.06 0.16 0.14 0.48 0.31


Tabel 3: Toegepast op een 3000 × 3000-matrix Naam Algoritme Power Methode Gauss-Seidel Arnoldi8 BiCGSTAB GMRES8

Tijd (sec) 0.10 0.28 0.23 0.78 0.51


Tabel 4: Toegepast op een 4000 × 4000-matrix In de tabellen 1 t/m 4 is aangegeven hoelang elke methode er over doet om de gewenste vector p te benaderen met een error < 10−8 . Het aantal iteraties die een methode nodig heeft is interessant om te weten, maar het gaat er bij ons om dat de methode de vector kan benaderen in een zo kort mogelijk tijd. De uitslagen van de tijd geven we per matrix weer in een staafdiagram.

Figuur 3: De tijdsduur voor een 1000 × 1000-matrix

27




Als we de diagrammen hierboven bekijken, zien we dat de tijd die de BiCGSTAB en de GMRES8 nodig heeft om de vector te vinden, in alle vier de matrices opvallend langer duren dan de andere drie. We zien ook dat bij alle vier de figuren dat de Power methode als beste naar voren komt. De Gauss-Seidel methode en de Arnoldi methode lopen bij de eerste drie tabellen gelijk op, maar uiteindelijk zal Arnoldi toch sneller zijn. Het feit dat de PageRank methode gebruik maakt van de Power methode lijkt bij het zien van deze plaatjes een goede keuze. Maar we hebben nog niet gekeken hoe snel deze methoden convergeren.

Figuur 7: Convergentie snelheid bij de 2000 × 2000-matrix

28

We zien dat vrijwel alle methoden lineair convergeren. De Arnoldi methode is na enkele iteraties al klaar met het vinden van de oplossing. Dit geeft ons de motivatie om te kijken of het combineren van de Arnoldi methode en de Power methode een oplossing is voor het vinden van een snellere methode. Het programma pagerank.m geeft een goed beeld met welke methoden we het best aan de slag kunnen. Dit programma hebben we verder niet gebruikt voor ons verdere onderzoek, maar is gebruikt om een goed beeld te krijgen van de methoden.

5.3

Vergelijken Resultaten van Methoden

In hoofdstuk 3 hebben we vier verschillende methoden uitgelegd: de Power methode, Arnoldi methode, Gauss-Seidel methode en de Jacobi methode. Deze vier methoden zijn stuk voor stuk verwerkt in de PageRank methode om vervolgens de vector p te benaderen. Per methode bekijken we de uitslagen van verschillende grote matrices en verschillende errors > 0. We meten hier de tijdsduur van de methoden die we in de PageRank methode gebruiken, de Power methode, Arnoldi methode, Jacobi of Gauss-Seidel, dus niet de het PageRank methode zelf. Zowel de Power methode, Gauss-Seidel als Jacobi geven na hun iteraties de gewenste vector. De Arnoldi methode moet na de iteraties de vector, die meestal een kleinere dimensie heeft dan de Google vector, als nog met een matrix vermenigvuldigingen om de Google vector p te verkrijgen. Dit zal voor deze methode tijd kosten, waardoor hij misschien niet snel genoeg zal zijn. 5.3.1

Resultaten Power Methode

Allereerst kijken we naar de methode die door de PageRank zelf wordt gebruikt. De PageRank moet voldoen met elke willekeurige startvector p0 6= 0. We nemen hier het volgende stopcriterium: |λ(k) − λ1 | < met > 0. De resultaten zijn te vinden in tabel 5. (Iteraties is afgekort to it.) De tijd die de methode er over doet, zoals het in de tabel staat weer gegeven, is soms afwijkend dan wat er verwacht wordt. Neem bijvoorbeeld de matrix van grootte 30; bij een = 10−2 doet hij over drie iteraties volgens de tabel langer dan bij een = 10−4 met zes iteraties. De tijd die het programma weergeeft is telkens iets anders, maar de grote lijnen hoe de maten en errors afhankelijk zijn voor de tijd zijn er in af te lezen. Het mag duidelijk zijn dat hoe dichter we in de buurt van de echte vector p willen komen, dus hoe kleiner , hoe meer iteraties er nodig zijn. Ook is het duidelijk dat het langer duurt als er meer iteraties nodig zijn. Opvallend is dat hoe groter de matrix is, hoe minder iteraties de methode nodig heeft om de Google vector p te benaderen. Dit zou betekenen dat de convergentie snelheid van een random matrix afhankelijk is van zijn grote. We hebben gelezen in paragraaf 4.1 dat de convergentie snelheid van de Power methode afhangt van de twee grootste eigenwaarden: k ! λ2 |λ(k) − λ1 | = O λ1 Deze waarden geven we weer in de tabel 6.

29

maat matrix 5 30 50 130 200 1000 2000 3000 4000

= 10−2 0.0054 sec 4 it. 0.0065 sec 3 it. 0.0082 sec 4 it. 0.0057 sec 4 it. 0.0057 sec 2 it. 0.0159 sec 2 it. 0.0503 sec 2 it. 0.1028 sec 2 it. 0.1948 sec 2 it.





Tabel 5: Uitslagen van de Power methode

λ2 λ1

5

30

50

130

200

1000

2000

3000

4000

0.35496

0.23890

0.41590

0.20315

0.07680

0.03353

0.03709

0.03061

0.02637

Tabel 6: Convergentie snelheid In de tabel is te zien dat de convergentiesnelheid van de grote matrices sneller is dan de kleine matrices. Want we zagen in hoofdstuk 3 stelling 7 hoe kleiner de waarde van α = λλ21 , hoe sneller de methode convergeert. Dit verklaard waarom de grote matrices minder iteraties nodig heeft de Google vector p te benaderen. Het is voor ons niet duidelijk waarom de waarde van α kleiner is bij grotere matrices. Dit is een punt voor verder onderzoek. 5.3.2

Resultaten Arnoldi Methode

We willen weten hoelang deze methode er over doet om de vector p te benaderen. We tellen het aantal iteraties die de Arnoldi methode er over doet totdat zijn fout klein genoeg is. Op dat moment is de methode nog niet klaar, want dan moet er nog een matrix vermenigvuldiging gedaan worden om de Google vector te bepalen. In de tabel 7 bekijken we dezelfde matrices en errors als bij de Power methode. Als we deze tabel vergelijken met de uitkomsten van de Power methode, komen de uikomsten van de Arnoldi methode beter uit. Alleen bij een = 10−12 heeft Arnoldi het lastig, maar voor de rest is hij sneller. Volgens het internet programma zou de Power methode sneller aan de uitslag moeten komen dan de Arnoldi methode, dus dat hier de Arnoldi methode als snelste naar voren komt is onverwachts.

30

maat matrix 5 30 50 130 200 1000 2000 3000 4000






Tabel 7: Uitslagen van de Arnoldi methode Als stop criterium hebben we gebruikt: |λ(k) − λ1 | < met λ(k) de grootste eigenwaarde van de Hessenberg matrix Hk , λ1 de grootste eigenwaarde van de Google matrix G, deze waarde is 1 en met > 0. Dit stop criterium lijkt op het stop criterium van de Power methode. Of het eerlijk is om deze twee methoden met behulp van deze twee stop criteria te vergelijken bespreken we verder in dit hoofdstuk. Bij een = 10−12 hebben de matrices van grootte 2000 en 4000 een onverwachte uitslag. Het is vreemd dat deze methoden opeens zo veel meer iteraties nodig heeft dan daarvoor. Het kan zijn dat dit komt door het stop criterium. Dit is iets voor een verder onderzoek. 5.3.3

Resultaten Jacobi en Gauss-Seidel

We hebben gezien in hoofdstuk 4 dat we het probleem Gp = p kunnen omschrijven naar (G−I)p, zodat we met de Jacobi en Gauss-Seidel methode de oplossing voor de Google vector kunnen vinden. Tabel 8 geeft de uitslagen weer van de Jacobi methoden en tabel 9 geeft de uitslagen van de Gauss-Seidel methode. Omdat we bij deze methoden niet kijken naar de eigenwaarden van de matrix, maar het lineaire stelsel oplossen, hebben we een ander stop criterium dan de Arnoldi methode en de Power methode. We gebruiken hier als stop criterium: ||b − Gui ||2 ≤ ||b||2

31

maat matrix 5 30 50 130 200 1000 2000 3000 4000






Tabel 8: Uitslagen van de Jacobi methode

maat matrix 5 30 50 130 200 1000 2000 3000 4000





Tabel 9: Uitslagen van de Gauss-Seidel methode

32


Omdat het stelsel wat we moeten oplossen is (G − I)p = 0, betekent het dat b = 0. Daarom nemen we bij dit probleem als stop criterium || − Gui ||2 ≤ omdat we anders door 0 zouden moeten delen. Zoals we al verwachtten uit paragraaf 5.2 zijn deze methoden bij grote matrices langzamer dan de Power methode, dit geldt al vanaf = 10−2 . We hebben in ieder geval gezien dat zowel de Jacobi methode als de Gauss-Seidel methode een oplossing bieden voor het vinden van de Google vector p, maar dat ze niet op kunnen tegen de snelheid van de Power methode.

5.4

Testen van de Stop Criteria

We vergelijken hier vier verschillende methoden, maar wel met verschillende stop criteria. Bij de Power methode kijken we naar de grootste benaderde eigenwaarde, bij de Arnoldi methode kijken we naar de grootste eigenwaarde van de Hessenberg matrix Hk en bij de Jacobi en GaussSeidel methode kijken we naar de norm van de benaderde vector. Dit is misschien niet helemaal eerlijk, want we vergelijken verschillende fouten. We gaan nu testen of het stop criterium wel eerlijk is. De matrices die we gekozen hebben zijn klein genoeg om de echte waarde van p te bepalen voor de vergelijking Gp = p. We kiezen een willekeurige matrix om de echte Google vector p te bepalen. Dan nemen we van elke methode de benaderde vector p(k) , na de k de iteratie. Nu bepalen we van elke benaderde vector de echte fout als volgt: ||p(k) − p||2 < ||p||2 We hebben gekozen om de vectoren van de 2000 × 2000-matrix te vergelijken bij een error van = 10−8 en = 10−12 . De uitslagen staan in tabel 10. Error = 10−8 = 10−12

Power methode 4.07091168·10−8 1.84630541·10−12

Arnoldi methode 9.15848634·10−4 1.32283456·10−11

Jacobi methode 1.47115950·10−9 6.69763431·10−14

Gauss- Seidel methode 5.97446852·10−9 1.66240789·10−13

Tabel 10: Testen van stop criteria We zien in de tabel dat bij de Power methode, Jacobi en Gauss-Seidel methode de echte fout overeenkomt met het stop criterium, bij Jacobi en Gauss- Seidel zelfs beter. De Arnoldi daarentegen komt met zijn stop criterium niet onder de fout van de echte fout. Het is dus niet eerlijk om te zeggen dat de Arnoldi methode dus sneller is dan de Power methode. Als we de lijst van de sites bekijken, die horen bij de 2000 × 2000- matrix, van belangrijkste site naar onbelangrijkste site, dan komt de volgorde helemaal overeen. Dit hoeft niet altijd zo te zijn, want de volgorde kan afhangen van het tiende decimaal. Als we gaan kijken naar de echte Google matrix die groter is dan 10 miljard×10 miljard, is belangrijk om op twaalf decimalen nauwkeurig de waarden te weten. We hebben gezien dat de Arnoldi sneller is, maar niet met de gewenste fout. Dit maakt het interessant om de Power methode en de Arnoldi methode te combineren om het programma sneller te maken, maar wel met de gewenste fout. 33

5.5

Combineren Power Methode en Arnoldi Methode

Als we kijken naar de resultaten uit de vorige paragraaf, zien we dat de Arnoldi methode sneller is dan de Power methode, maar met een te grote . Elke iteratie van de Arnoldi methode duurt korter dan de iteraties die daar op volgen. Hij begint met een kleine matrix die steeds groter wordt totdat de eigenwaarde de gewenste fout heeft benaderd. De Arnoldi methode heeft ook de eigenschap sneller te convergeren dan de Power methode. Dit kunnen we gebruiken om de twee methoden te combineren.

5.5.1

Arnoldi Methode tot een gegeven

We maken gebruik van het feit dat de Arnoldi methode sneller convergeert dan de Power methode. Het idee is dat we de Arnoldi methode toepassen totdat de grootste eigenwaarde van de Hessenberg matrix een fout heeft die kleiner is dan een gegeven , om vervolgens de Power methode door te laten rekenen met de benaderde vector. Deze tijd wordt vergeleken met de tijd die de Power methode alleen nodig heeft om de vector te vinden. Deze uitkomsten kunnen we nu goed vergelijken met elkaar, omdat aan het eind van de combinatie methode hetzelfde stop critium geldt: |λ(k) − λ1 | < met λ1 = 1 en > 0. We bekijken hier alleen de matrices van grote 1000, 2000, 3000 en 4000 die we verkregen hebben met onze random generator, omdat het bij ons gaat om grote matrices. In de tabel geven we het verschil weer in tijd, dit doen we als volgt: Verschil in tijd = De tijd van de combinatie - De tijd van de Power methode Duidelijk mag zijn dat bij een positief verschil de Power methode sneller is en bij een negatief verschil de combinatie sneller is. In tabel 11 bekijken we de vector p met een fout = 10−8 . Boven aan in elke kolom is aan gegeven tot welke we de Arnoldi methode laten rekenen. Hier is ‘A’ de Arnoldi methode en ‘P’de Power methode. We bekijken ook hoeveel iteraties de Arnoldi methode en de Power methode maken in de combinatie methode. maat matrix 1000

2000

3000

4000

= 10−1 0.0106 sec A 2 it. P 3 it. 0.0243 sec A 2 it. P 4 it. 0.0470 sec A 2 it. P 3 it. 0.0939 sec A 2 it. P 3 it.

= 10−2 -0.0105 sec A 2 it. P 3 it. 0.0319 sec A 2 it. P 4 it. 0.0513 sec A 2 it. P 3 it. 0.0874 sec A 2 it. P 3 it.





Tabel 11: Verschil in tijd van de Power methode met de Combinatie methode. Tot een fout van = 10−8 .

34

Nu bekijken we de tabel 12 met een = 10−12 , maar met andere waarden in de kolommen. maat matrix 1000

2000

3000

4000






Tabel 12: Verschil in tijd van de Power methode met de Combinatie methode. Tot een fout van = 10−12 . We zien dat we winst hebben geboekt bij de 1000 × 1000-matrix. Maar hoe groter de matrices worden, hoe groter het verschil wordt in het voordeel van de Power methode. Dus voor de Google matrix zal deze methode geen tijdswinst opleveren. Als we kijken naar de iteraties van de Power methode en de Arnoldi methode zijn ze gelijk, ongeacht welke we willen bereiken. Maar als we kijken naar tabel 5 waar de uitslagen staan van de Power methode, zien we dat we telkens één iteratie van de Power methode minder hebben als we de combinatie methode gebruiken. We zien dat de matrices, ongeacht de fout die we willen bepalen, dezelfde iteraties maakt. Toch is de tijd niet overal hetzelfde. We maken in MATLAB gebruik van het commando ‘tic toc’, om te meten hoelang de methode erover doet. Deze waarden kunnen afwijken, zeker bij zulke kleine tijdsintervallen, maar eigenlijk zouden ze gelijk moeten zijn. In deze methode gaan we over naar de Power methode op het moment dat Arnoldi een gegeven heeft bereikt. We kunnen er ook voor kiezen dat de Arnoldi methode een vast aantal iteraties doet, waarna de Power methode het overneemt. Dit principe doen we hieronder. 5.5.2

Vast aantal stappen met de Arnoldi Methode

Hier maken we gebruik van het feit dat de eerste paar iteraties van de Arnoldi methoden sneller gaan dan die van de Power methode. Als eerst laten we de Arnoldi methode k iteraties uitvoeren, waar hij vervolgens zijn benaderde vector uitgeeft, die daarna op de Power methode wordt toe gepast. Deze tijd wordt wederom vergeleken met de tijd die de Power methode alleen nodig heeft om de vector te vinden. Ook hier bekijken we de matrices van grootte 1000, 2000, 3000 en 4000. Het aantal iteraties die de Arnoldi methode neemt zijn de aantallen 1 t/m 5. In tabel 13 zal duidelijk zijn dat we niet verder hoeven te gaan. In de tabel geven we het verschil weer in tijd, dit doen we als volgt: Verschil in tijd = De tijd van de combinatie - De tijd van de Power methode

35

Net als in de vorige combinatie methode geldt dat bij een positief verschil de Power methode sneller is en bij een negatief verschil de combinatie methode sneller is. We bekijken eerst de tabel als we de vector p willen benaderen met een fout = 10−8 . k is het aantal iteraties dat de Arnoldi methode neemt. De ‘P’ in de tabel geeft aan hoeveel iteraties de Power methode nog nodig heeft om onder de gewenste fout te komen. maat matrix 1000 2000 3000 4000

k=1 0.0056 sec P 4 it. 0.0230 sec P 5 it. 0.0458 sec P 4 it. 0.0880 sec P 4 it.





Tabel 13: Verschil in tijd van de Power methode met de Combinatie methode. Tot een fout van = 10−12 . In tabel 13 staan alleen positieve getallen, wat betekent dat de Power methode bij elke matrix en bij elke waarde van k sneller is dan de combinatie. We zien ook dat grotere waarden van k geen zin heeft, want hoe groter de waarde van k is, hoe groter het verschil in het voordeel van de Power methode. Maar wat gebeurt er als we een fout willen hebben van = 10−12 ? Dit is gegeven in tabel 14. maat matrix 1000 2000 3000 4000






Tabel 14: Verschil in tijd van de Power methode met de Combinatie methode. Tot een fout van = 10−12 . We zien dat het verschil erg klein is, maar toch is de Power methode sneller dan deze combinatie methode. We zien ook hoe groter de matrices worden, hoe groter het verschil wordt. We verwachten dan ook niet dat de combinatie methode bij nog grotere matrices een snellere uitslag krijgt dan de Power methode. Het aantal iteraties die de Power methode moet maken is duidelijk afhankelijk van het aantal iteraties die de Arnoldi methode moet maken. Als we tabel 12 en tabel 13 met tabel 5 vergelijken, zien we dat na één iteratie van de Arnoldi methode er evenveel iteraties moet worden gemaakt door de Power methode. Word er meer dan één iteratie gedaan met de Arnoldi methode, dan zijn er minder iteraties nodig van de Power methode. We hebben getest als k > 5, dan zal de Power methode altijd nog twee iteraties nodig hebben. 36

5.5.3

Verklaren Resultaten Combinatie Methode

Ondanks het feit dat de Arnoldi methode sneller convergeert in het begin, was de combinatie van Power methode en Arnoldi methode niet sneller dan de Power methode alleen. De verschillen waren bij onze matrices niet erg groot, maar we zagen dat de verschillen wel steeds groter worden naarmate de matrices groter worden. De Power methode begint met een startvector welke hij vermenigvuldigt met de Google matrix G, waarna hij gelijk de volgende vector heeft. De Arnoldi methode daarentegen moet na zijn iteraties, als hij onder de afgesproken fout zit, de eigenvector vinden van de bijbehorende eigenwaarde en daarmee nog een vermenigvuldiging met een matrix nemen. Dit laatste kost waarschijnlijk te veel tijd om van de Power methode te winnen. Daarnaast duurt een iteratie van de Arnoldi methode steeds langer, waardoor het niet effectief is om veel iteraties te nemen. We hebben gezien dat het tijdsverschil voor onze matrices erg klein is tussen de Power methode en onze combinatie methoden, maar voor de echte Google matrix zal de combinatie methode geen optie zijn.

6 6.1

Conclusie & Discussie Conclusie

In dit verslag zijn we bezig geweest met het begrijpen van de PageRank methode en het toepassen van verschillende oplosmethoden voor de vergelijking Gp = p, waar G de Google matrix en en p de Google vector is. Bij het begrijpen van de PageRank methoden hadden we ons de twee vragen gesteld: welk effect heeft de waarde van α op de convergentie en is de maximale eigenwaarde van de Google matrix G gelijk aan 1? Het bewijs dat de maximale eigenwaarde van G gelijk is aan 1 is te vinden in paragraaf 3.3. In paragraaf 3.3 is te lezen dat G = αS + (1 − α)T , waar S en T stochastische matrices zijn, waarbij T alle elementen gelijk zijn en groter dan 1. Hier door geldt dat de grootste eigenwaarden van G is λ1 = 1 en de op één na grootste eigenwaarde van G is λ2 ≤α. De PageRank k methode maakt gebruik van de Power methode, die een orde heeft van O = λλ12 . Nu geldt dat α = λλ21 , dus is de orde O = αk . De waarde van α heeft dus invloed op de convergentie snelheid. Daarnaast mag de waarde van α ook niet te laag zijn, anders gaat er veel informatie verloren. Het is bekent gemaakt door Google dat ze de waarde α = 0.85 gebruiken. Onze hoofd doelvraag was: Is er een andere methode of combinatie van methoden zodat de PageRank sneller gevonden kan worden? We hebben vier methoden bekeken: Power methode, Arnoldi methode, Jacobi en Gauss-Seidel methode. De eerste conclussie die we kunnen trekken is dat de Power methode niet de enige methode is om de PageRank te vinden. Bij alle vier de methoden vonden we uiteindelijk dezelfde volgorde van de sites, maar niet elke methode was even snel. De Jacobi methode en de Gauss-Seidel methode lossen een lineair stelsel op. We kunnen hiermee de PageRank vinden, maar door de relatief lange tijdsduur vielen deze af. De Power methode en de Arnoldi methode bepalen de grootste eigenwaarde met de bijbehorende eigenvector. Ons stop criterium van de Arnoldi methode voldeed niet voldoende, anders zou de deze methode sneller geweest zijn. Als we deze methoden vergelijken is de Power methode de beste optie. We hebben de Arnoldi methode en de Power methode gecombineerd. De Arnoldi methode convergeert snel en heeft bij het begin kort durende iteraties. Als de deze methode 37

een gegeven fout heeft bereikt neemt de Power methode het over. Omdat de Arnoldi methode naast zijn iteraties meer berekeningen moet maken om een vector te verkrijgen voor de Power methode, duurde deze methode toch te lang. De Power methode is sneller dan de andere drie methoden en sneller dan de combinatie methode. Met deze gegevens is de Power methode een goede kandidaat om toegepast te worden in de PageRank methode.

6.2

Discussie

In de Inleiding is vermeldt dat Google alle nieuwe ontwikkelingen voor het vinden van de Google vector geheim heeft gehouden, vanwege het feit dat mensen deze lijst proberen te manipuleren. Het principe van de PageRank zoals wij hem besproken hebben in het verslag is hierdoor misschien wat achterhaald ten op zichte van de echte Google vector berekening. Ondanks dat is het nog steeds interessant om de PageRank methode sneller te maken. Omdat het programma surfer.m ons geen enorme grote matrices kon bezorgen, hebben we zelf een random matrix generator gemaakt (is te vinden in de bijlagen). Hier nemen we een matrix van grote n, waar ongeveer 80% Dangling nodes en waar elke pagina maar naar een handje vol andere pagina’s verwijst (dit wordt ook random gekozen). Dit geeft misschien geen goed beeld van de matrix die Google gebruikt. Het kan best zijn dat er een pagina is, die naar 1000 sites verwijst, deze uitzonderingen hebben we niet meegenomen in de matrices. In paragraaf 5.4 hebben we de stop criteria van de methoden besproken. Deze hebben we vergeleken om een eerlijk beeld te krijgen van de methoden. Het probleem zat hem voornamelijk in het stop criterium van de Arnoldi methode. We hebben andere stop criteria gebruikt, bijvoorbeeld hk+1,k = ||rk ||2 ≤ . Hier was het probleem dat dit stop criterium in ons programma niet lager kwam dan = 10−4 . Om de methoden te vergelijken maakte we gebruik van het MATLAB commando ‘tic toc’. Dit kan ons een beeld geven hoe de methoden onderling met elkaar verschillen. Maar dit commando is niet nauwkeurig, zeker niet met zulke kleine tijdsintervallen waar wij mee werken. Voor een vervolg onderzoek zou het nauwkeuriger zijn om het aantal berekeningen, het aantal flops, te bepalen van een methoden. Als startvector gebruikte we p0 = n1 [1, ..., 1]T met n het aantal pagina’s. Google berekent elke twee weken opnieuw de PageRank van elke pagina. Misschien convergeert de methode sneller als ze als startvector de PageRank van twee weken terug nemen in plaats van de startvector die wij nemen. Want het web verandert wel veel, maar veel links blijven wel hetzelfde.

38

Literatuurverwijzing [1] A.N.Langville C.D.Meyer: Google’s PageRank and Beyond, the science of search engine rankings, Princeton University Press (2006), ISBN 978-0-691-12202-1 [2] J.Brandts: De PageRank van Google: de Grootste Matrixberekening ooit, Universiteit van Amsterdam (3 december 2007) [3] C.Vuik P.van Beek F.Vermolen J.van Kan: Numerieke Methoden voor DifferentiaalvergelijkingenVSSD, Delft(2006) [4] D. Poole: Linear Algebra, a modern introduction, Trent University(2003) ISBN 0-534-341748 [5] R.A.Adams: Calculus, a complete course (fifth edition), University of Britisch Columbia (2003), ISBN 0-201-79131-5 [6] R.E.Greene S.G.Krantz Function Theory of One Complex Variable(third edition), Graduate studies in mathematics (2006), ISBN 1065-7339 [7] E.A.Cator: Probability and Statistics II, TU Delft (2006) [8] R.J,Kooman: Lineaire Algebra 2, Universiteit Leiden (2005) [9] R.L.Burden & J.Douglas Faires: Numerical Analysis(8th edition), Thomason Brooks/Cole, VS (2005), ISBN 0-534-40499-5 [10] G.H.Golub & C.F. Van Loan: Matrix Computations, The Johns Hopkins University (Baltimore and London)(1996). third edition. [11] C.W.Oosterlee & C.Vuik: Scientific Computing, TU Delft (2008) [12] http://www.mathworks.com/moler/ncm/surfer.m [13] D. Gleich: http://www.mathworks.com/matlabcentral/fileexchange/11613 (2006)

39

7

Bijlagen

Hier geven we de MATLAB programma’s die we nodig hebben gehad voor het onderzoek. Elk programma in de bijlagen is toegepast voor een 2000 × 2000-matrix.

7.1

Cre¨ eren van een eigen matrix

savefile = ’n2000_eigen.mat’; n=2000; G=zeros(n);

%Het maken van een 2000x2000-matrix

for i=1:n for j=1:n r=rand; if r>0.6 G(i,j)=1; end end end nul=zeros(1,n); for i=1:n r=rand; if rand<0.8 G(i,1:n)=nul; end end U=zeros(n,1); for i=1:n U(i,1)=i; end save(savefile, ’U’, ’G’, ’n’)

40

7.2

Maken van de Google matrix

savefile = ’googlematrix_n2000.mat’; alpha=0.85; load n2000_eigen A=full(G); H=zeros(n); for j=1:n teller=0; for i=1:n teller=teller+A(i,j); end a=0; if teller>0 a = 1/teller; end for i=1:n if A(i,j)==1; H(i,j)= a ; end end end H; S=H;

%hyperlink matrix %maken matrix S

b=1/n; for j=1:n teller=0; for i=1:n teller=teller+H(i,j); end if teller==0 for k=1:n S(k,j)=b; end end end S; T=b*ones(n);

%transport matrix

google=alpha*S+(1-alpha)*T;

%maken Google matrix

save(savefile, ’H’, ’S’, ’alpha’,’T’, ’google’) 41

7.3

PageRank met de Power Methode

load n2000_eigen load googlematrix_n2000 format long epsilon=10^-8; P=0.5*ones(n,1);

%startvector

z=0.5*ones(n,1); %deze vector is nodig voor de power methode labda=0; stop=1; %power methode voor matrix G tic; for i=1:100 z=google*P; P=z/norm(z); labda=P’*z; stop=abs(1-labda); if stop<epsilon aantal_loops=i break end end toc; vector=P; %pagerankvector lijst_getallen=zeros(n,1); lijst_sites=zeros(n,1); for i=1:n M=max(P); for j=1:n if P(j,1)==M lijst_getallen(i,1)=P(j,1); lijst_sites(i,1)=U(j,1); P(j,1)=0; break end end end lijst_getallen; U; lijst_sites; 42

7.4

PageRank met de Arnoldi methode

format long load n2000_eigen load googlematrix_n2000 epsilon=10^-8; P=0.5*ones(n,1);

%startvector

%arnoldi r=P; j=0; B=1; bewaar_P=zeros(n); h=0; stop=3000; tel=0; tic; bewaar_P(1:n,1)=P; while stop>epsilon tel=tel+1; P=r/B; bewaar_P(1:n,j+1)=P; j=j+1; r=google*P; for i=1:j z=bewaar_P(1:n,i); h(i,j)= z’*r; r=r-h(i,j)*bewaar_P(1:n,i); end B=norm(r); M=max(eig(h)); stop=abs(1-M); h; if j< n h(j+1,j)=B; end if j==n break end end bewaar_P; h; h_a=h(1:tel,1:tel);

%Hessenberg matrix 43

Q=bewaar_P(1:n,1:tel); %Dit zijn de vectoren die er gebruikt zijn. [v,d] = eig(h_a);

%v zijn alle kolommen eigenvectoren d is op de diagonaal %alle eigenwaarden behorend bij de eigenvectoren %h_a*v== v*d Dit is nu precies hetzelfde vector_een=v(:,1); %dit is de eigenvector die behoord bij eigenwaarde 1 %de gebruikte P ("pagerank"-vectoren) maal de eigenvector van eigenwaarde 1 vector_google=Q*v(:,1); toc; aantal_iteraties=tel P=abs(vector_google);

%pagerankvector. %de vector kan ook geheel negatief zijn, daarom de %absolute waarde. lijst_getallen=zeros(n,1); lijst_sites=zeros(n,1); for i=1:n M=max(P); for j=1:n if P(j,1)==M lijst_getallen(i,1)=P(j,1); lijst_sites(i,1)=U(j,1); P(j,1)=0; break end end end lijst_getallen; U; lijst_sites;

7.5

PageRank met de Jacobi methode

format long load n2000_eigen load googlematrix_n2000 epsilon=10^(-8);

%stopcriterium

P=1/sqrt(n)*ones(n,1); I=eye(n); B=google-I;

%startvector, de norm gelijk is aan 1 %GP=P --> (G-I)P=0

44

%Jacobi tic; u=P; i=0; stop=10; while norm(-1*B*P)> epsilon i=i+1; for j=1:n som=0; for k=1:n if j~=k som=som+B(j,k)*u(k,1); end end P(j,1)=-1*som/B(j,j); end u=P; if norm(-1*B*P)< epsilon i break end end toc; P=u;

%pagerankvector

lijst_getallen=zeros(n,1); lijst_sites=zeros(n,1); for i=1:n M=max(P); for j=1:n if P(j,1)==M lijst_getallen(i,1)=P(j,1); lijst_sites(i,1)=U(j,1); P(j,1)=0; break end end end lijst_getallen; U; lijst_sites;

45

7.6

PageRank met de Gauss-Seidel methode

format long load n2000_eigen load googlematrix_n2000 epsilon=10^(-8); %stopcriterium P=1/sqrt(n)*ones(n,1); %startvector, de norm gelijk is aan 1 (norm(P)=1) I=eye(n); B=google-I; %GP=P --> (G-I)P=0 %Gauss-Seidel methode tic; i=0; while norm(-1*B*P)> epsilon i=i+1; for j=1:n som=0; for k=1:n if j~=k som=som+B(j,k)*P(k,1); end end P(j,1)=-1*som/B(j,j); end P; stop=norm(-1*B*P); if stop< epsilon i break end end toc; P; %pagerankvector lijst_getallen=zeros(n,1); lijst_sites=zeros(n,1); for i=1:n M=max(P); for j=1:n if P(j,1)==M lijst_getallen(i,1)=P(j,1); lijst_sites(i,1)=U(j,1); P(j,1)=0; break end end end lijst_getallen; U; lijst_sites;

46

7.7

Combinatie Arnoldi methode en Power methode met error

format long load n2000_eigen load googlematrix_n2000 epsilon2=10^(-4); epsilon=10^(-12);

%fout voor Arnodi methode %fout voor Power methode

P=1/sqrt(n)*ones(n,1);

%startvector

%arnoldi if epsilon>epsilon2 epsilon2=epsilon; end r=P; j=0; B=1; bewaar_P=zeros(n,100); h=0; stop=3000; tel=0; tic; bewaar_P(1:n,1)=P; while stop>epsilon2 tel=tel+1; P=r/B; bewaar_P(1:n,j+1)=P; j=j+1; r=google*P; for i=1:j z=bewaar_P(1:n,i); h(i,j)= z’*r; r=r-h(i,j)*bewaar_P(1:n,i); end B=norm(r); M=max(eig(h)); stop=abs(1-M); h; if j< n h(j+1,j)=B; end if j==n break end 47

end bewaar_P; h; h_a=h(1:tel,1:tel); %Hessenberg matrix Q=bewaar_P(1:n,1:tel); %Dit zijn de vectoren die er gebruikt zijn. [v,d] = eig(h_a);

%v zijn alle kolommen eigenvectoren %d is op de diagonaal alle eigenwaarden behorend % bij de eigenvectoren %h_a*v== v*d Dit is nu precies hetzelfde vector_een=v(:,1); %dit is de eigenvector die behoord bij eigenwaarde 1 %de gebruikte P ("pagerank"-vectoren) maal de eigenvector van eigenwaarde 1 vector_google=Q*v(:,1); aantal_iteraties_Arnoldi=tel; P=abs(vector_google); %pagerankvector. %de vector kan ook geheel negatief zijn, daarom de %absolute waarde. if epsilon<epsilon2 z=0.5*ones(n,1); labda=0; stop=1;

%deze vector is nodig voor de power methode

%power methode voor matrix G for i=1:100 z=google*P; P=z/norm(z); labda=P’*z; stop=abs(1-labda); if stop<epsilon aantal_loops_powermethode=i break end end arnoldi_power=toc; P; %pagerankvector

% Dit is de tijd voor de combinatie methode

end %Nu de google vector vinden met alleen de Power methode P=1/sqrt(n)*ones(n,1); %startvector z=1/sqrt(n)*ones(n,1); %deze vector is nodig voor de power methode labda=0; stop=1; %power methode voor matrix G 48

tic; for i=1:100 z=google*P; P=z/norm(z); labda=P’*z; stop=abs(1-labda); if stop<epsilon aantal_loops_alleen_power=i break end end powermethodetijd=toc; % Dit is de tijd voor de Power methode P;

%pagerankvector

verschil=arnoldi_power - powermethodetijd

%Tijdsverschil tussen de methoden

end

7.8

Combinatie Arnoldi methode en Power methode met vast aantal iteraties

format long load n2000_eigen load googlematrix_n2000 epsilon=10^-12; %fout k=3 %Dit is het aantal iteraties die je met Arnoldi wilt nemen P=1/sqrt(n)*ones(n,1);

%startvector

%arnoldi r=P; %deze vector is nodig voor de power methode j=0; B=1; bewaar_P=zeros(n); h=0; tel=0; tic; bewaar_P(1:n,1)=P; while tel~=k tel=tel+1; P=r/B; bewaar_P(1:n,j+1)=P; j=j+1; r=google*P; for i=1:j 49

z=bewaar_P(1:n,i); h(i,j)= z’*r; r=r-h(i,j)*bewaar_P(1:n,i); end B=norm(r); h; if j< n h(j+1,j)=B; end if j==n break end end Arnoldi_iteraties=tel; bewaar_P; h; h_a=h(1:tel,1:tel); Q=bewaar_P(1:n,1:tel); [v,d] = eig(h_a);

%Hessenberg matrix %Dit zijn de vectoren die er gebruikt zijn.

%v zijn alle kolommen eigenvectoren %d is op de diagonaal alle eigenwaarden behorend %bij de eigenvectoren

vector_een=v(:,1); %dit is de eigenvector die behoord bij eigenwaarde 1 %de gebruikte P ("pagerank"-vectoren) maal de eigenvector van eigenwaarde 1 vector_google=Q*v(:,1); P=abs(vector_google);

if epsilon
%pagerankvector. %de vector kan ook geheel negatief zijn, daarom de %absolute waarde. %deze vector is nodig voor de power methode

%power methode voor matrix G for i=1:100 z=google*P; P=z/norm(z); labda=P’*z; stop=abs(1-labda); if stop<epsilon aantal_loops=i break end end P; %pagerankvector end 50

Arnoldi_Power_tijd=toc;

% Dit is de tijd voor de combinatie methode

% NU ALLEEN POWERMETHODE P=1/sqrt(n)*ones(n,1);

%startvector

z=0.5*ones(n,1); labda=0; stop=1; tic; for i=1:100 z=google*P; P=z/norm(z); labda=P’*z; stop=abs(1-labda); if stop<epsilon aantal_loops=i; break end end powermethodetijd=toc; P;

% Dit is de tijd voor de Power methode

%pagerankvector

verschil=Arnoldi_Power_tijd-powermethodetijd

51

%Tijdsverschil tussen de methoden

Efficiente benadering van Google s PageRank (Engelse titel: Efficient approximation of Google s PageRank)

Recommend Documents