Als je bij Google een zoekterm intikt, zoeken diens computers in de totale lijst met tien miljard webpagina’s alle pagina’s bij elkaar waarin dit trefwoord voorkomt. Dat zijn er meestal veel te veel, maar omdat alle webpagina’s een rapportcijfer hebben, laat Google slechts de selectie met de hoogste rapportcijfers zien. Die selectie stemt vaak verrassend goed overeen met wat je echt belangrijk vindt. Om uit te leggen hoe dat kan, introduceren we eerst een goede fee en een stel onbaatzuchtige kabouters.
Kabouters en een goede fee
Stel, er zijn vijf kabouters die we even B1, B2, B3, B4 en B5 noemen. Ieder van deze kabouters is sponsor van een aantal andere kabouters. In figuur 1 kun je zien wie een sponsor van wie is: bijvoorbeeld, de pijl van B2 naar B1 betekent dat B2 sponsor is van B1.

Behalve kabouters is er ook een goede fee, in het bezit van enorme hoeveelheden goudstukken, die ze graag aan de kabouters wil uitdelen. Er is echter een probleem: zodra een kabouter goudstukken krijgt, zal hij ze eerlijk verdelen over alle kabouters die hij sponsort. Zo zitten kabouters nu eenmaal in elkaar. De fee besluit daarom elke kabouter een zodanig aantal goudstukken te geven (minstens één), dat nadat iedere kabouter zijn goudstukken heeft verdeeld over zijn gesponsorden, ze allemaal weer net zoveel goudstukken hebben als ervóór. Zo ontstaat dus een evenwichtsverdeling van de goudstukken over de kabouters. Maar hoe kan ze dit doen? Omdat dit niet even snel uit te leggen is, komen we er later op terug.

Rapportcijfers
Het World Wide Web kan net als het sponsor-netwerk van de kabouters gezien worden als een gerichte graaf. Een pijl van B1 naar B2 geeft dan aan dat webpagina B1 een hyperlink heeft waarmee je naar B2 kunt surfen. De hoeveelheid knikkers waarmee het raadsel is opgelost, komt overeen met het rapportcijfer van de webpagina. In die situatie heeft een kabouter veel knikkers als:
- hij sponsors heeft met veel knikkers,
- die sponsors niet veel anderen sponsoren.
Dit komt overeen met de vuistregels die de oprichters van Google, Larry Page en Sergei Brin, in hun PageRank-model tot uitdrukking wilden laten komen, namelijk, een webpagina is belangrijk als:
- er naar verwezen wordt door belangrijke pagina’s,
- die pagina’s niet ook naar veel andere pagina’s verwijzen.
Oftewel, je bent goed af als Koningin Beatrix op haar webpagina naar de jouwe verwijst, maar al een stuk minder goed als ze naar al haar onderdanen blijkt te verwijzen! Een evenwichtsverdeling van de knikkers is in figuur 1 al niet zo eenvoudig te vinden. Bij de onderstaande grafen is het wat makkelijker.


Goozzle
De oplossingen van de grafen hierboven kun je vinden door gewoon maar wat te proberen. We introduceren nu een andere grafische voorstelling van de raadsels, de Goozzle, om ook moeilijker grafen aan te kunnen, zie figuur 4.

Hier is het idee als volgt: In het rooster is een hokje (x, y) open als er een pijl gaat van Bx naar By, anders is het dicht.
- Plaats knikkers in de bovenste drie vakjes,
- verdeel ze per kolom eerlijk over de open vakjes er verticaal onder,
- verplaats ze per rij horizontaal naar de rechter drie vakjes.
Als de aantallen knikkers in de rechter vakjes nu hetzelfde zijn als waarmee je bovenin begon, heb je de evenwichtsverdeling gevonden.

Als je liever niet geholpen was bij deze Goozzle: de 4 die al ingevuld is, is niet echt een cadeau. We hadden immers al gezien dat veelvouden van een oplossing ook weer oplossingen zijn. Er is dan ook een veelvoud dat inderdaad een 4 op die positie heeft. Mocht dit tijdens het oplossen ergens tot gebroken knikkers – breuken dus – leiden, is dat niet erg: na afloop vermenigvuldigen we dan alles met een getal zodanig dat alle breuken verdwijnen.
Onvolkomenheden
De voorgaande Goozzles hebben allemaal een oplossing. Dit hoeft echter niet, zoals blijkt uit het voorbeeld in figuur 6.

In dit voorbeeld krijgt kabouter B3 knikkers van B1 en B2, maar geeft zelf niets weg. Hij zal dus altijd meer bezitten dan ervoor, tenzij B1 en B2 geen knikkers hadden. Maar de fee gaf iedere kabouter ten minste één knikker. Deze Goozzle heeft dus geen oplossing.
Wat is op internet het equivalent van een kabouter die niemand sponsort? Een webpagina waarnaar wel gelinkt wordt, maar die zelf geen links naar andere pagina’s bevat. Beschouwd als graaf, noemen we zoiets een loshangende knoop (dangling node in het Engels). Google-oprichters Page en Brin argumenteren dat als een surfer in een loshangende knoop aankomt, hij bij gebrek aan hyperlinks een willekeurig nieuw webadres in de browserbalk zal intikken.
In een graaf komt dit erop neer dat je vanuit een loshangende knoop pijlen trekt naar alle andere knopen, inclusief de loshangende knoop zelf, hoewel deze takken dus eigenlijk niet echt bestaan, zie figuur 7. Het surfen naar een andere webpagina zonder daarbij een hyperlink te volgen wordt teleportatie genoemd. Je denkt misschien dat loshangende knopen zeldzaam zijn op internet, maar in feite is dit ongeveer viervijfde van alle bestanden op het World Wide Web! Plaatjes (.jpg, .gif) en pdf-bestanden bevatten namelijk geen links.

Reden om ook een pijl te trekken naar de loshangende knoop zelf, is dat ieder van de pagina’s B1, B2, B3 even veel profiteert van de PageRank die B3 uiteindelijk krijgt. Geen van de pagina’s wordt dus bevoordeeld in deze behandeling van de loshangende knoop. Toch zijn nu nog niet alle problemen de wereld uit. Bijvoorbeeld, het World Wide Web zou kunnen bestaan uit meerdere groepen pagina’s die onderling geen links hebben. Pagina’s uit verschillende groepen kunnen dan niet eerlijk met elkaar worden vergeleken, omdat de hoeveelheid knikkers binnen iedere groep met een willekeurig getal vermenigvuldigd kan worden.
Meer teleportatie
Het algoritme van Brin en Page houdt er ook nog rekening mee, dat een surfer niet alleen een nieuw webadres in de browserbalk kan intikken als hij of zij in een loshangende knoop zit, maar ook op andere momenten. De vraag is wanneer, en hoe vaak. Een surfer zal een deel α (0 < α < 1) van de tijd hyperlinks volgen, en een deel 1 – α een nieuw adres in de browserbalk intikken. Googles uiteindelijke model bestaat uit een combinatie van het model dat we hadden na het repareren van de problemen die door loshangende knopen worden veroorzaakt, en het volledige teleportatie-model. Dit laatste model gaat er (fictief) vanuit dat er van iedere pagina een link is naar iedere andere pagina, inclusief zichzelf.
Hoe wordt deze combinatie in de praktijk gemaakt? Door te stellen dat een deel α van de knikkers via de pijlen moet lopen van het oorspronkelijke model, en het resterende deel volgens de pijlen van het volledige teleportatie model, zie het kader onderaan dit artikel.
Speurwerk
Omdat andere zoekmachines graag van het succes van Google zouden meeprofiteren, houdt Google veel details van z’n model geheim, waaronder ook α. Wiskundig speurwerk heeft echter opgeleverd dat Google α = 0,85 = 17/20 gebruikt. Het linkerdeel van de Goozzle in figuur 8 is het teleportatieblok; het 3/20-ste deel van de knikkers dat hierin belandt wordt gelijkelijk verdeeld over alle andere pagina’s.

We zien dat het overeenkomstige kabouterraadsel erg ingewikkeld kan worden. De vraag is nu dus hoe de fee de kabouters knikkers kan geven zodanig, dat als 85% van de knikkers via het rechter blok in figuur 8 wordt verdeeld, en 15% van de knikkers volgens het linker blok, de situatie weer is zoals tevoren. En voor het echte World Wide Web dan ook nog eens met zo’n tien miljard kabouters in plaats van de drie die we hier bekijken.
Het kost maar liefst drie dagen om deze tien miljard rapportcijfers uit te rekenen met behulp van grote hoeveelheden aan elkaar geschakelde supercomputers. Dat is erg duur, en dus doet Google dit maar één keer per maand. Dit wordt ook wel de Google dance genoemd. Dus maximaal eens per maand verandert de PageRank van een website. Dit is de beschrijving van het model die Page en Brin zelf hebben gepubliceerd, maar natuurlijk is dit nog lang niet de hele waarheid. Google heeft ongetwijfeld nog heel wat kleinere en grotere slimmigheden om efficiÎnt om te gaan met zoekopdrachten en pageranking. Maar zoals gezegd, die zijn voor het grootste deel geheim.

Zie verder:
- De wiskunde van Jan Brandts (Kennislinkartikel)
- De homepage van Jan Brandts
- Over de wiskunde die Google groot maakte (pdf)
- PageRank