Tidigare idag delade Majestics Dixon Jones på Twitter en omfattande och lättsmält förklaring av hur PageRank faktiskt fungerar.
Jag gav den en klocka själv och tyckte att det var ett bra tillfälle att återbesöka detta vilda stycke matematik som har tagit världen med storm de senaste 20 åren.
Som en sidoanteckning vet vi från 2017 att medan PageRank togs bort från Google Verktygsfält 2016, utgör fortfarande en viktig del av den övergripande rankningsalgoritmen, och det är därför det är värt att förstå.
Jones börjar med den enkla formeln, eller åtminstone enkla.
För dem som inte älskar matematik, eller som kanske har glömt några tekniska termer sedan förra kalkylkursen, skulle den här formeln läsas högt så här:
“PageRank för en sida i denna iteration är lika med 1 minus en dämpningsfaktor, plus, för varje länk till sidan (förutom länkar till sig själv), lägg till sidrankningen för den sidan delat med antalet länkar som utskjuter på sidan och reduceras med dämpningsfaktorn.”
Återgå till det ursprungliga Google-dokumentet
Vid det här laget flyttar Jones videon mot en enklare, mer användbar version av beräkningen. Ta ut Excel, en enkel visualisering med 5 noder, och rita upp sorteringsalgoritmen i 15 iterationer. Bra sak.
Personligen ville jag ha lite mer matematik, så jag gick tillbaka och läste den fullständiga versionen av “Anatomin hos en storskalig hypertextwebbsökmotor”(Ett naturligt första steg). Detta var artikeln som skrevs av Larry Page och Sergey Brin 1997. Även känd som artikeln där de introducerade Google, publicerad på Institutionen för datavetenskap i Stanford. (Ja, det är långt och jag kommer att jobba lite sent ikväll. Allt roligt!)
Hur är det här för en öppningsrad?I den här artikeln presenterar vi Google, en storskalig sökmotorprototyp som intensivt använder strukturen som finns i hypertext.“
Informell, enligt dess allmänna och kontinuerliga stil.
Som ett extra roligt faktum, vår egen Search Engine Watch citerades i den Google-presentationsartikeln! Av ingen mindre än Page och Brin, uppger att 100 miljoner webbdokument redan fanns i november 1997.
Hur som helst, tillbaka till jobbet.
Så här definierades PageRank-beräkningen ursprungligen:
“Akademisk citatlitteratur har applicerats på webben, till stor del genom att räkna citat eller bakåtlänkar till en viss sida. Detta ger en uppskattning av vikten eller kvaliteten på en sida. PageRank utökar denna idé genom att inte räkna länkar från alla sidor lika och normalisera med antalet länkar på en sida. PageRank definieras enligt följande:
Vi antar att sida A har sidorna T1…Tn som pekar på den (dvs. de är citattecken). Parametern d är en dämpningsfaktor som kan ställas in mellan 0 och 1. Vanligtvis sätter vi d till 0,85. Det finns mer information om d i nästa avsnitt. Även C(A) definieras som antalet länkar som lämnar sida A. PageRank för en sida A ges enligt följande:
PR (A) = (1-d) + d (PR (T1) / C (T1) +… + PR (Tn) / C (Tn))
Observera att PageRanks bildar en sannolikhetsfördelning över webbsidor, så summan av PageRanks för alla webbsidor blir en.
PageRank eller PR (A) kan beräknas med hjälp av en enkel iterativ algoritm, och motsvarar huvudegenvektorn för den normaliserade länkmatrisen för webben. Dessutom kan en PageRank för 26 miljoner webbsidor beräknas på några timmar på en medelstor arbetsstation. Det finns många andra detaljer som ligger utanför ramen för detta dokument.”
Vad betyder det?
Stå ut med oss! Här är vår formel igen:
PR (A) = (1-d) + d (PR (T1) / C (T1) +… + PR (Tn) / C (Tn))
Observera att detta är samma som bilden ovan, förutom att fotot “förenklar” den andra delen av ekvationen genom att ersätta en versal sigma (∑), som är symbolen för en matematisk summa, d.v.s. gör denna formel för alla sidor 1 genom n och lägg sedan till dem.
Så för att beräkna PageRank för den givna sidan A tar vi först 1 minus dämpningsfaktorn (d). D är normalt inställt på .85, som framgår av ditt originaldokument.
Vi tar sedan PageRanks för alla sidor som pekar till och från sida A, lägger ihop dem och multiplicerar med dämpningsfaktorn 0,85.
Det är inte så illa, eller hur? Lättare sagt än gjort.
PageRank är en iterativ algoritm
Dina ögon kanske blixtrade över den här delen, men Brin och Sergey använde faktiskt ordet “egenvektor” i sin definition. Jag var tvungen att leta upp det.
Tydligen spelar egenvektorer en framträdande roll i differentialekvationer. Prefixet “eigen” kommer från tyskan för “egen” eller “egenskap”. Det finns också egenvärden och egenekvationer.
Som Rogers påpekade i sin klassiska artikel om PageRank, är det viktigaste för oss med egenvektorbiten att det är en typ av matematik som låter dig arbeta med flera rörliga delar. “Vi kan gå vidare och beräkna PageRank för en sida utan att veta det slutliga PR-värdet på de andra sidorna. Det verkar konstigt men i princip varje gång vi kör beräkningen får vi en närmare uppskattning av det slutliga värdet. Så allt vi behöver göra är att komma ihåg varje värde vi beräknade och upprepa beräkningarna många gånger tills siffrorna slutar förändras mycket.”
Eller med andra ord Vikten av egenvektorn är att PageRank är en iterativ algoritm. Ju fler gånger du upprepar beräkningen, desto närmare kommer du de mest exakta siffrorna.
PageRank visas i Excel
I sin video kommer Jones direkt till den roliga delen, varför den är så effektiv på bara 18 minuter. Demonstrerar hur PageRank beräknas med exemplet med 5 webbplatser som länkar till varandra.
Sedan återgår den till beräkningarna i Excel:
Och demonstrera hur du skulle iterera genom att ta raden med siffror längst ner och upprepa beräkningen.
Genom att göra detta, siffrorna börjar så småningom jämna ut sig (detta var efter bara 15 iterationer):
Eller som vissa kanske kallar det här fotot, “Självvektorer i naturen.”
Andra intressanta observationer som Jones tar upp:
- Antal länkar (endast totala antal) är ett dåligt mått. Vi måste bry oss mer om rankningen av varje sida.
- Det är rankingen i sidnivån som räknas, inte domänmyndigheten. PageRank tittade bara på enskilda sidor.
- De flesta sidor har knappt någon rankning. I ditt exempel representerade topp 3 av 10 75-80 % av den totala rankingen.
Så äntligen, här är den ursprungliga tweeten som ledde mig ner i detta långa och fascinerande kaninhål. Jag hoppas att du gillar detsamma!
Här har du. Hur PageRank VERKLIGEN fungerar https://t.co/OO7J0KChsr cc @RyanJones och @JosephKlok och alla andra som vill retweeta.
– Dixon (@Dixon_Jones) 25 oktober 2018
