211service.com
Forskare hittar PageRank-Type Algorithm från 1940-talet
PageRank-algoritmen är en viktig del av Googles metod för att rangordna webbsidor i sökresultat. Den använder nätverket av länkar mellan webbsidor för att bestämma deras värde och, känt nog, bedömer den en sida som viktig om den är länkad till av andra viktiga sidor.
En avgörande egenskap hos denna idé är att den kräver ett iterativt tillvägagångssätt för att ständigt omvärdera värdet av en sida eftersom betydelsen av andra varierar. Iterativa rankningsalgoritmer har sedan dess blivit en viktig del av nätverksteorin.
PageRank utvecklades 1998 av Googles grundare Sergey Brin och Larry Page och dess inverkan har varit sådan att det är lätt att glömma att tillvägagångssättet inte var helt nytt. Massimo Franceschet vid universitetet i Udine i Italien påpekar att idén framgångsrikt har utnyttjats ett antal gånger inom 1900-talets vetenskap, även innan Brin och Page föddes. Idag presenterar han en kort historia av iterativa rankningsalgoritmer och kartlägger deras utveckling före Googles uppkomst.
Han börjar i omvänd kronologisk ordning med arbetet av Jon Kleinberg, en datavetare vid Cornell University, som utvecklade ett nästan identiskt tillvägagångssätt för PageRank, bara några år tidigare. Brin och Page refererar till och med hans arbete i deras berömda papper som introducerar PageRank.
Kleinberg kallade sin algoritm Hypertext Induced Topic Search eller HITS och den behandlade webbsidor som nav och auktoriteter. Den använde den cirkulära definitionen att myndigheter är sidor som pekas på av nav och nav är sidor som pekar på myndigheter och kräver ett iterativt tillvägagångssätt för att lösa.
Under de berusande dagarna av dotcom-boomen i slutet av 1900-talet, innan Google blev så framgångsrikt, fick Kleinbergs arbete betydande mediabevakning.
Franceschet undersöker också Gabriel Pinskis och Francis Narins arbete som utvecklat ett sätt att rangordna tidskrifter. Deras regel var att en tidskrift är viktig om den citeras av andra viktiga tidskrifter. Precis som PageRank och HITS kräver detta en iterativ metod för att utnyttja strukturen av länkar mellan tidskrifter för att komma fram till en rankning.
Långt innan detta analyserade dock Charles H Hubbell vid University of Califronia, Santa Barbara, sociala nätverk på ett liknande sätt. 1965 publicerade han en teknik för att bestämma betydelsen av individer baserat på betydelsen av de människor som stöder dem. Detta har återigen den karakteristiska cirkulära definitionen och iterativa lösningen. Hubbell är erkänt av många inklusive Kleinberg som en pionjär inom iterativ rankingteori.
Men den stora överraskningen är Franceschets upptäckt av en ännu tidigare föregångare till PageRank i Harvard-ekonomen Wassily Leontiefs arbete. 1941 publicerade Leontief en artikel där han delar upp ett lands ekonomi i sektorer som både levererar och tar emot resurser från varandra, om än inte i lika stor utsträckning. En viktig fråga är: vad är värdet av varje sektor när de är så tätt integrerade? Leontiefs svar var att utveckla en iterativ metod för att värdera varje sektor baserat på betydelsen av de sektorer som levererar den. Låter bekant? 1973 tilldelades Leontief Nobelpriset i ekonomi för detta arbete.
Det som är uppenbart är att idéerna bakom PageRank har en vördnadsvärd historia men överraskningen är att de går tillbaka till åtminstone 1940-talet. Det ska bli intressant att se om någon kan hitta något liknande arbete som föregick detta.
Ref: arxiv.org/abs/1002.2858 : PageRank: Stå på jättarnas axlar