211service.com
Wetenschapper vindt PageRank-type algoritme uit de jaren 40
Het PageRank-algoritme is een belangrijk onderdeel van Google's methode om webpagina's in zoekresultaten te rangschikken. Het gebruikt het netwerk van links tussen webpagina's om hun waarde te bepalen en, zoals bekend, beoordeelt een pagina als belangrijk als er door andere belangrijke pagina's naar wordt gelinkt.
Een cruciaal kenmerk van dit idee is dat het een iteratieve benadering vereist om de waarde van een pagina voortdurend opnieuw te evalueren, aangezien het belang van andere varieert. Iteratieve rangschikkingsalgoritmen zijn sindsdien een belangrijk onderdeel geworden van de netwerktheorie.
PageRank werd in 1998 ontwikkeld door de oprichters van Google, Sergey Brin en Larry Page, en de impact was zo groot dat je gemakkelijk vergeet dat de aanpak niet helemaal nieuw was. Massimo Franceschet van de Universiteit van Udine in Italië wijst erop dat het idee een aantal keren met succes is uitgebuit in de 20e-eeuwse wetenschap, zelfs voordat Brin en Page werden geboren. Vandaag presenteert hij een korte geschiedenis van iteratieve rangschikkingsalgoritmen en brengt hij hun evolutie in kaart vóór de opkomst van Google.
Hij begint in omgekeerde chronologische volgorde met het werk van Jon Kleinberg, een computerwetenschapper aan de Cornell University, die een paar jaar eerder een bijna identieke benadering van PageRank ontwikkelde. Brin en Page verwijzen zelfs naar zijn werk in hun beroemde paper waarin PageRank wordt geïntroduceerd.
Kleinberg noemde zijn algoritme Hypertext Induced Topic Search of HITS en behandelde webpagina's als hubs en autoriteiten. Het gebruikte de circulaire definitie dat autoriteiten pagina's zijn waarnaar wordt verwezen door hubs en hubs zijn pagina's die verwijzen naar autoriteiten en vereisen een iteratieve aanpak om op te lossen.
In de onstuimige dagen van de dotcom-boom in de late 20e eeuw, voordat Google zo succesvol werd, kreeg Kleinbergs werk veel media-aandacht.
Franceschet onderzoekt ook het werk van Gabriel Pinski en Francis Narin, die een manier hebben ontwikkeld om tijdschriften te rangschikken. Hun regel was dat een tijdschrift belangrijk is als het wordt geciteerd door andere belangrijke tijdschriften. Net als PageRank en HITS vereist dit een iteratieve methode om de structuur van koppelingen tussen tijdschriften te benutten om tot een ranking te komen.
Lang daarvoor analyseerde Charles H Hubbell van de Universiteit van Califronia, Santa Barbara, sociale netwerken op een vergelijkbare manier. In 1965 publiceerde hij een techniek om het belang van individuen te bepalen op basis van het belang van de mensen die hen onderschrijven. Dit heeft weer de karakteristieke circulaire definitie en iteratieve oplossing. Hubbell wordt door velen, waaronder Kleinberg, erkend als een pionier in iteratieve rangschikkingstheorie.
Maar de grote verrassing is Franceschets ontdekking van een nog eerdere voorloper van PageRank in het werk van de Harvard-econoom Wassily Leontief. In 1941 publiceerde Leontief een paper waarin hij de economie van een land opdeelt in sectoren die zowel middelen leveren als van elkaar ontvangen, hoewel niet in gelijke mate. Een belangrijke vraag is: wat is de waarde van elke sector als ze zo nauw geïntegreerd zijn? Het antwoord van Leontief was om een iteratieve methode te ontwikkelen om elke sector te waarderen op basis van het belang van de sectoren die eraan leveren. Klinkt bekend? In 1973 kreeg Leontief voor dit werk de Nobelprijs voor de economie.
Wat duidelijk is, is dat de ideeën achter PageRank een eerbiedwaardige geschiedenis hebben, maar de verrassing is dat ze dateren uit ten minste de jaren veertig. Het zal interessant zijn om te zien of iemand soortgelijk werk kan vinden dat dateert van vóór dit.
Referentie: arxiv.org/abs/1002.2858 : PageRank: Sta op de schouders van reuzen