PageRank — het idee
Leerdoel: je begrijpt waarom PageRank links als stemmen telt, waarom een stem van een belangrijke pagina zwaarder weegt, en waarom je het daarom in rondes uitrekent. Code komt pas daarna.
Het college
Bekijk eerst de slides van je docent. Onder de slides staat het idee nog een keer op een rij.
Slides openen in een nieuw tabblad (PDF)
Het probleem
Typ iets in Google en je krijgt miljoenen pagina's terug, in een volgorde die meestal klopt. Hoe bepaalt een computer welke pagina het belangrijkst is?
Je zou de links kunnen tellen: een pagina waar veel andere pagina's naar linken, zal wel belangrijk zijn. Maar dan maak je duizend nep-pagina's die naar je eigen site linken, en je staat bovenaan. En een link van een belangrijke pagina hoort zwaarder te tellen dan een link van een pagina die niemand kent.
Links zijn stemmen
Larry Page en Sergey Brin, die later Google oprichtten, bedachten in 1998 PageRank. Daarin is elke link een stem. Een pagina verdeelt haar "belang" over de pagina's waar ze naar linkt, en een stem van een belangrijke pagina is dus meer waard. Een pagina is belangrijk als er belangrijke pagina's naar linken.
Daar zit een cirkel in. Om te weten hoe belangrijk A is, moet je weten hoe belangrijk de pagina's zijn die naar A linken, en om dat te weten moet je weer verder terug. Dat kip-ei-probleem los je op door de berekening te herhalen tot de waarden niet meer veranderen.
De random surfer
Stel je een random surfer voor: iemand die eindeloos doorklikt en op elke pagina een willekeurige link kiest. De PageRank van een pagina is het deel van de tijd dat de surfer daar is. Op een pagina waar veel naartoe leidt, komt hij vaker langs.
Maar wat als de surfer vastloopt in een groepje pagina's dat alleen naar
elkaar linkt? Daarvoor is damping: met kans d volgt de surfer een
link, en met kans 1 − d springt hij naar een willekeurige pagina ergens
op het web. De gebruikelijke waarde is d = 0,85. Zo komt de surfer
overal, en loopt hij nooit voorgoed vast.
Een klein web
Je werkt steeds met dit mini-web van vier pagina's. Een pijl A → B
betekent "A linkt naar B".
A → B, A → C
B → C
C → A
D → C
C krijgt links van A, B én D, en wordt waarschijnlijk de populairste.
Naar D linkt niemand; die zal laag eindigen.
Wat we gaan bouwen
Je schrijft stap voor stap een functie die voor zo'n web de PageRank van elke pagina uitrekent, met deze formule:
rank(p) = (1 − d)/N + d · Σ rank(i) / aantal_links(i)
i → p
Het belang van pagina p is een klein basisdeel (1−d)/N, plus de
stemmen van alle pagina's i die naar p linken. Elke stem is het belang
van i gedeeld door het aantal links dat i uitdeelt. Die berekening
herhaal je tot de waarden nauwelijks nog veranderen.
Het stemmen kun je klassikaal naspelen met fiches op ditzelfde mini-web: print Stemmen met fiches.
Zo bouw je het op
De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":
- Bouwsteen 1 — het web als graph
- Bouwsteen 2 — de startverdeling
- Bouwsteen 3 — één pagina bijwerken
- Bouwsteen 4 — itereren tot het stabiel is
Daarna zet je alles samen in De complete oplossing, en ga je het aanpassen en zelf bouwen.
Door naar stellingen →.