Internetwiskunde: over de webgraaf
Roel Niessen 31 augustus 2010
Bachelorscriptie Begeleider: dr. Jan Brandts
KdV Instituut voor Wiskunde Faculteit der Natuurwetenschappen, Wiskunde en Informatica Universiteit van Amsterdam
Samenvatting
Deze scriptie behandelt enkele aspecten van het relatief nieuwe vakgebied internetwiskunde. Na een korte inleiding over de webgraaf en de structuur hiervan, wordt in Hoofdstuk 2 de wiskunde achter drie bekende zoekalgoritmes (Googles PageRank, HITS en SALSA) uitgebreid beschreven. Het laatste hoofdstuk behandelt het zogeheten contactproces, waarmee het gedrag van virussen op het web kan worden bestudeerd.
Gegevens
Titel: Internetwiskunde: over de webgraaf Auteur: Roel Niessen,
[email protected], 5750628 Begeleider: dr. Jan Brandts Tweede beoordelaar: prof. dr. Rob Stevenson Einddatum: 31 augustus 2010 Korteweg de Vries Instituut voor Wiskunde Universiteit van Amsterdam Plantage Muidergracht 24, 1018 TV Amsterdam http://www.science.uva.nl/math
Inhoudsopgave 1 Introductie
3
1.1 De webgraaf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2 Lineaire algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.1
Singuliere waarden decompositie . . . . . . . . . . . . . . . . . . . . .
7
1.3 Markovketens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2 Structureren en organiseren: hoe vind ik wat ik nodig heb? 2.1 Googles PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10 10
2.1.1
Constructie van de PageRankvector . . . . . . . . . . . . . . . . . . .
11
2.1.2
Berekening van de PageRankvector . . . . . . . . . . . . . . . . . . .
14
2.2 HITS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2.1
Selectie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.2.2
Gewichtstoekenning . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.3 SALSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.3.1
Random walks over een bipartiete graaf . . . . . . . . . . . . . . . . .
3 Virussen op het web
25
30
3.1 Introductie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.2 Barabási-Albert-model en Pólya-urn-model . . . . . . . . . . . . . . . . . . .
31
3.3 Het contactproces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4 Populaire samenvatting
37
1
Voorwoord Met de opkomst van het internet is ook een nieuwe tak van wiskunde ontstaan, zogenaamde internetwiskunde. Aan de hand van de webgraaf, een wiskundige representatie van het web, kunnen allerlei interessante aspecten van het internet worden bestudeerd. De webgraaf is dan ook de gemene deler van alle hoofdstukken in deze scriptie. In Hoofdstuk 1 wordt, naast een uitleg en karakterisering van de webgraaf, een introductie gegeven in lineaire algebra en Markovketens. Hierin komen alle deelonderwerpen aan bod die we in de overige hoofdstukken nog zullen gebruiken. De machtswet, de stelling van Perron-Frobenius en de singuliere waarden decompositie zijn voorbeelden hiervan. In Hoofdstuk 2 komen drie wiskundige algoritmes aan bod die gebruikt worden in internetzoekmachines. Allereerst wordt het bekende PageRank van Google behandeld, en vervolgens het minder bekende hyperlink-induced topic search (HITS) algoritme. Tot slot bestuderen we het recentere SALSA, dat een nieuwe manier van zoeken introduceert. In Hoofdstuk 3 zullen we kennismaken met een manier om virussen op het web te modelleren. Dit doen we aan de hand van het contactproces en het Barabási-Albert-model. We zullen zien hoe de structuur van het web invloed heeft op de verspreiding en overlevingskansen van infecties. Tot slot wil ik graag mijn begeleider dr. Jan Brandts hartelijk bedanken voor alle vrijheid en steun die hij me heeft gegeven bij de totstandkoming van deze scriptie. Roel Niessen
2
Hoofdstuk 1 Introductie In dit hoofdstuk worden alle belangrijke de nities en stellingen geïntroduceerd, die we in een later stadium nodig zullen hebben. 1.1
De webgraaf
Als we alle webpagina's zien als punten van een graaf, en hyperlinks tussen webpagina's representeren met gerichte lijnen tussen deze punten, dan ontstaat er de zogeheten webgraaf. Deze webgraaf zullen we aanduiden met W . Het is eigenlijk misleidend om te praten over de webgraaf, omdat er continu webpagina's en hyperlinks bijkomen en verdwijnen. In het vervolg van deze scriptie zullen we dit voor lief nemen, en behandelen we W als een gegeven graaf. In deze sectie introduceren we enkele belangrijke eigenschappen van de webgraaf, die we later zullen gebruiken om wiskundige redeneringen omtrent W te kunnen maken. Volgens [1] heeft het web een vlinderdasstructuur (Eng.: bow-tie structure ), zie guur 1.1. De knoop van de vlinderdas bestaat uit een sterk samenhangende component, die de kern wordt genoemd. Eén kant van de das bestaat uit pagina's die naar de kern verwijzen, en de andere kant bestaat uit pagina's die een link uit de kern ontvangen. De overige webpagina's liggen ofwel in losstaande componenten, ofwel in uitlopers, die alleen in verbinding staat met pagina's buiten de kern. Er zijn verschillende schattingen gemaakt over de groottes van al deze componenten, maar de precieze cijfers zijn onbekend. Een duidelijk fenomeen is in ieder geval de groei van de kern, wat duidt op een groeiende samenhang tussen webbladzijden.
3
Figuur 1.1: De vlinderdasstructuur van het web. Misschien wel de belangrijkste eigenschap van W is de graadverdeling die voldoet aan de machtswet.
De nitie 1. Laat G een ongerichte graaf en k een niet-negatief geheel getal zijn. Dan de niëren we Nk,G als het aantal punten in G van graad k :
Nk,G = |{x ∈ V (G) | deg(x) = k}|.
Merk op: als |V (G)| = n, dan is Nk,G een geheel getal in het interval [0, n].
De nitie 2. Laat G een ongerichte graaf en k een niet-negatief geheel getal zijn. Laat verder |V (G)| = n. Dan is de graadverdeling van G gede nieerd als de rij (Nk,G | 0 ≤ k ≤ n).
De nitie 3. Laat G een ongerichte graaf zijn met |V (G)| = n. We zeggen dat de graadverdeling van G voldoet aan de machtswet als voor k → ∞ geldt Nk,G ∼ k −β , n
(1.1)
voor een zekere reële constante β > 1. We noemen β de exponent van de machtswet. Als de graadverdeling van G voldoet aan de machtswet, dan noemen we G een machtswetgraaf. We kunnen bovenstaande de nities als volgt interpreteren. Als G een machtswetgraaf is, dan heeft G relatief veel punten met een kleine graad, en voor grotere graden worden dit er exponentieel minder. Als we aan beide kanten van 1.1 de logaritme nemen, dan krijgen we log(Nk,G ) ∼ log(n) − β log(k).
4
Daarom zal de log-logplot van de graadverdeling van G een rechte lijn zijn met richtingscoëf ciënt −β . Bovenstaande de nities zijn telkens in termen van ongerichte grafen, terwijl we onze webgraaf W gede nieerd hebben als een gerichte graaf. We kunnen daarom de machtswetten voor zowel uit in te de niëren. en Nk,G de ingraadverdeling als de uitgraadverdeling bekijken door Nk,G Tot slot nog een de nitie die we later zullen gebruiken.
De nitie 4. We schrijven f = Θ(g) als g zowel een bovengrens als een ondergrens voor f is. 1.2
Lineaire algebra
We veronderstellen dat de lezer bekend is met elementaire lineaire algebra. De minder elementaire lineaire algebra, die we in de volgende hoofdstukken zullen tegenkomen, zullen we in deze sectie behandelen. Kernwoorden hierbij zijn dominante eigenwaarden en -vectoren, verbindingsmatrix en de Stelling van Perron-Frobenius. Als we p vanaf over "de norm" kxk van een vector, dan bedoelen we 2-norm Pde Pn nu spreken n 2 . De 1-norm kxk van een vector is gede nieerd als kxk = |x | i 1 1 i=1 |xi |. i=1
kxk2 =
De nitie 5. Laat A een n × n matrix zijn. Een eigenwaarde λ van A is een complex getal
dat voldoet aan Ax = λx voor een bepaalde niet-nul vector x ∈ Cn . De vector x wordt een eigenvector bij λ genoemd. Als λ1 , ..., λn de eigenwaarden van A zijn, en |λ1 | ≥ ... ≥ |λn |, dan noemen we λ1 de dominante eigenwaarde. Een bijbehorende eigenvector v1 noemen we de dominante eigenvector.
De nitie 6. Laat G een graaf zijn met V (G) = {1, ..., n}. Dan is de verbindingsmatrix A(G) als volgt gede nieerd:
A(G)i,j
( 1 als (i, j) ∈ E(G) = 0 anders.
Merk op dat A(G) symmetrisch is als G een ongerichte graaf is.
Propositie 1. Een n × n matrix A is diagonaliseerbaar precies als er basis voor Cn is die bestaat uit eigenvectoren van A.
−1 Bew¼s. Stel dat A diagonaliseerbaar is en dat A = P DP we P = . Hierbij noteren
v1
. . . vn , waarbij v1 , ..., vn vectoren zijn, en D =
dat AP = P D, dus Av1 . . . Avn
=
5
λ1 0 · · · 0 λ2 · · ·
.. .
.. .
0
0
λ1 v1 . . . λn vn
.
0 0 . Er geldt . . . .. . · · · λn
Dit betekent dat Avi = λi vi voor alle 1 ≤ i ≤ n, dus vi zijn eigenvectoren van A. De matrix P is inverteerbaar, dus de kolommen vi van P zijn lineair onafhankelijk. We concluderen dat {v1 , ..., vn } een basis is voor Cn . Anderzijds, stel dat {v1 , ..., vn } eigenvectoren zijn van A die een basis vormen vanCn . Laat λ1 , ..., λn de bijbehorende eigenwaarden zijn. We de niëren P = v1 . . . vn en D =
λ1 0 · · · 0 λ2 · · ·
.. .
.. .
0
0 zijn, is P
0 0 , zodat AP = P D. Omdat de kolommen van P lineair onafhankelijk . . . .. . · · · λn inverteerbaar. Dus A = P DP −1 en A is diagonaliseerbaar.
De nitie 7. We noemen een matrix positief (niet-negatief ) als alle entries positief (niet-
negatief) zijn. Notatie: A > 0 (A ≥ 0). Een niet-negatieve matrix is stochastisch als van elke rij de entries optellen tot 1. We noemen een niet-negatieve vector stochastisch als alle entries optellen tot 1.
De nitie 8. Een niet-negatieve n × n matrix A is primitief als Am > 0 voor zekere m > 0. De nitie 9. Laat A een matrix zijn met eigenwaarden λ1 , ..., λn . De spectraalstraal ρ(A) van A is
ρ(A) = max {|λi |}. 1≤i≤n
Stelling 1 (Stelling van Perron-Frobenius). Laat A een primitieve matrix zijn met spec-
traalstraal ρ(A) = λ. Dan λ = λ1 > 0, waarbij λ1 de strikt dominante eigenwaarde is met algebraïsche multipliciteit 1. Verder heeft λ1 een positieve corresponderende eigenvector. Voordat we deze stelling bewijzen, formuleren we het volgende lemma, dat in [10] bewezen wordt.
Lemma 1. Laat T een lineaire afbeelding zijn over een eindigdimensionale vectorruimte.
Laat Q een polyhedron zijn dat de oorsprong bevat in zijn inwendige, en zodanig dat Q onder een positieve macht van T wordt afgebeeld in zijn inwendige. Dan is ρ(T ) < 1. Met behulp van dit lemma zullen we de stelling bewezen.
Bewijs van Stelling 1. De eenheidssimplex S is de verzameling van niet-negatieve vectoren v zodat kvk1 = 1. Omdat de matrix A niet-negatief is, wordt S door A continu afgebeeld op S af door een vector v te sturen naar kvk−1 1 v . Volgens de dekpuntstelling van Brouwer heeft deze afbeelding een dekpunt, wat aantoont dat er een niet-negatieve eigenvector bestaat. Omdat A primitief is, is Am > 0 voor zekere m > 0, dus de eigenvector is zelfs positief. Laat λ de bijbehorende eigenwaarde zijn, die positief is. Laat r een positieve rechtereigenvector zijn. De nieer R als de diagonaalmatrix met diagonaalelementen gelijk aan de entries van r. De nieer vervolgens de matrix P =
1 −1 R AR. λ
6
Dan is ook P een primitieve matrix. De kolomvector Jn,1 is een eigenvector van P met eigenwaarde 1, dus P is stochastisch. We bekijken nu hoe P werkt op rijvectoren. P beeldt de eenheidssimplex S af op zichzelf en een macht van P beeldt S af op zijn inwendige. We weten dat er een positieve rijvector v in s is die door P niet wordt veranderd. Dus Q = −v + S is een polyhedron dat de oorsprong bevat in zijn inwendige. Maar nu heeft vanwege Lemma 1 de beperking van P tot de deelruimte V die wordt opgespannen door Q een spectraalstraal kleiner dan 1. Maar V is P -invariant met codimensie 1. 1.2.1
Singuliere waarden decompositie
In deze sectie bespreken we een handige factorisatie van een m × n-matrix A, de singuliere waarden decompositie. Deze zal later van pas komen bij het berekenen van eigenvectoren van de matrices AT A en AAT . Laat A een m × n-matrix zijn. Dan is AT A symmetrisch, dus ook diagonaliseerbaar, en heeft Rn een orthogonale basis {v1 , ..., vn } van eigenvectoren van AT A. Laat λi de bij vi behorende eigenwaarde zijn, dus AT Avi = λi vi . Dan geldt voor alle 1 ≤ i ≤ n kAvi k2 = = = =
(Avi )T Avi viT AT Avi viT λi vi λi .
We zien dat de eigenwaarden van AT A allemaal niet-negatief zijn. Door te hernummeren kunnen we nu de eigenwaarden als volgt ordenen λ1 ≥ λ2 ≥ ... ≥ λn ≥ 0.
Dit leidt ons tot de volgende de nitie en stelling.
De nitie 10. De singuliere waarden σ1 , ..., σn van√A zijn de wortels van de eigenwaarden λi , voor 1 ≤ i ≤ n.
van AT A, genoteerd in dalende volgorde. Dus σi =
Stelling 2 (Singuliere waarden decompositie). Laat A een m × n-matrix zijn met r niet-nul singuliere waarden. Laat Σ gede nieerd zijn door Σ=
D 0 0 0
,
waarbij D de diagonaalmatrix is met als entries de eerste r singuliere waarden van A, σ1 ≥ ... ≥ σr > 0. Dan bestaan er een m × m-orthogonaalmatrix U en een n × n-orthogonaalmatrix V zodanig dat A = U ΣV T .
7
Bew¼s. We geven hier slechts een schets van het bewijs. Voor het volledige bewijs verwijzen we de lezer door naar [9]. Aan de hand van de orthogonale eigenvectoren v1 , ..., vn van AT A en de singuliere waarden σ1 , ..., σr kunnen we een r-dimensionale basis vinden, die we kunnen uitbreiden tot een basis {u1 , ..., um } van Rm . Vervolgens de niëren we U=
u1 u2 · · ·
um
en
V =
v1 v2 · · ·
vn
.
We kunnen dan inzien dat U Σ = AV , en omdat V per constructie orthogonaal is, geldt U ΣV T = AV V T = A.
Propositie 2. Laat A een matrix zijn met singuliere waarden decompositie A = U ΣV T . Dan zijn de kolommen van V gelijk aan de eigenvectoren van AT A en de kolommen van U aan de eigenvectoren van AAT . Bew¼s. We gebruiken de singuliere waarden decompositie van A om AT A te berekenen. AT A = = = =
(U ΣV T )T U ΣV T V ΣT U T U ΣV T V (ΣT Σ)V T V DV −1 ,
waarbij D de diagonaalmatrix is met alle eigenwaarden van AT A. Dus V diagonaliseert AT A. Dit betekent dat de kolommen van V gelijk zijn aan de eigenvectoren van AT A. Het bewijs voor U en AAT gaat analoog. 1.3
Markovketens
In de volgende hoofdstukken wordt meermaals een beroep gedaan op kennis van Markovketens. In deze sectie geven de belangrijkste de nities en stellingen rondom dit onderwerp. Sleutelbegrippen hierbij zijn discrete-tijds Markovketens, transitiematrix, ergodiciteit en evenwichtsverdeling.
De nitie 11. Een (discrete-tijds) Markovketen M is een rij stochastische variabelen (Xn )n≥0 met de Markov-eigenschap:
P (Xn+1 = xn+1 | X1 = x1 , ..., Xn = xn ) = P (Xn+1 = xn+1 | Xn = xn ).
De verzameling van mogelijke waarden die Xn aanneemt, noemen we de toestandsruimte T .
8
De nitie 12. We de niëren de (een-staps)overgangskans pij van i naar j als pij = P (Xn = j | Xn−1 = i).
We de niëren de n-stapsovergangskans p(n) ij van i naar j als (n)
pij = P (Xn = j | X0 = i).
De nitie 13. Zij M een Markovketen met T = {1, ..., n}. De transitiematrix van M is de n × n matrix P zodat de (i, j) entry van P gelijk is aan pij .
Merk op dat de transitiematrix van een Markovketen stochastisch is. We kunnen elke Markovketen identi ceren met een gewogen, gerichte graaf G = (V, E). Hierbij is V = T en de gerichte lijnen corresponderen met de positieve overgangskansen pij .
De nitie 14. Een Markovketen M is irreducibel als voor alle i, j ∈ T er een n > 0 bestaat zodat p(n) ij > 0.
De nitie 15. Laat P een transitiematrix van een Markovketen zijn, en laat i ∈ T zijn. We noemen i aperiodiek als p(n) ii > 0 voor voldoend grote n. Een Markovketen heet aperiodiek als alle punten in de bijbehorende graaf aperiodiek zijn.
De nitie 16. Een Markovketen is ergodisch als deze irreducibel en aperiodiek is. Lemma 2. Een Markovketen met een primitieve transitiematrix is ergodisch. Bew¼s. Een primitieve transitiematrix P heeft de eigenschap dat P m > 0 voor zekere m > 0. Deze bewering is equivalent met irreducibiliteit, dus daar is aan voldaan. Maar dan is P ook meteen aperiodiek, en dus is de Markovketen ergodisch.
De nitie 17. De evenwichtsverdeling s van een Markovketen is een kansverdeling (dus een stochastische vector) met de eigenschap dat sT = sT P .
Stelling 3. Een ergodische Markovketen heeft een unieke evenwichtsverdeling s. Het bewijs van deze stelling gaat in feite op dezelfde manier als het bewijs van de Stelling van Perron-Frobenius. Er bestaat nog een ander ingenieus bewijs van bovenstaande stelling, waarbij twee Markovketens aan elkaar worden gekoppeld. Hiervoor zijn echter veel meer details over Markovketens voor nodig, en daarom verwijzen we de lezer hiervoor door naar [12].
9
Hoofdstuk 2 Structureren en organiseren: hoe vind ik wat ik nodig heb? Niemand weet uit hoeveel pagina's het web bestaat, omdat er dagelijks miljoenen pagina's bijkomen, verdwijnen en veranderen. Nownederland is een website die onlangs heeft geprobeerd dit aantal te bepalen, en hun schatting (mei 2010, [5]) is dat het web uit meer dan 20 miljard pagina's bestaat. Om internetgebruikers een beetje wegwijs te maken in deze wirwar die we de webgraaf noemen, hebben verschillende informatici in de jaren '90 geprobeerd structuren te ontdekken in webgraaf. Er werden zoekmachines gebouwd. Op die manier krijgen we bij een bepaalde zoekterm een lijst met bijbehorende pagina's, gesorteerd op relevantie. De wiskunde achter de verschillende sorteermechanismen is erg verschillend. In dit hoofdstuk bekijken we drie algoritmes, waarvan er in ieder geval twee worden gebruikt in bekende zoekmachines. Aan het eind proberen we iets te zeggen over hoe deze zoekmachines zich tot elkaar verhouden. 2.1
Googles PageRank
Eén van de bekendste zoekmachines op dit moment is zonder twijfel Google. Google werd in 1998 na jarenlang onderzoek ontworpen door twee Amerikaanse PhD-studenten, Larry Page en Sergey Brin. Achter het succes van Google gaat het wiskundige model PageRank schuil. Dit model kent aan elke webpagina een getal toe dat het belang van een pagina aangeeft. Google zorgt ervoor dat deze getallen maandelijks bijgewerkt worden, maar het rechtstreeks berekenen van de Pagerank van elke bladzijde is zelfs met de snelste computers een onmogelijke taak. Page en Brin hebben daarom een manier gevonden om binnen redelijke tijd alle Pagerankgetallen goed te benaderen. In deze paragraaf ontdekken we de precieze wiskunde achter Google. We zullen allereerst de PageRankvector de nieren en de existentie en uniciteit ervan aantonen. Tot slot bekijken we hoe we de PageRankvector met de machtsmethode kunnen benaderen. 10
2.1.1
Constructie van de PageRankvector
PageRank modelleert als het ware een willekeurige internetgebruiker. De PageRankwaarde van een webbladzijde is de kans dat een willekeurige bezoeker op een bepaald moment deze bladzijde bezoekt. Brin en Page baseerden hun model op de onderstaande twee principes. 1. Een internetgebruiker gaat meestal van een pagina p naar een andere pagina q doordat p een uitgaande link naar q heeft. 2. Het kan ook zo zijn dat een surfer plotseling naar een compleet willekeurige andere pagina gaat, door bijvoorbeeld het bijbehorende webadres in de adresbalk in te voeren. Dit laatste fenomeen noemen we globale teleportatie. Deze twee ideeën zullen we nu samenvoegen in een wiskundig model. Doordat PageRank een willekeurige surfer modelleert, betekent dit dat PageRank de stationaire verdeling van een random walk op de gerichte webgraaf W is. We willen nu graag de bijbehorende transitiematrix P construeren, die we de Google-matrix zullen noemen. Aan de hand van het eerste principe maken we een eerste versie P1 van de transitiematrix: 1 P1 (p, q) = deg + (i) 0
als (p, q) ∈ E(W ) anders.
Dit betekent dus dat een surfer vanuit een pagina p met gelijke kans naar een pagina q gaat, waarbij q willekeurig gekozen wordt uit de verzameling pagina's waar p naar verwijst. Hierbij nemen we dus impliciet aan dat de uitgraad van p ongelijk aan 0 is. Maar aangezien ongeveer 80 procent van de webpagina's wél een uitgraad gelijk aan 0 heeft (denk maar aan jpg- en pdf-bestanden), is dit geen goede aanname. Brin en Page hebben het probleem met deze zogenaamde dangling nodes op een handige manier opgelost. Om uit een dangling node weg te komen, kunnen we een nieuw webadres intikken in de adresbalk, waardoor we naar een willekeurige andere pagina gaan. Dit noemen we ook teleportatie. Op deze manier kunnen we een dangling node in ons model representeren als een pagina die naar alle pagina's binnen het web, inclusief zichzelf, verwijst. In P1 herkennen we dangling nodes als rijen met alleen maar nullen. Elk van deze rijen vervangen we nu door n1 J1,n , de rijvector met alleen maar entries n1 , waarbij n = |V (W )| het totale aantal webpagina's is. De transitiematrix die we op deze manier verkrijgen noemen we P2 . Het tweede principe van Brin en Page gaat over globale teleportatie: een surfer voert soms een willekeurig nieuw webadres in, en gaat dus niet via een hyperlink naar een andere pagina. Je gaat dan vanuit een pagina p met kans n1 naar een willekeurige pagina in W , inclusief p zelf, waarbij weer n = |V (W )|. Deze eigenschap wordt weergegeven door de transitiematrix 1 J , waarbij Jn,n de n × n matrix is met overal enen. n n,n 11
De twee principes kunnen we op de volgende manier combineren. Met kans c ∈ [0, 1] gaat een surfer via een link naar een andere website, en met kans 1 − c gebeurt dit via globale teleportatie. We noemen c de globale-teleportatie-constante en Brin en Page gebruiken c = 0, 85 in hun model. De nieer de Google-matrix nu als volgt: P = cP2 +
1−c Jn,n . n
Ter illustratie van deze de nitie bekijken we een concreet voorbeeld. Voorbeeld 1. In dit voorbeeld berekenen we de Google-matrix P van een web H dat bestaat uit vier pagina's V (H) = {1, 2, 3, 4}. Zie onderstaande graaf.
Figuur 2.1: De gerichte graaf H . De transitiematrix P1 bij H ziet er als volgt uit: 0 21 12 0 0 0 0 0 P1 = 0 1 0 1 . 2 2 1 0 0 0
We zien in de graaf dat punt 2 een dangling node is, omdat het naar geen enkel ander punt verwijst. Dit zien we ook terug in P1 , omdat de tweede rij uit louter nullen bestaat. Met het principe van teleportatie vinden we nu onze transitiematrix P2 :
0
1 2 1 4 1 2
1 2 1 4
0
1 1 4 4 . P2 = 0 0 12 1 0 0 0
Als we net als Brin en Page de globale-teleportatie-constante c gelijk aan 0,85 nemen, dan vinden we de volgende Google-matrix bij H : P = 0, 85P2 + 3 37 =
80 1 4 3 80 71 80
80 1 4 37 80 3 80
12
0, 15 J4,4 4 37 80 1 4 3 80 3 80
3 80 1 4 37 80 3 80
.
In het algemeen geldt dat de entries van de Google-matrix P niet-negatief zijn. Verder zullen we in het volgende lemma bewijzen dat de rijen van P altijd optellen tot 1, waardoor P de transitiematrix van een Markovketen is. Aan de hand van dit gegeven zullen we later de PageRankgetallen de niëren.
Lemma 3. De Google-matrix P is een stochastische matrix. Bew¼s. We onderscheiden twee gevallen. Geval 1. De uitgraad van i in W is positief. Omdat dan de ide rij van P2 gelijk is aan de ide rij van P1 , en omdat de rijen van P1 per de nitie optellen tot 1, geldt dat
ri
n X 1−c (Jn,n )i,j = c(P2 )i,j + n j=1 = c
n X
n
(P1 )i,j
j=1
1−cX 1 + n j=1
= c+1−c = 1.
Geval 2. De uitgraad van i in W is nul. Dan ri
n X 1−c = c(P2 )i,j + (Jn,n )i,j n j=1 n n X 1 1−cX = c + 1 n n j=1 j=1
= c+1−c = 1.
Dus P is de transitiematrix van een Markovketen. De volgende stelling beschrijft de convergentie van deze Markovketen. Merk hiervoor op dat alle entries van P positief zijn, en dus dat P primitief is.
Stelling 4. De Markovketen met transitiematrix P convergeert naar een bepaalde evenwichts-
verdeling s. Deze s is de dominante eigenvector van P met ksk1 = 1, corresponderend met eigenwaarde 1. Bew¼s. Volgens Lemma 2 is de Markovketen van P ergodisch, en dus volgens Stelling 3 heeft onze Markovketen een evenwichtsverdeling s. Volgens de Stelling van Perron-Frobenius is s nu de (unieke) dominante eigenvector met ksk1 = 1. Omdat sT P = sT , geldt dat de bij s behorende eigenwaarde gelijk is aan 1. 13
Nu kunnen we de PageRankvector de niëren.
De nitie 18. We de niëren de PageRankvector als de evenwichtsverdeling s van de Markov-
keten met transitiematrix P . Voor een zekere nummering V (W ) = {1, ..., n} is de ide entry van s dan de PageRank van de ide pagina van W .
Omdat sT P = sT , kan s met elementaire lineaire algebra worden berekend, bijvoorbeeld door het vegen met rijen en kolommen. Maar omdat er het aantal bladzijden (twintig miljard) tot de derde macht berekeningen voor nodig zijn, is dit zelfs voor de snelste computers een onmogelijke taak. In de volgende paragraaf zien we hoe Google dan wél maandelijks alle PageRankgetallen relatief snel benadert. 2.1.2
Berekening van de PageRankvector
PageRank wordt wel eens gezien als 's werelds grootste matrixberekening. In combinatie met het feit dat P geen nullen heeft, is de standaardmethode (vegen met rijen en kolommen) dus niet handig om s te bepalen. In deze paragraaf zien we dat de machtsmethode een eenvoudige techniek is, die de PageRankvector s snel en nauwkeurig benadert.
De nitie 19. De machtsmethode is een iteratie, zk+1 = P zk , met een gegeven startvector z0 ,
die een rij vectoren zk de nieert, waarbij iedere vector in de rij simpelweg P maal de vorige is.
Stelling 5 (Convergentie van de machtsmethode). Laat P en s gede nieerd zijn zoals hierboven, en laat z0 een willekeurige stochastische vector in Rn zijn. Kies de globale-teleportatieconstante c zodanig dat 0 ≤ c ≤ 1. Dan geldt
T
s − z0T P k ≤ ck sT − z0T . 1 1
Dit impliceert dat, als 0 ≤ c < 1,
lim z0T P k = sT .
k→∞
Bew¼s. Omdat zo veel getransponeerde vectoren nogal wat verwarring kunnen veroorzaken, zullen we de volgende equivalente bewering bewijzen:
s − Qk z0 ≤ ck ks − z0 k , 1 1
waarbij Q = P T . Hieruit zal dan ook volgen dat lim Qk z0 = s.
k→∞
14
De nieer Y 0 = s − z0 en de nieer voor k ≥ 1 de rij Y k = s − Qk z0 .
We zien dat voor iedere k de som van entries van Y k gelijk is aan nul. Maar dan geldt ook dat 1 Jn,n Y k = 0. (2.1) n
Voor elke Y ∈ Rn schrijven we nu Y+ voor de vector Y met alle negatieve entries vervangen door 0, en schrijven we Y− voor de vector Y met alle positieve entries vervangen door 0. Er geldt dus dat Y = Y+ + Y− en kY k1 = kY+ k1 + kY− k1 . De volgende eigenschap van Q2 = P2T (waarbij P2 hierboven is gede nieerd) zullen we later nodig hebben, maar bewijzen we eerst: kQ2 Y k1 ≤ kY k1 ,
(2.2)
voor alle Y ∈ Rn . Omdat de entries van Q2 niet negatief zijn en de kolommen van Q2 optellen tot 1, geldt dat kQ2 Y+ k1 = kY+ k1 en kQ2 Y− k1 = kY− k1 . Met behulp van de driehoeksongelijkheid volgt 2.2: kQ2 Y k1 = ≤ = =
kQ2 Y+ + Q2 Y− k1 kQ2 Y+ k1 + kQ2 Y− k1 kY+ k1 + kY− k1 kY k1 .
Per de nitie van Y k en met 2.1 volgt nu dat Y k+1 = = = =
s − Qk+1 z0 Q(s − Qk z0 ) QY k cQ2 Y k .
Met behulp van 2.2 impliceert dit dat
k+1
Y
= c Q2 Y k 1
1 ≤ c Y k . 1
De eerste bewering van de stelling volgt nu met inductie naar k . De tweede bewering volgt eenvoudig uit het feit dat 0 < c < 1. 15
De Google-matrix P is positief (en dus ook primitief) en stochastisch, en uit Stelling 1 volgt de existentie en uniciteit van de dominante eigenvector s van P , die voldoet aan ksk1 = 1. Op deze manier kunnen we dus door een aantal relatief simpele berekeningen een benadering krijgen van de PageRankvector s. De vraag is natuurlijk wel hoe snel de rij z0 , P z0 , P 2 z0 , ... convergeert naar de werkelijke waarde van s. Hoewel de machtsmethode over het algemeen langzaam convergeert, gebeurt dit voor PageRank vrij snel. Dit komt doordat we de waarde van c zelf mogen kiezen: hoe kleiner de waarde van c, des te sneller convergeert de machtsmethode. Als c = 0, dan duurt de iteratie slechts 1 stap, maar dan is ons model wel wat onrealistisch: niemand maakt immers alleen maar gebruik van globale teleportatie.Volgens Brin en Page is (bij c = 0, 85) een iteratie tussen de 50 en 100 stappen genoeg om tot een goede ranking te komen.
Voorbeeld 2. Beschouw de graaf uit guur 2.1. We gebruiken nu de machtsmethode om de PageRank van alle vier de pagina's te benaderen. We nemen dus de globale-teleportatieconstante c gelijk aan 0,85. Kies als startvector z0T = 41 14 41 41 . Na een korte iteratie van elf stappen vinden we s in vier decimalen nauwkeurig:
0, 2714 0, 3124 s= 0, 2192 . 0, 1970
We zien dat punt 2 het belangrijkst is, wat een voordehandliggend resultaat is. Immers, punt 2 is het enige punt met twee inkomende lijnen. Ter afsluiting van deze sectie bekijken we nog een voorbeeld van een groter web.
Voorbeeld 3. In dit voorbeeld benaderen we met behulp van de machtsmethode de PageRanks van de punten van de gerichte graaf G, zie Figuur 2.2.
Figuur 2.2: De gerichte graaf G. 16
Als we wederom de globale-teleportatie-constante c gelijk aan 0,85 nemen, dan vinden we de volgende Google-matrix bij G: P =
3 200 3 200 3 200 3 200 3 200 1 10 3 200 179 600 3 200 3 200
37 200 3 200 11 25 3 200 3 200 1 10 3 200 179 600 179 600 11 25
3 200 11 25 3 200 3 200 3 200 1 10 3 200 3 200 3 200 11 25
37 200 11 25 11 25 3 200 3 200 1 10 3 200 3 200 3 200 3 200
37 200 3 200 3 200 173 200 3 200 1 10 3 200 3 200 3 200 3 200
37 200 3 200 3 200 3 200 173 200 1 10 173 200 3 200 3 200 3 200
37 200 3 200 3 200 3 200 3 200 1 10 3 200 179 600 3 200 3 200
3 200 3 200 3 200 3 200 3 200 1 10 3 200 3 200 179 600 3 200
3 200 3 200 3 200 3 200 3 200 1 10 3 200 3 200 3 200 3 200
3 200 3 200 3 200 3 200 3 200 1 10 3 200 3 200 179 600 3 200
.
We gebruiken nu de machtsmethode om de PageRank van elke pagina te benaderen. Kies als startvector z0T = 101 101 101 101 101 101 101 101 101 101 . We vinden na een korte iteratie van zestien stappen de volgende PageRankvector in vier decimalen nauwkeurig: s=
0, 0377 0, 1241 0, 1056 0, 1485 0, 1821 0, 2610 0, 0452 0, 0348 0, 0261 0, 0348
.
(2.3)
We zien dat punt 2 zeker niet de beste PageRank heeft, ook al heeft 2 de hoogste ingraad. Dit heeft te maken met het feit dat de pagina's die naar 2 verwijzen zelf ook geen uitzonderlijk hoge PageRank hebben. Omdat het belangrijke punt 5 alleen naar punt 6 verwijst, krijgt 6 de hoogste PageRank in deze graaf. 2.2
HITS
HITS is een afkorting voor hyperlink-induced topic search, wat vrij vertaald zoveel betekent als 'op hyperlinks gebaseerde zoektocht naar onderwerpen'. HITS is een algoritme dat ook in 1998 door Jon Kleinberg werd geïntroduceerd. Een bekende zoekmachine die HITS als basis gebruikt is Teoma. Voor elke zoekopdracht vindt HITS een verzameling relevante webpagina's, waar vervolgens twee vectoren aan worden toegekend. Met de entries van deze vectoren, die net als de PageRankvector iteratief worden berekend, wordt het belang van een pagina bepaald. In deze sectie zien we hoe HITS op een wiskundige manier omgaat met een zoekopdracht. 17
2.2.1
Selectie
De eerste stap in het HITS-algoritme is de selectiestap. Bij een gegeven zoekopdracht z wordt een verzameling webpagina's Sz gezocht die mogelijk relevant zijn voor z . Hiervoor kunnen we bijvoorbeeld de collectie van pagina's nemen die z letterlijk bevatten. Op deze manier krijg je een verzameling die al gauw miljoenen pagina's kan bevatten. Maar we willen juist dat onze collectie niet te groot wordt, want anders komt er in de volgende stap veel rekenwerk bij kijken. Maar Sz moet wel zoveel mogelijk belangrijke pagina's, zogenaamde autoriteiten, bevatten, en moet daarom dus ook niet te klein zijn. Om een zo goed mogelijke collectie te genereren heeft Kleinberg de volgende drie eisen opgelegd aan Sz . Merk op: met relevante pagina's bedoelen we pagina's die letterlijk met de zoekopdracht te maken hebben, terwijl autoriteiten pagina's zijn die daadwerkelijk de belangrijke informatie bevatten. (1) Sz is relatief klein; (2) Sz is rijk aan relevante pagina's; (3) Sz bevat de meeste belangrijkste autoriteiten. Maar hoe vinden we een Sz die aan deze nogal subjectieve voorwaarden voldoet? Allereerste nemen we voor een positief geheel getal t (in de praktijk meestal rond de 200) de eerste t hoogst-geclassi ceerde pagina's bij een zoekopdracht z . De keuze voor deze pagina's is gebaseerd op een zoekmachine zoals AltaVista, die een pagina alleen vindt als de zoekopdracht er letterlijk in voorkomt. Deze collectie van t pagina's noemen we de wortelverzameling Wz . Deze verzameling voldoet aan de eerste twee voorwaarden, maar bevat over het algemeen niet de meeste belangrijkste autoriteiten.
Figuur 2.3: Uitbreiding van een wortelverzameling tot een basisverzameling. We kunnen nu wel onze Wz gebruiken om te proberen een verzameling Sz te construeren die wél voldoet aan alledrie de eisen. We beschouwen nu een belangrijke autoriteit bij onze zoekopdracht. Het kan best zo zijn dat deze pagina niet in Wz zit, maar volgens Kleinberg mogen we aannemen dat er minstens één pagina in Wz is die verwijst naar deze autoriteit. 18
Dus we kunnen het aantal autoriteiten in Wz uitbreiden door er pagina's aan toe te voegen die op een of andere manier een verband hebben met een pagina in Wz . Hiervoor wordt de volgende procedure gehanteerd. Laat Wz de verzameling pagina's zijn zoals hierboven gede nieerd en laat p ∈ Wz zijn. De nieer Γ+ (p) als de verzameling pagina's waar p naar verwijst en Γ− (p) als de verzameling pagina's uit de webgraaf W die naar p verwijzen. We krijgen nu Sz door Wz voor alle p ∈ Wz tegelijkertijd uit te breiden met Γ+ (p) en met d willekeurige pagina's uit Γ− (p), waarvoor d een van tevoren bepaald positief geheel getal is. We noemen Sz de basisverzameling voor z . Vervolgens willen we bij deze verzameling webpagina's een graaf maken, door alle relevante links tussen de pagina's toe te voegen. Beschouw hiervoor allereerst de door Sz geïnduceerde deelgraaf van W , notatie W [Sz ]. We maken onderscheid tussen twee soorten links in W [Sz ], links die naar een pagina met een andere domeinnaam verwijzen, en links die naar een pagina binnen het eigen domein verwijzen. De links van het tweede soort dienen bijna altijd ter navigatie binnen een website, en ze voegen daarom weinig toe aan de relevantie. De bijbehorende lijnen uit W [Sz ] halen we weg uit de graaf, en de overgebleven graaf noemen we Gz . Dit is de graaf waarmee we nu gaan bepalen welke webpagina's het relevantst zijn bij een bepaalde zoekopdracht. 2.2.2
Gewichtstoekenning
In de volgende stap berekent het HITS-algoritme voor elke pagina p uit de basisverzameling Sz = V (Gz ) twee niet-negatieve reële getallen, het autoriteitgewicht en het hubgewicht van p. Een hub is een pagina die naar veel relevante autoriteiten verwijst. Als p een hoog autoriteitgewicht heeft, dan is p een goede autoriteit, en als p een hoog hubgewicht heeft, dan is p een goede hub. Er zit een interessante heuristiek achter de berekening van het autoriteit- en hubgewicht. Allereerst bekijken we hoe je autoriteiten en hubs zou kunnen herkennen in de graaf Gz . Binnen Gz zijn er veel pagina's die verwijzen naar autoritaire pagina's, waardoor autoriteiten een hoge ingraad zullen hebben. Volgens Kleinberg is er zelfs aanzienlijke overlap tussen de pagina's die naar autoriteiten verwijzen, omdat alle autoritaire pagina's grotendeels over hetzelfde onderwerp gaan. Goede hub pagina's worden dan ook herkend door het feit dat ze veel links hebben naar belangrijke autoriteiten. Maar op deze manier lijkt er een cirkelredenering te ontstaan: een goede hub is een pagina die naar veel goede autoriteiten verwijst, en een goede autoriteit is een pagina waarnaar verwezen wordt door goede hubs. Dit schijnbare probleem heeft Kleinberg opgelost door de gewichten met een iteratief algoritme te berekenen. Als de hubgewichten van alle pagina's gegeven zijn, dan is het autoriteitgewicht van een pagina p ∈ Sz gelijk aan de som van de hubgewichten van alle pagina's q die naar p verwijzen, dus zodat (q, p) ∈ E(Gz ). Analoog, als de autoriteitgewichten van alle pagina's gegeven zijn, dan is het hubgewicht van een pagina p ∈ Sz gelijk aan de som van autoriteitgewichten van alle pagina's q waar p naar verwijst, dus zodat (p, q) ∈ E(Gz ). We beginnen nu het algoritme door alle pagina's in Gz autoriteit- en hubgewicht 1 te geven. Als 19
we bovengenoemde operaties achter elkaar blijven uitvoeren, dan zal blijken dat het resultaat convergeert. Het is tijd om het autoriteit- en hubgewicht van een pagina wiskundig te de niëren. Voordat we dit doen, introduceren we nog een belangrijke notatie. Voor elke verzameling pagina's P = {1, ..., n} zullen we de vectoren a(P ) en h(P ) berekenen. Deze vectoren hebben de eigenschap dat het autoriteitgewicht en hubgewicht van pagina i simpelweg de ide entries zijn van a(P ) en h(P ). We de niëren nu de vectoren a(P ) en h(P ) als de limiet van twee recursieve rijen van vectoren (ak (P ) | k ∈ N) en (hk (P ) | k ∈ N).
De nitie 20. Voor P = {1, ..., n} de niëren we a0 (P ) = h0 (P ) = J1,n . Laat nu ak (P ) en hk (P ) voor k ≥ 0 gede nieerd zijn. Dan de niëren we
h0 (P ) a0k+1 (P )
en hk+1 (P ) = k+1
ak+1 (P ) =
a0 (P )
h0 (P ) , k+1 k+1
waarbij a0k+1 (P ) = A(S)T hk (P ) en h0k+1 (P ) = A(S)a0k+1 (P ).
We zien in deze de nitie de heuristiek die we hierboven besproken hebben terug. Door A(S)T met hk (P ) te vermenigvuldigen, tellen we namelijk voor elk punt i precies de hubwaarden in stap k van alle punten j die naar i verwijzen op. Het getal we dan krijgen wordt (na normalisatie) het nieuwe autoriteitgewicht van punt i in stap k + 1. Idem dito, door A(S) met a0k+1 (P ) te vermenigvuldigen, tellen we voor elk punt i precies de autoriteitwaarden in stap k + 1 van alle punten j waarnaar i verwijst op, en zo krijgen we (na normalisatie) het nieuwe hubgewicht van punt i in stap k + 1.
Voorbeeld 4. We berekenen a2 (P ) en h2 (P ) van de onderstaande graaf H , met P = V (H) = {1, 2, 3, 4}.
Figuur 2.4: De gerichte graaf H .
20
Deze graaf heeft verbindingsmatrix
1 0 1 0
1 0 0 0
0 0 , 1 0
0 0 0 0
0 1 0 1
1 0 . 0 0
0 0 A(H) = 0 1
dus de getransponeerde matrix hiervan is 0 1 A(H)T = 1 0
Vervolgens berekenen we
0 1 a01 (P ) = 1 0
0 0 0 0
0 1 0 1
1 1 1 0 0 1 0 1
1 2 = en h01 (P ) = 1 1
0 0 0 1
1 0 1 0
1 0 0 0
0 1 2 0 1 1 0 1
3 0 = . 3 1
Door deze vectoren te delen door hun 2-norm, vinden we
1 0, 378 0, 756 1 2 ≈ a1 (P ) = √ 7 1 0, 378 1 0, 378
3 0, 688 0 0 1 en h1 (P ) = √ ≈ 0, 688 19 3 1 0, 229
.
Op dezelfde manier kunnen we a2 (P ) en h2 (P ) berekenen, en dan we vinden we
1 0, 135 0, 809 1 6 ≈ a2 (P ) = √ 55 3 0, 405 3 0, 405
9 0, 705 0 0 1 en h2 (P ) = √ ≈ 163 9 0, 705 1 0, 078
.
We zien na twee iteratiestappen dat punt 2 het hoogste autoriteitgewicht (0,809) krijgt toegekend. Dit zien we terug in de graaf doordat punt 1 en punt 3 (dat ook een redelijk autoriteitgewicht heeft) naar punt 2 wijzen. Punt 2 heeft op zijn beurt weer een laag hubgewicht (0), omdat het naar geen enkel ander punt verwijst. Omdat de punten 1 en 3 naar het autoriteiten punt 2 verwijzen, krijgen ze een hoog hubgewicht. Kleinberg heeft bewezen dat de rijtjes (ak (P ) | k ∈ N) en (hk (P ) | k ∈ N) onder bepaalde omstandigheden convergeren naar de dominante eigenvectoren van bepaalde matrices, en deze limieten blijken gelijk te zijn aan onze vectoren a(P ) en h(P ). 21
Stelling 6. Laat A = A(G) de verbindingsmatrix van G zijn, en kies p ∈ V (G). Veronderstel
dat AT A en AAT primitief zijn. Dan gelden de volgende eigenschappen. (1) De limiet a(P ) van de rij (ak (P ) | k ∈ N) is de genormaliseerde dominante eigenvector van AT A. (2) De limiet h(P ) van de rij (hk (P ) | k ∈ N) is de genormaliseerde dominante eigenvector van AAT . Voordat we deze stelling bewijzen, formuleren en bewijzen we het volgende lemma, waar we uitgaan van een diagonaliseerbare matrix.
Lemma 4. Laat M een niet-negatieve, primitieve, symmetrische (en dus diagonaliseerbare) matrix zijn, en laat v1 de dominante eigenvector van M zijn met kv1 k = 1. (Merk op dat v1 op teken na uniek is volgens de Stelling van Perron-Frobenius.) Laat verder z0 een willekeurige vector zijn die niet loodrecht op v1 staat. Voor gede nieerde zk , de niëren we zk+1 =
M zk . kM zk k
Dan lim zk = v1 .
k→∞
Bew¼s. Volgens Propositie 1 geldt, omdat M diagonaliseerbaar is, dat Cn een basis {v1 , ..., vn } heeft van de eigenvectoren van M . Hierbij is λi de eigenwaarde van vi , dus M vi = λi vi . Omdat v1 de dominante eigenvector van M is, geldt λ1 = |λ1 | > |λi |, voor alle 2 ≤ i ≤ n. Nu kunnen we z0 schrijven als een lineaire combinatie van basisvectoren z0 =
n X
ci v i ,
i=1
waarbij ci scalars zijn en c1 6= 0. Dit laatste is zo omdat 0 6= hv1 , z0 i = hv1 , P 2 n i=1 ci hv1 , vi i = c1 kv1 k = c1 . Merk op dat M k z0 zk = . kM k zk k
Nu kunnen we M k z0 als volgt herschrijven: k
M z0 = M
k
n X
ci vi
i=1
= =
n X i=1 n X
ci M k v i ci λki vi
i=1
= c1 λk1
k ! n X ci λ i vi . v1 + c λ 1 1 i=2
22
Pn
i=1 ci vi i
=
Omdat |λ1 | > |λi |, voor alle 2 ≤ i ≤ n, is λλ1i < 1. En omdat zk de genormaliseerde vector van M k z0 is, geldt M k z0 k→∞ kM k z0 k P k c1 λ1 v1 + ni=2
= lim
P k→∞ k c1 λ1 v1 + ni=2
lim zk =
k→∞
lim
ci c1 ci c1
k λi vi λ1 k
λi vi λ1
v1 kv1 k = v1 .
=
Nu kunnen we met behulp van dit lemma Stelling 6 bewijzen.
Bewijs van Stelling 6. De matrices AT A en AAT zijn reëel en symmetrisch, en zijn dus ook diagonaliseerbaar. Uit De nitie 20 volgt dat we ak (P ) kunnen schrijven als (AT A)k−1 AT J1,n k(AT A)k−1 AT J1,n k
en dat hk (P ) gelijk is aan
(AAT )k J1,n . k(AAT )k J1,n k
We bewijzen alleen bewering (1) van de stelling, omdat het bewijs van (2) analoog verloopt. Als M = AT A positief is, dan is er volgens de Stelling van Perron-Frobenius een dominante eigenvector v1 van AT A zodanig dat kv1 k = 1. Er bestaat een tweede versie van de Stelling van Perron-Frobenius die hetzelfde resultaat garandeert voor het geval dat M niet-negatief is. In dit geval is v1 ook niet-negatief. Voor meer details hierover verwijzen we de lezer door naar [13]. De nieer z0 = AT J1,n . Omdat z0 niet-negatief is met hier en daar positieve entries, en omdat v1 niet de nulvector is, geldt dat v1 en z0 niet orthogonaal zijn. Volgens Lemma 4 geldt nu (AT A)k−1 (AT J1,n ) k→∞ k(AT A)k−1 (AT J1,n )k M k−1 z0 = lim k→∞ kM k−1 z0 k = v1 .
lim ak (P ) =
k→∞
lim
Dus de limiet a(P ) van de rij (ak (P ) | k ∈ N) is de genormaliseerde dominante eigenvector v1 van AT A. 23
Om de limieten a(P ) en h(P ) van onze rijtjes te weten te komen, kunnen we dus de genormaliseerde dominante eigenvectoren van AT A en AAT berekenen. Dit zijn twee onafhankelijke berekeningen, terwijl er een methode is waarmee we deze eigenvectoren in één keer kunnen berekenen. Deze methode is de singuliere waarden decompositie, die we in Sectie 1.2.1 geïntroduceerd hebben. Als A = U ΣV T , dan zijn volgens Propositie 2 de kolommen van U gelijk aan de eigenvectoren van AAT , en de kolommen van V aan de eigenvectoren van AT A.
Voorbeeld 5. We beschouwen nogmaals de gerichte graaf uit guur 2.4. We gebruiken de singuliere waarden decompositie om a(P ) en h(P ) te berekenen. Volgens Stelling 2 kunnen we schrijven A = U ΣV T . De matrices die hieraan voldoen, zijn √ √ − 12 2 0 − 21 2 0 0 0 0 −1 , √ √ U = 1 1 − 2 0 2 0 2 2 0 −1 0 0
√
3 0 Σ= 0 0
0 1 0 0
0 0 1 0
0 0 , 0 0
0√ −1 0 0√ −1 6 0 0√ − 13√ 3 3√ V = −1 6 0 −1 2 1 3 . 6√ 2√ 3√ 1 1 2 3 − 16 6 0 2 3
De eerste kolommen van U en V geven ons de genormaliseerde dominante eigenvectoren van AAT en AT A: 1 √ 0
2
0 h(P ) = √1
en
2
0
a(P ) =
√2 6 √1 6 √1 6
.
Het autoriteit- of hubgewicht van een punt i kunnen we nu a ezen als de ide entry van a(P ) of h(P ). We zien dat de vectoren a2 (P ) en h2 (P ) uit Voorbeeld 4 aardig overeenkomen met de werkelijke a(P ) en h(P ). De convergentie van (ak (P ) | k ∈ N) en (hk (P ) | k ∈ N) lijkt dus vrij snel te gaan, en volgens Kleinberg zijn 20 iteratieve stappen voldoende om een goede gewichtstoekenning te waarborgen. 2.3
SALSA
In 2001 publiceerden Ronny Lempel en Shlomo Moran een artikel [4] waarin ze een nieuw zoekalgoritme SALSA beschrijven. Stochastic Approach for Link Structure Analysis (SALSA) combineert eigenschappen van PageRank en van HITS. 24
Zo gaat SALSA bij een bepaalde zoekopdracht z allereerst uit van een geïnduceerde deelgraaf Gz van W , die op een analoge manier als in HITS wordt gekozen. Vervolgens bekijken we een random walk op Gz , die de autoriteiten bij z net als in PageRank met hoge kans zal bezoeken. We kijken wederom naar zowel autoriteiten en hubs, en voor elk van de twee bekijken we een aparte Markovketen. De transitiematrices hiervan zullen we niet zoals gewoonlijk vinden, maar door het doorlopen van twee links achter elkaar als één transitie te zien. Door beide ketens de analyseren zullen we voor elke pagina een autoriteit- en een hubgewicht vinden. In deze sectie zien we waarom en hoe Lempel en Moran de webstructuur van W op deze manier gebruikten om het belang van een pagina te berekenen. 2.3.1
Random walks over een bipartiete graaf
De eerste stap van SALSA is het construeren van een basisgraaf Gz die relatief klein is, die veel relevante pagina's bevat en die de meeste autoriteiten bevat. Dit gebeurt op dezelfde manier als bij HITS, zie Sectie 2.2.1. Aan de hand van Gz de niëren we nu een bipartiete ongerichte graaf B = (Va ∪ Vh , E) als volgt: Va = {ga | g ∈ Gz en deg− (g) > 0} Vh = {gh | g ∈ Gz en deg+ (g) > 0} E = {(gh , g¯a ) | (g, g¯) ∈ E(Gz )}.
We noemen Va de verzameling van autoriteitspunten en Vh de verzameling van hubpunten. Via deze de nitie wordt elke niet-geïsoleerde pagina g in Gz gerepresenteerd in B door ofwel ga , ofwel gh , of beide. Elke gerichte lijn van g naar g¯ in E(Gz ) wordt gerepresenteerd door een ongerichte lijn tussen gh en g¯a in B . Dit geeft ook een heuristische verklaring van de termen autoriteit en hub (die in Sectie 2.2 zijn geïntroduceerd). In guur 2.4 zien we hoe B uit een gegeven graaf Gz wordt gemaakt. We gaan nu op onze bipartiete graaf B twee random walks maken. Hierbij zien we het doorlopen van twee lijnen in B als één stap in de random walk. Omdat B bipartiet is, betekent dit dat de punten waarin een random walk terechtkomt allemaal aan één zijde van B zitten. Als we de twee random walks aan verschillende kanten laten beginnen, hebben we dus enerzijds een random walk over Va en anderzijds een random walk over Vh . Een mooie eigenschap van B is dat de belangrijkste autoriteiten en hubs bij een zoekopdracht goed zichtbaar zullen zijn, doordat ze door veel andere punten direct of via een kort pad bereikt kunnen worden. We mogen dan ook wel verwachten dat autoriteiten vaak bezocht worden bij de random walk over Va en dat hubs vaak bezocht worden bij de random walk over Vh . We zullen deze random walks nu zien als Markovketens door de bijbehorende transitiematrices op te stellen (zie ook Propositie 3). Deze Markovketens noemen we de autoriteitketen (de keten over Va ) met bijbehorende autoriteitmatrix A¯, en de hubketen (de keten over Vh ) met ¯. bijbehorende hubmatrix H 25
Figuur 2.5: De constructie van (b) de bipartiete graaf B uit (a) de gerichte graaf Gz .
De nitie 21. We de niëren A¯ door: a ¯i,j =
X {k|(kh ,ia ),(kh ,ja )∈B}
1 1 · , deg(ia ) deg(kh )
(2.4)
¯ door: en we de niëren H ¯ i,j = h
X {k|(ih ,ka ),(jh ,ka )∈B}
1 1 · . deg(ih ) deg(ka )
Dit is een goede de nitie, want a¯i,j is simpelweg de sommatie over alle mogelijke hubs kh (via welke je van ia naar ja kunt) van de kansen dat je vanuit ia via kh in ja terechtkomt. Op ¯ i,j de sommatie over alle mogelijke autoriteiten ka (via welke je van ih dezelfde manier is h naar jh kunt) van de kansen dat je vanuit ih via ka in ja terechtkomt. En omdat we met een random walk te maken hebben, gaan we met gelijke kans van een punt ga naar een willekeurig ander punt g¯h dat in B met ga verbonden is, en vice versa.
Voorbeeld 6. We bekijken de bipartiete graaf B uit guur 2.4. De bijbehorende autoriteit-
matrix en hubmatrix zijn:
← 2a ← 1h 1 0 0 0 1 0 0 0 0 1 1 1 ← 3a 0 1 1 1 ← 2h 2 4 4 2 4 4 ¯ A¯ = 0 1 1 1 ← 4a en H = 0 1 1 1 ← 4h . 4 2 4 4 2 4 0 14 14 12 ← 6a 0 14 41 12 ← 5h
¯ gelijk aan elkaar. Merk verder op dat je een lijn ook Omdat B symmetrisch is, zijn A¯ en H twee keer achter elkaar mag doorlopen in de random walks. Vanuit 1h ga je bijvoorbeeld
26
met kans 1 naar 2a , en vervolgens ga je met kans 1 over dezelfde lijn weer terug naar 1h . ¯ 1,1 = 1. Op dezelfde manier kun je vanuit 4a met kans 1 naar 2h en Dit impliceert dat h 2 met kans 12 over dezelfde lijn weer terug naar 4a , wat is zijn geheel dus gebeurt met kans 1 1 · = 14 . Maar je kunt ook via 5h op en neer naar 4a , ook met kans 14 . Dit betekent dat 2 2 a ¯4,4 = 14 + 14 = 12 .
Opmerking 1. Een positieve transitiekans a¯i,j > 0 betekent dat er een pagina k is, die in Gz zowel naar i als naar j verwijst. Op die manier is j in Gz vanuit i in twee stappen te bereiken, namelijk door eerst de link k → i in omgekeerde richting te volgen, en vervolgens de link k → j te volgen. ¯ nog op een alternatieve manier karakteriseren. Deze manier We kunnen de matrices A¯ en H zal ons later toestaan om op dezelfde manier als bij PageRank en HITS te bewijzen dat de autoriteit- en hubketen convergeren naar een evenwichtsverdeling. Laat A = A(Gz ) de verbindingsmatrix van de oorspronkelijke gerichte graaf Gz zijn. Laat Ar de matrix zijn die we krijgen als we elk niet-nulelement (i, j) ∈ A delen door de rijsom ri , en laat Ak de matrix zijn die we krijgen als we elk niet-nulelement (i, j) ∈ A delen door de kolomsom kj . Merk op dat de sommen van rijen of kolommen die niet-nulelementen bevatten groter dan 0 zijn. Nu geldt de volgende stelling.
Stelling 7. A¯ bestaat uit de niet-nulrijen en -kolommen van ATk Ar en H¯ bestaat uit de
niet-nulrijen en -kolommen van Ar ATk .
Bew¼s. We bewijzen de bewering voor A¯; het bewijs voor de tweede bewering verloopt analoog. Per constructie is Ar een stochastische matrix die een random walk op Gz modelleert, en is ˜ z uit Gz is ATk een stochastische matrix die een random walk op G˜z modelleert, waarbij G afgeleid door de richting van elke lijn om te draaien. Dus entry (i, j) van het product ATk Ar is een sommatie over alle mogelijke manieren waarop we in Gz van i naar j kunnen door eerst een lijn in tegengestelde richting te volgen en vervolgens een lijn in Gz te volgen. Hierbij wordt per pad de kans geteld dat we dát pad van i naar j nemen. Nu volgt uit opmerking 1 dat A¯ precies bestaat uit de niet-nulrijen en -kolommen van ATk Ar . ¯ daadwerkelijk transitiematrices van twee MarkovWe moeten alleen nog bewijzen dat A¯ en H ketens zijn. Met bovenstaande karakterising is dit eenvoudig na te gaan.
Propositie 3. De autoriteitmatrix A¯ en de hubmatrix H¯ zijn stochastische matrices. Bew¼s. Per constructie tellen de rijen van Ar en ATk op tot 1, en zijn dus stochastische matrices. Maar dan zijn de producten ATk Ar en Ar ATk ook stochastisch. Met Stelling 7 volgt nu het gestelde. Lempel en Moran hebben onderstaande stelling op een zelfde manier bewezen als PageRank en HITS [4]. 27
Figuur 2.6: De samenhangende graaf G.
Stelling 8. Laat de bipartiete graaf B samenhangend zijn. Dan zijn A¯ en H¯ stochastische
en primitieve matrices. In het bijzonder convergeren de autoriteit- en hubketen naar even¯ zijn. wichtsverdelingen, die de k · k1 -genormaliseerde dominante eigenvectoren van A¯ en H We sluiten deze sectie af met een voorbeeld.
Voorbeeld 7. We berekenen de autoriteitgewichten van de graaf in guur 2.6. Hiervoor gebruiken we de karakterisering uit Stelling 7. We zien dat 1 1 1 5
1 5
1 5
0 0 1 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1 0 15 0 0 5 0 12 0 0 0 1 1 1 0 0 3 3 3 1 0 0 21 0 2 1 0 0 0 31 3 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 0 0
Ar = 1 3 0 0
en
T Ak =
5
0 1 2
0 0 0 0 1 3 1 3 1 2
0 1 2
0 0 0 0 0 0 0 1 2
5 1 2 1 2
0 0 0 0 0 0 0
28
1 3
0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 3 0 0
0 0 0 0 0 0 0 0 1 3
0 0 0 0
1 5
0 0 0 1 0 3 0 21 0 0 0 1 0 0 0 0 0 1
,
0
1 0 0 1 5
1 5 1 2
0 0 0 0 0 0 0
.
Na vermenigvuldiging en het wissen van nulrijen en -kolommen, vinden we ¯ A=
1 3 1 15
0 0 0 0 1 6
0 0
1 3 28 75 1 4 7 30 1 10 1 15 4 15 1 3 1 3
0
0
0
0
1 10 1 2 1 6
14 100 1 4 2 5 1 10 1 15 1 10
1 25
1 25
1 3 8 75
0
0
0
1 15 3 5 1 15 1 10
1 15 1 10 11 15 1 10
1 15 1 10 1 15 4 15
0 0
0 0
0 0
0 0
0 0 0 0 0
0
0
1 15
1 15
0 0 0 0 0
0 0 0 0 0
1 3 1 3
1 3 1 3
.
We zien dat A¯ slechts negen rijen en kolommen heeft. Dit komt doordat punt 9 in de graaf geen inkomende lijnen heeft en daarom van SALSA geen autoriteitwaarde krijgt toegekend. Nu gebruiken we een andere versie van de machtsmethode (namelijk voor niet-symmetrische matrices, zie [14]) om de autoriteitwaarden van de overige punten te benaderen. We kiezen hierbij als startvector z0 = 19 19 91 19 91 91 91 19 19 . Na een iteratie van 26 stappen vinden we de volgende evenwichtsverdeling in twee decimalen nauwkeurig: s=
0, 05 0, 25 0, 10 0, 15 0, 10 0, 15 0, 10 0, 05 0, 05
.
We zien dat, in tegenstelling tot de PageRankvector 2.3, punt 2 hier wel de hoogste waarde krijgt. Verder komen de getallen globaal redelijk overeen. Achter PageRank lijkt echter iets meer diepgang en reële menselijkheid te zitten, wat misschien het enorme succes van Google een beetje kan verklaren.
29
Hoofdstuk 3 Virussen op het web Er is overtuigend bewijs dat de graadverdeling van de punten in de webgraaf volgens een machtswet gaat [6]. Een graaf waarvan de graadverdeling van de punten een machtswet volgt, noemen we in dit hoofdstuk een scale-free graaf. Het houdt in dat er veel punten met een kleine graad zijn, en voor grotere graden worden dit er exponentieel minder. Maar wat voor impact heeft deze structuur op processen op het web? In dit hoofdstuk bekijken we aan de hand van [7] een proces dat de verspreiding van virussen op het web modelleert, en hoe dit proces wordt beïnvloed door het feit dat de webgraaf scale-free is. 3.1
Introductie
Het standaardmodel voor de bestudering van virusinfecties op het web is het contactproces, ook wel het SIS-model 1 genoemd. Dit model gaat uit van de webgraaf zoals we die kennen, en een virus kan zich verspreiden door de pijlen in de graaf te volgen. Elk punt van de webgraaf is ófwel gezond (maar wel vatbaar voor een virus), ófwel geïnfecteerd door een virus. Met rate 1 (dat wil zeggen: na een exponentieel verdeelde tijd met parameter 1) wordt een geïnfecteerd punt weer gezond, onafhankelijk van de toestand van zijn buren. Een gezond punt wordt geïnfecteerd met rate λ > 0, vermenigvuldigd met het aantal geïnfecteerde buren, waarbij λ de zogenaamde voortplantingsverhouding is. Hoe meer geïnfecteerde buren een punt heeft, des te groter is dus de kans op infectie van het punt zelf.
De nitie 22. We noemen de aanwezigheid van een virus in het web, vanaf het tijdstip waarop het verschijnt tot de verdwijning van het virus, een infectie.
De nitie 23. We noemen een infectie een epidemie als de tijd, die het virus nodig heeft om uit te sterven, exponentieel is in het aantal punten.
Als we het contactproces bekijken op een random graaf, waarin elk punt met gelijke kans een bepaalde graad heeft, dan is het belangrijkste resultaat dat er waarschijnlijk een niet-nul 1 SIS
is een afkorting voor susceptible-infected-susceptible, wat vatbaar-geïnfecteerd-vatbaar betekent.
30
epidemiedrempel λc bestaat. Als de voortplantingsverhouding groter is dan deze drempel, λ ≥ λc , dan zal het virus zich uitbreiden zonder te verdwijnen. Maar als λ < λc , dan zal het virus exponentieel snel uitsterven. Het is echter niet duidelijk of de webgraaf inderdaad kunnen beschouwen als een random gegenereerde graaf. We zullen zien dat vanwege de machtswet, waaraan de graadverdeling van de webgraaf voldoet, we inderdaad bovenstaande eigenschap niet kunnen toepassen op de webgraaf. De epidemiedrempel λc zal namelijk gelijk aan 0 blijken te zijn. Omdat λ positief is, betekent dit dat zelfs virussen met een zeer kleine voortplantingsverhouding een positieve kans hebben om een epidemie te veroorzaken. Verder zullen we zien dat het ontstaan van een epidemie ook erg afhangt van het punt waarop het virus begint. De epidemiekans voor een virus dat op een speciaal punt begint, is gelijk aan λ
Θ
log(λ−1 ) log log(λ−1 )
,
(3.1)
terwijl de epidemiekans beginnend bij een willekeurig punt gelijk aan λΘ(1) is. De Θ-notatie hebben we gede nieerd is De nitie 4. In de rest van dit hoofdstuk zullen we 3.1 verder uitwerken (zie Stelling 9) en gedeeltes van het bewijs ervan behandelen. Het bewijs maakt gebruik van de Barabási-Albert-graaf, die we in Sectie 3.2 de niëren. Verder is het bewijs gebaseerd op eigenschappen van het contactproces en de machtswet, zoals we in Sectie 3.3 zullen zien. Allereerst geven we een intuïtieve omschrijving van het bewijs van 3.1. Het gedrag van het contactproces is in grote mate afhankelijk van de graadverdeling van de graaf. Als bijvoorbeeld alle graden in een graaf signi cant kleiner zijn dan λ−1 , dan zal het virus zeer snel verdwijnen. Maar als het virus een punt bereikt met een signi cant grotere graad dan λ−2 , dan is er een grote kans dat het virus lang zal voortleven in de buurt van dat punt. We willen dus graag een beter zicht hebben op de graadverdeling in de buurt van een bepaald punt. We zullen zien dat, voor bepaalde punten v , de grootste graad in een bal met straal Θ(1) k rond v zeer waarschijnlijk (k!) is. Op deze manier is het meest nabije punt van graad −1 ) log(λ λ−Θ(1) op een afstand van Θ log log(λ−1 ) . We willen nu dus de kans weten dat het virus daadwerkelijk aankomt bij een punt met graad λ−Θ(1) , en dit is precies de kans gegeven in 3.1. 3.2
Barabási-Albert-model en Pólya-urn-model
Een eigenschap van scale-free grafen is dat deze gegenereerd kunnen worden door bepaalde random-graafmodellen. In deze sectie introduceren we het model dat we gebruiken om de webgraaf te modelleren, zodat we op basis van dat model de gewenste eigenschappen kunnen a eiden. Dit model is in 1999 door Barabási en Albert [8] geïntroduceerd, en het de nieert de zogenaamde Barabási-Albert-graaf. 31
Laat m ≥ 2 een geheel getal zijn, en laat 0 ≤ α ≤ 1 een reëel getal zijn. Laat verder {vi } een reeks punten zijn, en laat Gi de Barabási-Albert-graaf op tijdstip i zijn. Dan is G1 de graaf bestaande uit alleen het punt v1 en geen lijnen, en is G2 de graaf bestaande uit de punten v1 en v2 , met m lijnen tussen deze punten. Voor een gegeven graaf Gn−1 , construeren we Gn als volgt. Voeg het punt vn toe aan de graaf, en kies m punten w1 , ..., wm inductief op onderstaande manier, mogelijk met herhaalde punten, uit Gn−1 . Vervolgens trekken we lijnen tussen vn en elke wj , 1 ≤ j ≤ m. Herhaalde punten in de rij w1 , ..., wm resulteren dan in meervoudige lijnen in Gn . De punten w1 , ..., wm worden op de volgende manier inductief gekozen. Met kans α kiezen we w1 = vi met kans 1/(n − 1) voor elke i = 1, ..., n − 1, en met kans 1 − α kiezen we w1 = vi , voor elke i = 1, ..., n − 1, met kans degn−1 (vi )/Z , waarbij Z zorgt voor normalisatie: Z =
n−1 X
degn−1 (vi )
i=1
= 2m(n − 2).
We vervolgen dit proces inductief door telkens dezelfde regel toe te passen, maar als we wk bepalen, dan gebruiken we niet degn−1 (vi ), maar 0
degn−1 (vi ) = degn−1 (vi ) + #{1 ≤ j ≤ k − 1 | wj = vi }.
Met kans 1 − α kiezen we dus een punt uit Gn−1 zódanig, dat de punten met de grootste graad in Gn−1 de grootste kans hebben om gekozen te worden. De Barabási-Albert-graaf G van grootte n de niëren we nu als Gn , de Barabási-Albert-graaf op tijdstip n. Opmerking 2. Volgens [7] is het niet erg dat we in de Barabási-Albert-graaf meervoudige lijnen toestaan. Ze hebben een meer natuurlijke variant, zonder meervoudige lijnen, ook bestudeerd, en dit blijkt het uiteindelijke resultaat niet te beïnvloeden.
Voorbeeld 8. We bekijken de in guur 3.1 gegeven Barabási-Albert-graaf G3 . In dit voor-
beeld construeren we een G4 uit een gegeven graaf G3 . Hierbij nemen we m = 3 en α = 0, 5.
We voegen nu een nieuw punt toe, en vanuit dat punt trekken we m = 3 lijnen naar de andere punten. De eerste lijn wordt op de volgende manier bepaald: - óf met kans 0,5 kiezen we willekeurig een punt uit G3 en verbinden de lijn hiermee; - óf met kans 0,5 kiezen we met kans en verbinden de lijn hiermee.
4 12
punt 1, met kans
5 12
punt 2 en met kans
3 12
punt 3
De volgende twee lijnen worden op ongeveer dezelfde manier gekozen. In guur 3.2 zien we een mogelijk resultaat. De uitwerking van 3.1, en dus de belangrijkste resultaten van dit hoofdstuk, geven we nu in de volgende twee stellingen. 32
Figuur 3.1: Een Barabási-Albert-graaf G3 , met m = 3 en α = 0, 5.
Figuur 3.2: Een Barabási-Albert-graaf G4 , met m = 3 en α = 0, 5.
Stelling 9. Voor elke λ > 0 bestaat er een N zodanig dat voor elke Barabási-Albert-graaf van
grootte n > N geldt: als we een willekeurig punt v kiezen, dan heeft v met kans 1 − O(λ2 ) de eigenschap dat de overlevingskans p van een infectie die in v begint als volgt wordt begrensd: λ
C1
log(λ−1 ) log log(λ−1 )
C2
≤p≤λ
log(λ−1 ) log log(λ−1 )
,
waarbij C1 en C2 constanten zijn, C1 ≥ C2 , onafhankelijk van λ en n.
Stelling 10. Voor elke λ > 0 bestaat er een N zodanig dat voor elke Barabási-Albert-graaf van grootte n > N geldt: als we een willekeurig punt v kiezen en de infectie in v laten beginnen, dan wordt de overlevingskans p van de infectie als volgt begrensd: λC3 ≤ p ≤ λC4 ,
waarbij C3 en C4 constanten zijn, C3 ≥ C4 , onafhankelijk van λ en n. Voor de bewijzen van bovenstaande stellingen zijn veel technische lemma's en specialistische details nodig, die we in deze scriptie niet allemaal kunnen behandelen. We zullen in de rest van dit hoofdstuk wel enkele interessante gedeeltes tentoonstellen aan de lezer. Voor de volledige versie verwijzen we de lezer graag door naar [7]. Het Barabási-Albert-model is lastig om mee te rekenen, en daarom wordt in [7] nog een ander model geïntroduceerd, het zogenaamde Pólya-urn-model, zie ook [11]. Gegeven is een aantal 33
urnen, met in elke urn een aantal ballen, en in elke stap wordt er een nieuwe bal toegevoegd aan één van de urnen. De kans dat de bal in i wordt gelegd is proportioneel aan Ni + u, waarbij Ni het aantal ballen in urn i is, en u een van tevoren bepaalde parameter van het model is. Pólya bewees dat dit model equivalent is aan het volgende wiskundige proces. We kiezen voor elke i een parameter pi (genaamd de aantrekkingskracht ), en in elke stap leggen we een nieuwe bal in urn i met kans pi , onafhankelijk van alle voorgaande stappen. Pólya speci ceerde een verdeling van u en het aantal ballen in elke urn in stap 0 zodat dit proces het urnmodel simuleert.
Voorbeeld 9. Beschouw twee urnen, elk beginnend met 1 bal en met u = 0. Dan is p1 een uniforme [0, 1] variabele, en p2 = 1 − p1 .
Pólya liet zien dat voor willekeurige waarden van u en {Ni (0)}, de waarden van {pi } bepaald worden door de β -verdeling met geschikte parameters. We kunnen het Pólya-urn-model op de volgende manier vergelijken met het Barabási-Albertmodel. Elke nieuwe verbinding die een punt vi in het Barabási-Albert-model maakt kunnen we in het Pólya-urn-model representeren met een bal die in urn i wordt gelegd. We kunnen nu dus ook een equivalente beschrijving van de Barabási-Albert-graaf maken. Dit zullen we echter niet expliciet behandelen in deze scriptie, en voor alle technische details hiervan verwijzen we de lezer door naar [7]. Het Pólya-urn-model kan gebruikt worden om scale-free grafen te genereren waarop we het contactproces (dat we in de volgende sectie wiskundig zullen de niëren) kunnen toepassen. Omdat het internet ook een scale-free graaf is, kunnen we op deze manier conclusies trekken over de manier waarop een virus zich over het internet verspreidt. 3.3
Het contactproces
In deze sectie zullen we een deel van de bewijzen van bovenstaande stellingen behandelen. Hiertoe geven we eerst een wiskundige de nitie van het eerdergenoemde contactproces. In dit model is een punt in de webgraaf ofwel gezond ofwel geïnfecteerd. Een geïnfecteerd punt wordt gezond na een exponentiële tijd met rate 1, onafhankelijk van de toestand van de buurpunten. Een gezond punt wordt geïnfecteerd met een rate die proportioneel is met het aantal geïnfecteerde buurpunten. De volgende de nitie geeft dit idee wiskundig weer.
De nitie 24. Het contactproces met parameter λ > 0 op een graaf G = (V, E) is een
(continue-tijds) Markovproces (Xt | t ∈ [0, ∞)) dat op tijdstip t wordt geïdenti ceerd met de deelverzameling punten A = {v ∈ V | Xt (v) = 1}. De punten in A noemen we geïnfecteerd en de punten in V \A noemen we gezond. De transitierates voor Xt worden gegeven door A → A\{v}, voor v ∈ Amet rate 1 A → A ∪ {v}, voor v ∈ / A met rate λ · #{u ∈ A | (u, v) ∈ E}.
34
We nemen aan dat op t = 0 één van de punten in G geïnfecteerd is. Dit punt noemen we de wortel. Merk op: hoe groter de waarde van λ, des te meer punten zullen er geïnfecteerd worden. Een deel van het bewijs van Stelling 9 bestaat uit het bewijzen van de volgende bewering: in een scale-free graaf van grootte n bestaat er een λn zodanig dat elk contactproces met parameter λ > λn een grote kans heeft om een epidemie te veroorzaken. Verder geldt dat λn → 0 als n → ∞. Een epidemie hebben we gede nieerd in De nitie 23.
Lemma 5. Laat G = (V, E) een graaf zijn met hoogste graad d. Laat S ⊆ V de verzameling punten zijn die ooit geinfecteerd worden in G. Dan geldt voor elke k P (|S| > k) < (2dλ)k .
Bew¼s. We mogen zonder verlies van algemeenheid aannemen dat λd < 1. De nieer Y als de grootheid die |A| op elk tijdstip aangeeft. De kans dat twee gebeurtenissen (een gezond punt wordt geinfecteerd of andersom) tegelijkertijd plaatsvinden is 0. Daarom worden de transitierates voor Y gegeven door Y Y
→ Y − 1 met rate Y → Y + 1 met rate λ · |c(A)|,
waarbij c(A) = {(u, v) ∈ E | u ∈ A, v ∈ V \A}. Er geldt dat |c(A)| ≤ Xd. Daarom geldt voor een volgend tijdstip dat Y overgaat naar Y + 1 met kans hoogstens λd 1 λY d = < λd, Y + λY d 1 + λd 2
omdat λd < 1. Er geldt ook dat Y overgaat naar Y − 1 met kans minstens 1 1 > 1 − λd. 1 + λd 2
Om de toestand Y = k + 1 te bereiken, moet Y minstens k keer overgaan naar Y + 1 in de eerste 2k stappen. De kans hierop wordt van boven begrensd door 2k
2
λd 2
k
= (2dλ)k .
Dit bewijst het lemma. De volgende stelling is het gevolg van bovenstaand bewijs.
35
Stelling 11. Laat G = (V, E) een graaf zijn, laat v ∈ V (G) zijn en laat l een positief geheel
getal zijn. Veronderstel dat in een bal van straal l rondom v alle graden begrensd worden door d. Begin nu een contactproces met parameter λ < 1/(2d) in {v}. Voor t > 0 de niëren we S(t) als de gebeurtenis dat AT 6= ∅. Laat B(l) de gebeurtenis zijn dat de infectie de bal van straal l rond v nooit verlaat. Dan geldt voor elke t dat P (S(t) | B(l)) < (2λd)t .
Een ander, cruciaal lemma voor het bewijs van Stelling 9 bestudeert de overlevingstijd van een contactproces in een stervormige graaf. Dit is een graaf met een middelpunt x dat verbonden is met alle blaadjes y1 , ...yk . Het lemma stelt dat de infectie met grote kans in een stervormige graaf zal overleven voor een tijd die exponentieel is in het aantal punten. Het idee van het bewijs van dit lemma is als volgt: als het middelpunt van de graaf wordt geïnfecteerd, dan begint dit punt de blaadjes met zeer hoge rate te infecteren. Het aantal geïnfecteerde blaadjes voordat het middelpunt weer gezond wordt, is hoog genoeg om er zeker van te zijn dat de infectie zal overleven totdat het middelpunt weer wordt geïnfecteerd. Dus hoe meer punten de graaf heeft, des te langer zal de infectie blijven voortduren.
36
Hoofdstuk 4 Populaire samenvatting Internetwiskunde is een relatief nieuw vakgebied binnen de wiskunde dat gaat over alle wiskunde die achter het internet schuilgaat. Hierbij wordt het web gra sch weergegeven door webpagina's te zien als punten en hyperlinks tussen pagina's als pijlen tussen de punten. Er ontstaat zo een graaf van punten en pijlen, en die noemen we de webgraaf. Zoekmachines
Het internet bevat heel veel informatie, en we willen natuurlijk zo snel mogelijk toegang tot de informatie waarnaar we op zoek zijn. Zoekmachines spelen hierin een cruciale rol, want zij geven bij een zoekopdracht een lijst met webpagina's, op a opende relevantie of belangrijkheid. Maar hoe wordt bepaald of een zekere pagina belangrijker is dan een andere pagina? U raadt het al, dit wordt gedaan door allerlei wiskundige algoritmes.
PageRank De bekendste zoekmachine is zonder twijfel Google, en werd in 1998 uitgevonden door Larry Page en Sergey Brin. Achter het succes van Google gaat het wiskundige algoritme PageRank schuil. Aan elke webpagina wordt een getal toegekend, de zogenaamde PageRank van die pagina, en dit getal geeft aan hoe belangrijk die pagina is. De PageRank van een pagina geeft de kans weer dat een bezoeker op een willekeurig moment op die pagina is. Het rechtstreeks berekenen van deze getallen is een onmogelijk karwei (het aantal nodige berekeningen is gelijk aan het aantal webbladzijden, zeg twintig miljard, tot de derde macht), en daarom gebruiken Page en Brin een iteratief proces om alle PageRankgetallen binnen drie dagen vrij nauwkeurig te benaderen. Een pagina krijgt een hoge PageRank als er veel andere bladzijdes zijn die naar die pagina verwijzen. Verder spelen de PageRanks van die andere bladzijdes ook een rol: als veel onbelangrijke bladzijdes naar een pagina verwijzen, dan zal die pagina een lagere PageRank krijgen dan als er weinig belangrijke bladzijdes naar die pagina verwijzen. Het laatste criterium is dat het veel waard als een pagina alleen naar jou verwijst, en niet naar nog andere pagina's. 37
Figuur 4.1: De relatieve PageRanks van een miniwebgraaf. In guur 4.1 zien we een miniwebgraaf van elf bladzijdes met de bijbehorende PageRanks van die bladzijdes. We zien dat de kleine paarse pagina's een zeer lage PageRank hebben, omdat er geen enkele pagina hiernaar verwijst. Al deze pagina's verwijzen evenals pagina F naar pagina E , waardoor die een betere PageRank krijgt. Pagina B krijgt de hoogste PageRank omdat er veel pagina's naar verwijzen, en omdat ook de belangrijke pagina C enkel en alleen naar B verwijst. Omdat B ook alleen naar C verwijst, heeft C ook een hoge Pagerank. De bepaling van de PageRankgetallen lijkt een cirkelredenering te zijn, maar in mijn scriptie heb ik laten zien dat een eenvoudige iteratie geen problemen oplevert.
HITS Google berekent maandelijks voor elke pagina opnieuw de PageRank, en dit kost zoals gezegd nogal wat computerwerk. Het algoritme Hyperlink-Induced Topic Search (HITS) is in 1998 door Jon Kleinberg bedacht, en pakt dit anders aan. Het bepaalt namelijk per zoekopdracht een verzameling pagina's die relevant zijn bij de zoekopdracht en voor elke pagina in die verzameling berekent het vervolgens het belang van een pagina. Deze selectie van pagina's gebeurt in twee stappen; allereerst worden er 200 pagina's genomen waarop de zoekopdracht letterlijk voorkomt. Vervolgens wordt deze zogenaamde wortelverzameling uitgebreid tot een basisverzameling door alle pagina's die verwijzen naar de wortelverzameling en pagina's waarnaar de wortelverzameling verwijst toe te voegen, zie guur 4.2. De volgende stap van het HITS-algoritme bestaat uit het bepalen van het autoriteitgewicht en het hubgewicht van elke pagina uit de basisverzameling. Als een pagina belangrijk en relevant voor de zoekopdracht is, dan krijgt deze een hoog autoriteitgewicht. Als een pagina naar veel goede autoriteiten verwijst, dan krijgt de pagina een hoog hubgewicht. De berekening van deze gewichten lijkt weer in een cirkelredenering te stranden, maar Kleinberg heeft het als 38
Figuur 4.2: Uitbreiding van een wortelverzameling tot een basisverzameling. volgt opgelost. Als de hubgewichten van alle pagina's bekend zijn, dan is het autoriteitgewicht van een pagina p gelijk aan de som van de hubgewichten van alle pagina's die naar p verwijzen. Andersom, als de autoriteitgewichten van alle pagina's bekend zijn, dan is het hubgewicht van een pagina p gelijk aan de som van de autoriteitgewichten waar p naar verwijst. We beginnen nu het algoritme door alle pagina's autoriteit- en hubgewicht 1 te geven. Vervolgens passen bovengenoemde operaties twintig keer uit, en het belang van een pagina wordt dan bepaald door het autoriteitgewicht ervan.
SALSA Stochastic Approach for Link Structure Analysis (SALSA) is een algoritme dat in 2001 door Ronny Lempel en Shlomo Moran werd bedacht. SALSA creëert eerst een basisverzameling en berekent vervolgens de kans dat een bezoeker op een willekeurig moment op een bepaalde pagina is, dus SALSA combineert eigenschappen van PageRank en HITS. Virussen op het web
Men heeft regelmatig last van virussen die het internet teisteren. Om deze virussen te bestrijden, is het natuurlijk belangrijk om te weten hoe de virussen zich verspreiden over het internet. Het standaardmodel voor de bestudering hiervan is het contactproces. Dit proces gaat ervan uit dat virussen zich tussen pagina's verspreiden door pijlen in de webgraaf te volgen. Elk punt in de webgraaf is ófwel gezond (maar wel vatbaar voor een virus), ófwel geïnfecteerd door een virus. Na een tijdje wordt een geïnfecteerd punt weer gezond, onafhankelijk van de toestand van zijn buren. Hoe meer geïnfecteerde buren een gezond punt heeft, des te sneller wordt het ook geïnfecteerd. De aanwezigheid van antivirussoftware is ook in het contactproces verwerkt. Met dit model kunnen we virussen zodanig goed nabootsen, dat we aan de eigenschappen van het virus kunnen zien of het snel zal uitsterven, of dat het altijd zal blijven voortbestaan. 39
Bibliogra e [1] Bonato, Anthony. A Course on the Web Graph, American Mathematical Society, March 2008. [2] Brandts, Jan. Over de wiskunde die Google groot maakte, Universiteit van Amsterdam, 13 januari 2009. [3] Kleinberg, Jon M. Authoritive Sources in a Hyperlinked Environment, ??? 1998 [4] R. Lempel, S. Moran. SALSA: The Stochastic Approach for Link-Structure Analysis, ACM Transactions on Information Systems, Volume 19, No. 2, April 2001. [5] http://www.nownederland.nl/nieuws/2010/05/aantal-webpaginas-wereldwijdminimaal-20-miljard/ [6] M. Faloutsos, P. Faloutsos, C. Faloutsos. On power-law relationships of the internet topology. 1999. [7] N. Berger, J. Chayes, C. Borgs, A. Saberi, On the spread of viruses on the Internet, Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, 2005. [8] A. Barabási, R. Albert. Emergence of scaling in random networks, Science, 286:509-512, 1999. [9] D. Lay. Linear Algebra and Its Applications, Third Edition, Pearson International Edition, 2003. [10] M. Boyle. Notes on the Perron-Frobenius theory of nonnegative matrices. [11] R. Durrett. Probability: Theory and Examples. Duxbury Press, 1996. [12] J. R. Norris. Markov Chains. Cambridge University Press, 1997. [13] A. Graham. Nonnegative matrices and applicable topics in linear algebra. John Wiley&Sons, New York, 1987. [14] http://www.maths.nottingham.ac.uk/personal/sw/HG2NLA/pow.pdf
40
