PageRank¹ is een algoritme dat gebruikt werd door Google om de volgorde van zoekresultaten te bepalen. Het werd bedacht door de oprichters van Google — Sergey Brin en Larry Page — en de naam is een woorspeling op de naam van één van de bedenkers en op het concept webpagina (Engels: web page). Het Internet vormt immers een verzameling van webpagina's die via hyperlinks² naar andere webpagina's verwijzen. PageRank gebruikt deze hyperlinks om een ruwe schatting te maken van hoe belangrijk elke webpagina is. Het onderliggende idee is dat belangrijke websites veel verwijzingen krijgen van andere websites.

Als voorbeeld nemen we het bovenstaande netwerk met zes webpagina's (blauwe cirkels) die we aanduiden met de letters A–F. De zwarte pijlen stellen hyperlinks tussen webpagina's voor. De pijlen die vertrekken vanaf een webpagina noemen we de uitgaande verwijzingen van de webpagina, dus webpagina E heeft uitgaande verwijzingen naar webpagina's D en F. De verzameling van alle webpagina's waarnaar webpagina $$p$$ verwijst, noteren we als $$\text{uit}(p)$$, dus $$\text{uit}(\text{E}) = \{\text{D}, \text{F}\}$$. De pijlen die aankomen bij een webpagina noemen we de inkomende verwijzingen van de webpagina, dus webpagina E heeft inkomende verwijzingen van webpagina's C en D. De verzameling van alle webpagina's die naar webpagina $$p$$ verwijzen, noteren we als $$\text{in}(p)$$, dus $$\text{in}(\text{E}) = \{\text{C}, \text{D}\}$$.

In het netwerk kunnen webpagina's voorkomen die geen enkele uitgaande verwijzing hebben. In het voorbeeldnetwerk is dat het geval voor webpagina B. PageRank doet alsof dergelijke webpagina's uitgaande verwijzingen hebben naar elke andere webpagina in het netwerk (inclusief de webpagina zelf). Automatisch krijgen alle webpagina's in het netwerk dan ook een inkomende verwijzing van webpagina's zonder uitgaande verwijzingen. We hebben die bijkomende verwijzingen aangeduid met grijs gestreepte pijlen in de voorstelling van het voorbeeldnetwerk. Voor PageRank geldt daarvoor dus dat $$\text{in}(\text{E}) = \{\text{B}, \text{C}, \text{D}\}$$.

PageRank berekent voor elke webpagina $$p$$ in het netwerk een score $$S(p) \in \mathbb{R}$$ die de belangrijkheid van de webpagina aanduidt. Deze score ligt tussen 0 en 1, en de som van de scores van alle webpagina's in het netwerk is gelijk aan 1. Als er $$N$$ webpagina's zijn in het netwerk, dan krijgt elke webpagina initieel (stap 0) score $$\frac{1}{N}$$. Daarna worden stap voor stap nieuwe scores berekend voor alle webpagina's in het netwerk. Bij elke volgende stap wordt de nieuwe score $$S(p)$$ voor elk webpagina $$p$$ als volgt berekend op basis van de oude scores uit de vorige stap: \[ S(p) = \frac{1 - d}{N} + d \left( \sum_{q\ \in\ \text{in}(p)}\frac{S(q)}{|\text{uit}(q)|}\right) \] Daarbij is de dempingsfactor $$d \in \mathbb{R}$$ een waarde tussen 0 en 1. De notatie $$|\text{uit}(q)|$$ staat voor het aantal elementen van de verzameling $$\text{uit}(q)$$, dus het aantal uitgaande verwijzingen van de webpagina $$q$$.

Google gebruikt standaard de waarde $$d = 0.85$$ als dempingsfactor. Als we die waarde gebruiken, dan wordt de score voor webpagina E in stap 1 berekend als \[ S(\text{E}) = \frac{1 - d}{N} + d \left( \frac{S(\text{B})}{|\text{uit}(\text{B})|} + \frac{S(\text{C})}{|\text{uit}(\text{C})|} + \frac{S(\text{D})}{|\text{uit}(\text{D})|} \right) = \frac{0.15}{6} + 0.85 \left( \frac{\frac{1}{6}}{6} + \frac{\frac{1}{6}}{3} + \frac{\frac{1}{6}}{2} \right) = \frac{1}{6} \] Hieronder vatten we de scores voor alle webpagina's van het voorbeeldnetwerk samen, met hun initiële waarde (stap 0), de waarde na vijf opeenvolgende stappen (stap 1–5), en de waarde na 100 stappen. We onderstrepen nogmaals dat de scores in een volgende stap telkens berekend worden op basis van de scores uit de voorgaande stap.

In de praktijk worden opeenvolgende stappen berekend totdat de scores nauwelijks nog veranderen. In het originele artikel over PageRank geven dat oprichters van Google aan dat dit in een netwerk met 332 miljoen hyperlinks het geval was na 52 stappen. Voor een netwerk met half zoveel hyperlinks was dat al het geval na 45 stappen.

Opgave

De structuur van een netwerk met $$N$$ webpagina's wordt beschreven in een tekstbestand. Elke webpagina wordt aangeduid met een uniek label (str) dat geen tabs bevat. Het bestand bestaat uit $$N$$ regels, één voor elke webpagina in het netwerk. Elke regel bestaat uit het label $$p$$ van een webpagina, gevolgd door de labels van de webpagina's waarnaar webpagina $$p$$ verwijst. Een regel bevat dus altijd minstens één label, en alle labels op de regel worden van elkaar gescheiden door tabs. Een tekstbestand dat de structuur van het voorbeeldnetwerk beschrijft, ziet er dan bijvoorbeeld als volgt uit:

A	B	C
B
C	A	B	E
D	E	F
E	D	F
F	D

Definieer een klasse Netwerk waarmee netwerken kunnen voorgesteld worden van webpagina's die naar elkaar verwijzen via hyperlinks. Bij het aanmaken van een netwerk (Netwerk) moet de locatie (str) doorgegeven worden van een tekstbestand dat de structuur van het netwerk beschrijft. Optioneel kan aan de parameter demping ook nog een dempingsfactor $$d \in \mathbb{R}$$ doorgegeven worden (standaardwaarde: 0.85). Elke webpagina in het netwerk heeft een score (een reeël getal tussen 0 en 1), en die is initieel gelijk is aan $$\frac{1}{N}$$ voor een netwerk met $$N$$ webpagina's.

Als er een netwerk (Netwerk) wordt doorgegeven aan de ingebouwde functie len, dan moet die teruggeven hoeveel webpagina's (int) er in het netwerk zitten. Voorts moet elk netwerk minstens de volgende methoden ondersteunen:

• Een methode uitgaand waaraan het label $$p$$ van een webpagina moet doorgegeven worden. De methode moet een verzameling (set) teruggeven met de labels van alle webpagina's waar $$p$$ naar verwijst volgens PageRank (i.e. $$\text{uit}(p)$$).

• Een methode inkomend waaraan het label $$p$$ van een webpagina moet doorgegeven worden. De methode moet een verzameling (set) teruggeven met de labels van alle webpagina's die naar $$p$$ verwijzen volgens PageRank (i.e. $$\text{in}(p)$$).

• Een methode score waaraan het label $$p$$ van een webpagina moet doorgegeven worden. De methode moet de huidige score (float) van $$p$$ teruggeven (i.e. $$S(p)$$).

• Een methode volgende_score waaraan het label $$p$$ van een webpagina moet doorgegeven worden. De methode moet de nieuwe score (float) teruggeven die $$p$$ zou krijgen in de volgende stap van het PageRank-algoritme, berekend op basis van de huidige scores van de webpagina's.

• Een methode scores_initialiseren waaraan geen argumenten moeten doorgegeven worden. De methode moet ervoor zorgen dat elke webpagina in het netwerk een score $$\frac{1}{N}$$ krijgt, voor een netwerk $$N$$ met webpagina's.

• Een methode scores_bijwerken met een optionele parameter stappen waaraan een getal $$n \in \mathbb{N}_0$$ kan doorgegeven worden. De methode moet ervoor zorgen dat elke webpagina in het netwerk een nieuwe score krijgt door $$n$$ stappen van het PageRank-algoritme uit te voeren. Als er niet expliciet een waarde wordt doorgegeven aan de parameter stappen, dan is $$n = 1$$.

• Een methode rangschikking waaraan geen argumenten moeten doorgegeven worden. De methode moet een lijst (list) teruggeven met voor elke webpagina in het netwerk een tuple (tuple) met het label en de score van de webpagina. De tuples moeten opgelijst worden volgens dalende score. Tuples met dezelfde score moeten alfabetisch volgens label opgelijst worden.

Voorbeeld

In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand www.txt³ zich in de huidige directory bevindt.

>>> netwerk = Netwerk('www.txt4')
>>> len(netwerk)
6
>>> netwerk.uitgaand('A')
{'B', 'C'}
>>> netwerk.uitgaand('B')
{'A', 'B', 'C', 'D', 'E', 'F'}
>>> netwerk.uitgaand('C')
{'A', 'B', 'E'}
>>> netwerk.uitgaand('D')
{'E', 'F'}
>>> netwerk.uitgaand('E')
{'D', 'F'}
>>> netwerk.uitgaand('F')
{'D'}
>>> netwerk.inkomend('A')
{'B', 'C'}
>>> netwerk.inkomend('B')
{'A', 'B', 'C'}
>>> netwerk.inkomend('C')
{'A', 'B'}
>>> netwerk.inkomend('D')
{'B', 'E', 'F'}
>>> netwerk.inkomend('E')
{'B', 'C', 'D'}
>>> netwerk.inkomend('F')
{'B', 'D', 'E'}
>>> netwerk.score('A')
0.16666666666666666
>>> netwerk.volgende_score('A')
0.09583333333333334
>>> netwerk.volgende_score('E')
0.16666666666666666
>>> netwerk.scores_bijwerken()
>>> netwerk.score('A')
0.09583333333333334
>>> netwerk.score('E')
0.16666666666666666
>>> netwerk.scores_bijwerken()
>>> netwerk.score('A')
0.08245370370370371
>>> netwerk.scores_bijwerken(stappen=100)
>>> netwerk.score('A')
0.05170474575702128
>>> netwerk.score('B')
0.07367926270375533
>>> netwerk.score('C')
0.057412412496432724
>>> netwerk.score('D')
0.34870368521481654
>>> netwerk.score('E')
0.1999038119733183
>>> netwerk.score('F')
0.268596081854656
>>> netwerk.scores_initialiseren()
>>> netwerk.score('A')
0.16666666666666666
>>> netwerk.scores_bijwerken(stappen=100)
>>> netwerk.score('A')
0.05170474575702128
>>> netwerk.rangschikking()
[('D', 0.34870368521481654), ('F', 0.268596081854656), ('E', 0.1999038119733183), ('B', 0.07367926270375533), ('C', 0.057412412496432724), ('A', 0.05170474575702128)]

>>> netwerk = Netwerk('www.txt5', demping=0.9)
>>> netwerk.scores_bijwerken(stappen=100)
>>> netwerk.rangschikking()
[('D', 0.3750808151098345), ('F', 0.2862458852154), ('E', 0.20599833187742753), ('B', 0.05395734936310289), ('C', 0.04150565335623299), ('A', 0.03721196507800199)]

Epiloog

In 1996 lanceerden Sergey Brin en Larry Page een zoekmachine onder de naam BackRub⁶. Bij de lancering indexeerde de zoekmachine 75 miljoen⁷ webpagina's. In 2021 indexeert Google meer dan 130 triljoen⁸ webpagina's. Maar hoe groot dat getal ook mag klinken, het komt belange nog niet in de buurt van een googol⁹.

Bronnen

• Brin S, Page L (1998). The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems 30(1–7), 107–117. ¹⁰

• Page L, Brin S, Motwani R, Winograd T (1999). The PageRank citation ranking: bringing order to the web. Stanford InfoLab. ¹¹