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 B₁, B₂, B₃, B₄ en B₅ 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 B₂ naar B₁ betekent dat B₂ sponsor is van B₁.

Figuur 1. Een gerichte graaf van sponsorrelaties

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.

h3. Wat is een graaf? Een graaf in de wiskunde is ongeveer wat we in het dagelijks leven een netwerk noemen. Een graaf bestaat per definitie uit knopen, die verbonden kunnen zijn door takken (ook wel zijden of kanten genaamd). Grafen duiken overal in het dagelijks leven op. Als je treinstations beschouwt als knopen en rails als takken, vormen de spoorwegen een graaf. Het kan abstracter: je vriendennetwerk is ook een graaf. Uiteraard zijn alle knopen in die graaf door takken met jou verbonden, maar er loopt alleen een tak van vriend A naar vriend B, als die ook met elkaar bevriend zijn. ‘Bevriend zijn’ is wederkerig: als A bevriend is met B, is B dat ook met A. De takken hebben daarom geen richting, er hangt geen ‘pijltje’ aan. Dat wordt anders als je een tak definieert als ‘heeft diens telefoonnummer in z’n mobieltje staan’. Als A het telefoonnummer van B heeft, hoeft B niet ook A’s telefoonnummer te hebben. De takken hebben dan een richting, en zo’n graaf heet een gerichte graaf. Het internet is een reusachtige gerichte graaf, met webpagina’s als knopen en de hyperlinks als takken. Deze graaf is gericht, omdat een hyperlink van de ene webpagina verwijst naar een andere, maar niet andersom (twee webpagina’s kunnen naar elkaar verwijzen, maar dat vergt twee aparte links). De afbeelding hierboven geeft het wereldwijde web weer als graaf. Het is gegenereerd door het tekenprogramma Large Graph Layout van Alex Adai, op basis van gegevens van The Opte Project van Barrett Lyon.

Flickr, NetMapper via CC BY-NC 2.0

Rapportcijfers

Het World Wide Web kan net als het sponsor-netwerk van de kabouters gezien worden als een gerichte graaf. Een pijl van B₁ naar B₂ geeft dan aan dat webpagina B₁ een hyperlink heeft waarmee je naar B₂ 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.

Figuur 2. Hoeveel knikkers moet je B₁ en B₂ geven om een evenwichtsverdeling te krijgen? Dit is natuurlijk een heel eenvoudig geval. Merk wel op, dat als je een oplossing hebt gevonden, je alle kabouters ook tweemaal zoveel had kunnen geven. Sterker nog, ieder veelvoud van een oplossing is weer een oplossing. Dit zullen we nog vaker tegenkomen.

Figuur 3. Nog twee grafen. De eerste evenwichtsverdeling is nog makkelijk te vinden, de tweede al wat moeilijker.

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.

Figuur 4. De grafen van figuur 3 weergegeven als Goozzle

Hier is het idee als volgt: In het rooster is een hokje (x, y) open als er een pijl gaat van B_x naar B_y, 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.

Figuur 5. Los deze Goozzle op. Om je op weg te helpen, hebben we één van de drie gezochte getallen al ingevuld.

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.

Figuur 6. Een onoplosbare Goozzle

In dit voorbeeld krijgt kabouter B₃ knikkers van B₁ en B₂, maar geeft zelf niets weg. Hij zal dus altijd meer bezitten dan ervoor, tenzij B₁ en B₂ 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.

Figuur 7. Dezelfde Goozzle als in figuur 6, maar nu met teleportatie

Reden om ook een pijl te trekken naar de loshangende knoop zelf, is dat ieder van de pagina’s B₁, B₂, B₃ even veel profiteert van de PageRank die B₃ 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.

Figuur 8. Goozzle met teleportatie en α-factor

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.

h3. π^∗ = π^∗(α S + (1 – α)E): de E = mc² van het internet In de PageRank-vergelijking komen de vector π^∗ en matrices S en E voor. Verder is α een getal tussen 0 en 1. Een vector kun je voorstellen door een rij getallen, een matrix door een rechthoek van getallen. Vectoren en matrices vermenigvuldig je met elkaar door hun getallen volgens bepaalde rekenregels te vermenigvuldigen en op te tellen. Een Goozzle is de ‘sudokumanier’ om de PageRank-vergelijking op te schrijven. De bovenbalk stelt π^∗ voor, de kolom rechts ook, en de beide vierkanten stellen een matrix voor, met in elk dicht hokje een 0 en in de open hokjes getallen ongelijk 0. De figuur hierboven geeft de PageRank-vergelijking voor een internet met drie pagina’s. Als je de PageRank van 10 miljard pagina’s wilt berekenen, bevat de vergelijking twee matrices van elk 10¹⁰ x 10¹⁰ = 10²⁰ getallen! De enige praktische manier om een oplossing van zo’n enorme matrixvergelijking te vinden, is door min of meer op goed geluk een startvector π^∗(0) boven in de Goozzle in te vullen. Dat levert rechts een zekere π^∗(1) op, die je weer bovenin invult, zodat je π^∗(2) vindt, enzovoort. Deze procedure heet iteratie. In formulevorm: π^∗(n + 1) = π^∗(n) (αS + (1 – α)E). De bedoeling is dat dit uiteindelijk een vector oplevert die niet meer verandert, want dan heb je de evenwichtsverdeling π^∗ gevonden. Google doet deze Google dance eens per maand. Over matrixvergelijkingen is veel bekend, waardoor wiskundigen weten onder welke voorwaarden, en hoe snel, zo’n iteratie naar de evenwichtsverdeling ‘toeloopt’. Voor de PageRank-vergelijking werkt iteratie goed. De structuur van het internet verandert wel voortdurend, maar een groot deel van de hyperlinks zal na een maand nog bestaan. Je zou dus verwachten dat je de π^∗ van deze maand relatief snel vindt met de iteratie-procedure, door als startvecor de π^∗ van de maand daarvoor te nemen. Dit blijkt echter niet waar te zijn: het meest efficiënt is om met een startvector te beginnen waarin alle PageRanks hetzelfde zijn, en alles elke maand weer opnieuw uit te rekenen.

Zie verder:

• De wiskunde van Jan Brandts (Kennislinkartikel)
• De homepage van Jan Brandts
• Over de wiskunde die Google groot maakte (pdf)
• PageRank