Deel dit artikel

in minder dan tien jaar heeft google in de brandz top 100 van de meest waardevolle merknamen microsoft van de eerste plaats geduwd. deze succesvolle internetzoekmotor slaagt er bijna altijd in om de meest relevante webpagina’s voor de ingetikte zoekterm vooraan te plaatsen. hoe bepaalt pagerank echter dat de ene pagina populairder en dus belangrijker is dan de andere? de kracht van google steunt op pure wiskunde.

Zeg nooit zomaar googelen tegen zoeken op het internet

Adhemar Bultheel


De advocaten van Google moeten bovenstaande inverse bananenslogan in gedachten hebben gehad toen ze protesteerden tegen de verklaring van het woord ‘googelen’ in verschillende Nederlandse woordenboeken als ‘zoeken op het internet’. Googelen kan je alleen met Google en dat is een beschermde merknaam. In feite is de naam Google een tikfout want het was de bedoeling van de stichters Larry Page en Sergey Brin, twee studenten aan de Stanford University, om in 1998 ‘Googol’ te laten registreren. Gezien de complexiteit die het web toen al had, leek dit hen een geschikte naam. Het betekent immers – een één gevolgd door honderd nullen – wat groter is dan het aantal elementaire deeltjes in het gekende heelal. Edward Kasner, een Amerikaanse wiskundige, populariseerde de term googol rond 1920 om uit te leggen dat heel groot nog niet hetzelfde is als oneindig. In feite was het zijn negenjarige neefje dat googol als naam suggereerde. Misschien heeft die wel google gezegd en heeft Kasner het verkeerd genoteerd.

Hoe kan Google in april 2007 – in minder dan tien jaar na zijn oprichting – zijn uitgegroeid tot de nummer één van de Brandz Top 100 van de meest waardevolle merknamen? Die plaats was lang bezet door Microsoft. De motor die het bedrijf zijn kracht geeft, is de Googlezoekmachine die erin slaagt om bijna steeds de meest relevante webpagina’s voor de ingetikte zoekterm vooraan te plaatsen. Die volgorde wordt bepaald door een algoritme dat PageRank heet (een woordspeling omdat Larry Page één van de auteurs is). Het gebeurt niet gauw dat wiskunde in de media komt, maar een artikel als ‘The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google’ van Kurt Bryan en Tanya Leise in de SIAM Review in 2006 trok wel de aandacht. Het bedrag in de titel verwijst naar de geschatte waarde van Google toen het bedrijf in 2004 naar de beurs ging.

Hoewel het not done is toe te geven dat je niet zonder dt-fouten kan schrijven, is het nog steeds bon ton om te verkondigen dat je niets van wiskunde kent. Anderzijds is het dan weer hip om met IT-termen te goochelen (met ch!). Misschien is deze tekst voor een aantal niet-wiskundigen een inleiding op de googlogie die met enige gretigheid zal worden gesavoureerd en kan dit stukje wiskunde in het (hopelijk) zoete googlebroodje worden verstopt. Dat gebeurt trouwens ook in het boek Google’s PageRank and Beyond: The Science of Search Engine Rankings, van de wiskundigen Amy N. Langville en Carl D. Meyer, respectievelijk verbonden aan het College of Charleston in South Carolina en aan de North Carolina State University.


De PageRank wordt aangegeven door het groene streepje op de Google taakbalk

Hoe bepaalt PageRank dat een webpagina populairder en dus belangrijker is dan een andere? Op een doorsneewebpagina staan gemiddeld ongeveer tien verwijzingen naar andere pagina’s. Dat zijn de outlinks voor die pagina. Omgekeerd zullen andere pagina’s dan weer verwijzen naar die pagina. Dat zijn dan de inlinks. Als pagina A verwijst naar pagina S, dan is dit een stem die A uitbrengt op S in de poppoll die op het web continu aan de gang is. Je zou zo de pagina met de meeste inlinks als de meest populaire kunnen beschouwen. Volgens het democratische principe krijgt elke pagina echter maar één stem om uit te delen. Pagina A kan dan die ene stem helemaal aan pagina S geven door alleen naar S te linken. A kan echter ook zijn stem gelijk verdelen over meerdere pagina’s. Als A bijvoorbeeld linkt naar drie pagina’s S ,K en U, dan krijgen die elk
een derde van de stem van A. Zo krijgt elke link een waarde. De populariteit van A wordt dan gemeten door de som te maken van de waardes van haar inlinks. Dit is een goede poging, maar zo zit de reële en dus ook de virtuele wereld niet in elkaar. Je behoort slechts tot de jetset als je populair bent bij de jetsetpopulatie. In een democratie is iedereen gelijk, maar de ene is al wat gelijker dan de andere. Daarom zal een stem van een populaire pagina uiteindelijk zwaarder wegen dan een stem van een niet-populaire pagina. De stem die A kan uitdelen, wordt gewogen met haar populariteitsindex. Met andere woorden een pagina verdeelt niet haar stem, maar verdeelt haar eigen populariteit over haar outlinks terwijl die populariteit wordt bepaald door wat de pagina aan populariteit binnenkrijgt via haar inlinks. Hiermee hebben we de moederversie van PageRank gedefinieerd.

Een benadering van de exacte oplossing die toelaat om een goede rangschikking te maken, is voldoende

Die laatste formulering is een zelfrefererend systeem. Om de populariteit van pagina A te berekenen moet je immers de populariteit kennen van alle pagina’s die naar A verwijzen, maar als A ook verwijst naar andere pagina’s, dan kan je de populariteit van die andere pagina’s niet berekenen voor je de populariteit van A kent. Dan zit je met een patstelling. Het is ook een transcendent probleem dat je nooit exact kan oplossen met een eindig aantal klassieke wiskundige bewerkingen. Hoe slaagt Google er dan toch in een rangschikking te bepalen? Heel eenvoudig: je moet het probleem niet exact willen oplossen. Een benadering van de exacte oplossing die toelaat om een goede rangschikking te maken, is voldoende. Dit is een algemeen principe. Wiskundige modellen zijn ook maar benaderingen van de realiteit en ze gelden slechts in een ideale, virtuele wereld. Theoretisch werkt de wiskunde met getallen die oneindig veel cijfers kunnen hebben en met lijnen en vlakken die geen dikte hebben. Die bestaan echter niet. Hoe geavanceerd onze toestellen ook zijn om het allerkleinste te meten, we zullen steeds op een grens stoten waaronder we geen onderverdeling meer kunnen maken. De waarneembare realiteit is niet continu, maar discreet. Dit besef en de daarmee gepaard gaande ontwikkeling van de wetenschap zijn er vooral gekomen na het ontstaan van digitale computers, waar de kleinst mogelijke korrel aan informatie één bit is.

Laten we echter terugkeren naar PageRank. Stel dat je vijf pagina’s (A,S,L,K,U) moet sorteren volgens PageRank. Je discretiseert de tijd in tijdstippen 0,1,2, … en start op het tijdstip 0 met de veronderstelling dat alle pagina’s even belangrijk zijn. Dit wordt voorgesteld door de rij . Op tijdstip 1 verdeelt elke pagina haar rang over bevriende pagina’s (haar outlinks). Dit herverdeelt de populariteit en je krijgt een nieuwe rij van getallen met voor elke pagina de rang na de herverdeling. Op tijdstip 2 verdeelt weer elke pagina zijn huidige rang over dezelfde vrienden als de eerste keer en dit proces blijf je herhalen. Zo kom je dichter bij de exacte oplossing die je weliswaar maar zal bereiken na oneindig veel stappen, maar praktisch heeft PageRank slechts een vijftigtal stappen nodig om een voldoende goede benadering te vinden die toelaat alle pagina’s te sorteren.

Het algoritme kan wiskundig eenvoudig worden neergeschreven. Stel dat H de tabel is met vijf rijen en vijf kolommen waarin op rij A vermeld staat hoeveel pagina A van haar stem toekent aan elk van de vijf mogelijke pagina’s. Dat is voor elke outlink evenveel, dus een derde omdat er drie outlinks zijn. De pagina’s waar niet naar gelinkt wordt, krijgen een 0 analoog aan de andere pagina’s. Pagina L heeft geen outlinks en de hele rij L is daarom 0. We noemen het een bengelende pagina. De tabel H is als de tabel S op de figuur, maar met nullen op de rij L. Lees je de tabel per kolom, dan staat bijvoorbeeld in kolom U hoeveel pagina U ontvangt van elk van de andere pagina’s via haar inlinks. De tabel H beschrijft de regels voor herverdeling. Met α = 0.85 geven we aan hoe na herverdeling wordt. Na oneindig veel stappen is er geen verbetering meer mogelijk en dan is π = πH. Een dergelijk probleem noemt men een eigenwaardeprobleem en π is een eigenvector. Dit is een wiskundige term die uit het Duits komt en voor het eerst werd gebruikt door David Hilbert in 1904. Hij heeft dus niets te maken met het feit dat een pagina haar eigen waarde zou kunnen bepalen. Eigenwaardeproblemen krijg je als iets op een veelvoud van zichzelf wordt afgebeeld. Een televisietoestel gefilmd door een televisiecamera wordt door de televisiezender gecapteerd en weer naar het scherm gestuurd. Dan zie je op het scherm een toestel met op het scherm een toestel … (het zogenaamde droste-effect). Als het toestel in het beeld maar half zo groot is als het gefilmde toestel is dit een eigenwaardeprobleem met eigenwaarde 0.5. Als de camera precies het beeldscherm filmt, is het uitgezonden beeld gelijk aan wat er gecapteerd wordt en is de eigenwaarde 1. Andere voorbeelden zijn: als je een microfoon voor een luidspreker houdt, zal de versterker de eigenfrequenties versterken (eigenwaarde groter dan 1) met onaangename fluittonen als gevolg. Ook gebouwen hebben eigenfrequenties, waardoor de trillingen van een aardebeving sommige gebouwen doen instorten en andere gebouwen met andere eigenfrequenties die er vlak naast liggen de schok bijna ongeschonden overleven.

Bengelende pagina’s vormen echter een praktisch probleem voor het PageRank-algoritme. Laten we veronderstellen dat een surfer domweg van pagina naar pagina springt door op elke pagina lukraak een outlink aan te klikken. Dit model noemt men in de wiskunde een dronkenmanswandeling. Dit lukraak surfen kan doorgaan tot hij op een bengelende pagina terechtkomt. Omdat hij geen uitweg ziet, stuurt hij de boodschap ‘Beam me up Scotty’ en zap! hij wordt lukraak geteleporteerd naar een willekeurige pagina van het web. De kans dat de surfer zich na k stappen op een bepaalde pagina zal bevinden, wordt weergegeven door de rij getalletjes en een surfstap later door . Het verband is waarbij S hetzelfde is als de tabel H maar de nulrij L is vervangen door een rij met waarden 1/5: er kan van L met gelijke kans naar om het even welke pagina worden gezapt. De bengelende pagina en de berekeningsproblemen zijn verdwenen. Het vraagstuk heeft nu een unieke oplossing die bestaat uit positieve getalletjes waarvan de som één is en de methode om ze te berekenen werkt. PageRank gaat nog één stapje verder. Als de surfer op een niet-bengelende pagina aankomt, is er de keuze tussen ofwel met een zekere waarschijnlijkheid verder te surfen via de outlinks of om te worden geteleporteerd naar een willekeurige pagina. De tabel S wordt dan vervangen door een nieuwe tabel G = αs + (1-α)E waarbij E de teleportatiematrix is. In ons minivoorbeeld is E een tabel helemaal opgevuld met de waarden 1/5, omdat alle sprongen even waarschijnlijk zijn, maar men zou dat eventueel kunnen personaliseren. De dronken surfer kan bijvoorbeeld een voorkeur hebben om naar websites van oenologische verenigingen te zappen. En hiermee zijn we tot de E = mc^2 gekomen van de webzoekmachines: π = π(αS + (1-α)E). Google kiest α = 0.85.

Als je ‘miserable failure’ intikte, bood Google je als belangrijkste pagina de webstek van George W. Bush aan

Een voordeel van dit PageRank-algoritme is dat het een rangschikking geeft van alle webpagina’s, onafhankelijk van de zoektermen die je intikt. Dit in tegenstelling tot bijvoorbeeld HITS (Hypertext Induced Topic Search), ook in 1998 geconcipieerd door Jon Kleinberg. Omdat het web voortdurend verandert, moet de PageRank voor de ongeveer zes miljard websites regelmatig worden herberekend. Webrobots zijn constant in de weer met het uitzenden van spinnen die het web afsnuffelen om de wijzigingen op te sporen. De informatie wordt opgeslagen en geïndexeerd zodat pagina’s relevant voor een vraag van een ‘gebruiker’ gemakkelijk kunnen worden gevonden. Google heeft steeds een tamelijk open politiek gevoerd en zo kan je de maandelijkse herberekening van de PageRank volgen op het web. Je krijgt de PageRank van een pagina te zien op drie verschillende servers. Waarschijnlijk is één ervan operationeel terwijl op de andere twee de herberekening gebeurt. Eenmaal voltooid wordt de nieuwe PageRank operationeel. Tijdens die berekeningen zie je de PageRank op en neer springen, wat gekend is als de Googledans. Ondanks het eenvoudige wiskundige principe blijft het maandelijkse (her)berekenen van de PageRank voor miljarden pagina’s een technologisch hoogstandje: een knap staaltje van software-engineering en wiskundige ingenieurstechnieken is nodig alleen al omdat je de Googlematrix $G$ maar in stukjes in de computer kan binnenhalen. Alle beschikbare rekenkracht wordt ingezet en de computers lopen warm. Eén van de redenen waarom Google in Ghlin-Baudour 250 miljoen wil investeren, is de nabijheid van water om de computers te koelen.


Zoek op het trefwoord ‘google’ en je krijgt meer dan 1 miljard pagina’s (op 18 mei 2007)

De Googledans wordt vol spanning gevolgd door firma’s die webpagina’s van hun klanten zo hoog mogelijk geklasseerd willen zien. Ze kunnen bijvoorbeeld linkmelkerijen (link farms) opzetten. Dat is een verzameling pagina’s die naar elkaar verwijzen om daardoor hun PageRank op te drijven. Dit is een vorm van spam, een probleem waar alle zoekmachines en niet alleen Google mee te maken hebben. Een andere manier om Google om de tuin te leiden is de Googlebom. De eerste Googlebom werd gelanceerd in 2001 door Adam Mathes, een student computerwetenschappen in Stanford. Een van de bekendste bommen is de ‘miserable failure’-bom. Als je die zoekterm intikte, bood Google je als belangrijkste pagina de webstek van George W. Bush aan. Het principe is eenvoudig. Om dit effect te bekomen moet je aan vrienden vragen op hun pagina’s een link te leggen naar de Bushwebstek met als verwijzende tekst ‘miserable failure’. Linkanalysesystemen zoals TrustRank van Yahoo! zijn speciaal ontworpen om relevante pagina’s van spam te onderscheiden. Natuurlijk is PageRank niet het enige systeem en zijn linkanalyse, datamining en aanverwante domeinen in volle ontwikkeling. Toepassingen zijn er overal waar gezocht wordt naar een naald in een hooiberg: bibliotheeksystemen, bibliometrie, bio-informatica, … en we exploreren nog maar het topje van de hooiberg.

Amy N. Langville, Carl D. Meyer, Google’s PageRank and Beyond: The Science of Search Engine Rankings (Princeton: Princeton University Press 2006).

Adhemar Bultheel is als toegepast wiskundige verbonden aan de KU Leuven.

Deel dit artikel
Gerelateerde artikelen