Forsker finder PageRank-Type Algorithm fra 1940'erne

PageRank-algoritmen er en vigtig del af Googles metode til at rangere websider i søgeresultaterne. Det bruger netværket af links mellem websider til at bestemme deres værdi og, berømt, vurderer en side som vigtig, hvis den er linket til af andre vigtige sider.

Et afgørende træk ved denne idé er, at det kræver en iterativ tilgang til konstant at revurdere værdien af ​​en side, da betydningen af ​​andre varierer. Iterative ranking-algoritmer er siden blevet en vigtig del af netværksteorien.

PageRank blev udviklet i 1998 af Googles grundlæggere Sergey Brin og Larry Page, og dens virkning har været sådan, at det er let at glemme, at tilgangen ikke var helt ny. Massimo Franceschet ved universitetet i Udine i Italien påpeger, at ideen er blevet udnyttet med succes en række gange i det 20. århundredes videnskab, selv før Brin og Page blev født. I dag præsenterer han en kort historie om iterative rangordningsalgoritmer og kortlægger deres udvikling forud for Googles fremkomst.

Han begynder i omvendt kronologisk rækkefølge med arbejdet af Jon Kleinberg, en datalog ved Cornell University, som udviklede en næsten identisk tilgang til PageRank, blot et par år tidligere. Brin og Page refererer endda til hans arbejde i deres berømte papir, der introducerer PageRank.

Kleinberg kaldte sin algoritme Hypertext Induced Topic Search eller HITS, og den behandlede websider som hubs og myndigheder. Den brugte den cirkulære definition, at autoriteter er sider, der peges på af hubs, og hubs er sider, der peger på autoriteter og kræver en iterativ tilgang til at løse.

I de berusende dage med dotcom-boomet i slutningen af ​​det 20. århundrede, før Google blev så succesfuld, fik Kleinbergs arbejde betydelig mediedækning.

Franceschet undersøger også Gabriel Pinskis og Francis Narins arbejde, som udviklede en måde at rangordne tidsskrifter på. Deres regel var, at et tidsskrift er vigtigt, hvis det er citeret af andre vigtige tidsskrifter. Ligesom PageRank og HITS kræver dette en iterativ metode til at udnytte strukturen af ​​links mellem tidsskrifter til at komme frem til en rangering.

Længe før dette analyserede Charles H Hubbell ved University of Califronia, Santa Barbara, sociale netværk på en lignende måde. I 1965 udgav han en teknik til at bestemme betydningen af ​​individer baseret på vigtigheden af ​​de mennesker, der støtter dem. Dette har igen den karakteristiske cirkulære definition og iterative løsning. Hubbell er anerkendt af mange, herunder Kleinberg som en pioner inden for iterativ rangordningsteori.

Men den store overraskelse er Franceschets opdagelse af en endnu tidligere forløber for PageRank i Harvard-økonomens Wassily Leontiefs arbejde. I 1941 udgav Leontief et papir, hvori han opdeler et lands økonomi i sektorer, der både leverer og modtager ressourcer fra hinanden, dog ikke i lige stor grad. Et vigtigt spørgsmål er: hvad er værdien af ​​hver sektor, når de er så tæt integreret? Leontiefs svar var at udvikle en iterativ metode til at værdiansætte hver sektor baseret på vigtigheden af ​​de sektorer, der leverer den. Lyder det bekendt? I 1973 blev Leontief tildelt Nobelprisen i økonomi for dette arbejde.

Det, der er klart, er, at ideerne bag PageRank har en ærværdig historie, men overraskelsen er, at de i det mindste går tilbage til 1940'erne. Det bliver interessant at se, om nogen kan finde noget lignende arbejde, der går forud for dette.

Ref: arxiv.org/abs/1002.2858 : PageRank: Stand On The Shoulders Of Giants

skjule