Googles PageRank-algoritme forklares

Tidligere i dag, Dixon Jones fra Majestic delt på kvidre En grundig og fordøjelig forklaring på, hvordan PageRank rent faktisk virker.

Jeg gav det selv et kig og troede, at det var et godt øjeblik at gennemgå dette vildt stykke matematik, der har gjort en smule dunk på verden i løbet af de sidste 20 år.

Som et sidebillede ved vi fra 2017 at mens PageRank blev fjernet fra værktøjslinjen i 2016, det udgør stadig en vigtig del af den overordnede rankingalgoritme, og det er således værd at forstå.

Jones starter med det enkle - eller i det mindste ligefrem - formel.

pagerankalgoritme

For dem, der ikke elsker matematik, eller som måske har glemt nogle tekniske termer siden den sidste beregningsklasse, ville denne formel blive læst højt som sådan:

"PageRank af en side i denne iteration svarer til 1 minus en dæmpningsfaktor plus, for hvert link på siden (undtagen for links til sig selv), tilføj sidens rangering af den pågældende side divideret med antallet af udgående links på siden og reduceret med dæmpningsfaktoren. "

Tilbage til det oprindelige Google-papir

På dette tidspunkt bevæger Jones fremad i videoen til en enklere, stadig nyttig version af beregningen. Han trækker ud excel, en let 5 node visuel, og kortlægger ranking algoritmen over 15 iterationer. Gode ​​sager.

Personligt ønskede jeg lidt mere af matematikken, så jeg gik tilbage og læste fuld længde versionen af ​​"Anatomien af ​​en storskaleret hypertekstlig websøgemaskine"(Et naturligt første skridt). Dette var papir skrevet af Larry Page og Sergey Brin i 1997. Aka det papir, hvori de fremlagde Google, offentliggjort i Stanford Computer Science Department. (Ja, det er langt, og jeg vil arbejde lidt sent i aften. Alt i god sjov!)

Hvordan er det for en åbningslinje: "I dette papir præsenterer vi Google, en prototype af en storstilet søgemaskine, som gør stor brug af strukturen til stede i hypertekst."

Casual, pr. Deres overordnede, fortsatte stil.

Som en ekstra sjov kendsgerning, vores helt egen Search Engine Watch blev citeret i det Google debutpapir! Af ingen anden end Page and Brin sig selv, idet det blev angivet, at der allerede var 100 millioner webdokumenter fra november 1997.

Anyway, tilbage til arbejde.

Sådan er PageRank-beregningen oprindeligt defineret:

"Akademisk citatlitteratur er blevet anvendt på internettet, stort set ved at tælle citater eller backlinks til en given side. Dette giver en vis tilnærmelse af en sides betydning eller kvalitet. PageRank udvider denne ide ved ikke at tælle links fra alle sider lige og ved normalisering af antallet af links på en side. PageRank er defineret som følger:

Vi antager, at side A har sider T1 ... Tn som peger på det (dvs. citeringer). Parameteren d er en dæmpningsfaktor, der kan indstilles mellem 0 og 1. Vi sætter normalt d til 0.85. Der er flere detaljer om d i næste afsnit. Også C (A) er defineret som antallet af links, der går ud af side A. Sidens rank på en side A er angivet som følger:

PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C (Tn))

Bemærk, at PageRanks udgør en sandsynlighedsfordeling over websider, så summen af ​​alle websider PageRanks bliver en.

PageRank eller PR (A) kan beregnes ved hjælp af en simpel iterativ algoritme og svarer til den primære egenvektor af den normaliserede linkmatrix af banen. En PageRank for 26 millioner websider kan også beregnes om et par timer på en mellemstor arbejdsstation. Der er mange andre detaljer, der ligger uden for rammerne af dette papir. "

Hvad betyder det?

Bær med os! Her er vores formel igen:

PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C (Tn))

Bemærk, at dette er det samme som ovenstående billede, bortset fra at billedet "forenkler" anden del af ligningen ved at erstatte en storcase sigma (Σ), som er symbolet for en matematisk summation, dvs. gøre denne formel for alle sider 1 gennem n og derefter tilføje dem op.

Så for at beregne PageRank for givet side A, tager vi først 1 minus dæmpningsfaktoren (d). D er typisk angivet som .85, som det ses i deres originale papir.

Vi tager så siderne af alle sider, der peger på og fra side A, tilføjer dem og multiplicerer med dæmpningsfaktoren for 0.85.

Ikke så slemt, ikke? Nemmere sagt end gjort.

PageRank er en iterativ algoritme

Måske dine øjne glaserede over denne del, men Brin og Sergey brugte faktisk ordet "egenvektor" i deres definition. Jeg måtte se det op.

Tilsyneladende spiller egenvektorer en fremtrædende rolle i differentialligninger. Prefixet "egen" kommer fra tysk til "korrekt" eller "karakteristisk." Der findes også egenværdier og egenskaber.

As Rogers påpegede i sit klassiske papir på PageRank er den største takeaway for os om egenvektorstykket, at det er en type matematik, der gør at du arbejder med flere bevægelige dele. "Vi kan gå videre og beregne en sides PageRank uden at vide den endelige værdi af PR på de andre sider. Det forekommer mærkeligt, men i det væsentlige hver gang vi kører beregningen, får vi et nærmere skøn over den endelige værdi. Så alt hvad vi skal gøre er at huske hver værdi, vi beregner, og gentag beregningerne mange gange, indtil tallene ikke længere ændres meget. "

Eller med andre ord, egenvektorens betydning er, at PageRank er en iterativ algoritme. Jo flere gange du gentager beregningen, jo tættere kommer du til de mest præcise tal.

PageRank visualiseret i Excel

I sin video, Jones bliver temmelig meget lige på den sjove del, hvorfor det er så effektivt i bare 18 minutter. Han demonstrerer, hvordan PageRank beregnes med eksemplet på 5-websites, der linker til og fra hinanden.

Han bringer det derefter tilbage til beregningerne i Excel:

Og viser hvordan du vil gentage ved at tage rækken af ​​tal nederst og gentage beregningen.

Ved dette gøres det Tallene begynder gradvist at udjævne (dette var efter blot 15 iterationer):

Eller som nogle måske billedtekster dette billede, "Eigenvectors in the Wild."

Andre interessante observationer Jones rejser:

  1. Link tæller (bare samlede tal) er en dårlig måling. Vi skal bekymre os mere om hver sides rang.
  2. Det er rangordningen på sidetal, der tæller, ikke domæneautoriteten. PageRank har kun set på enkelte sider.
  3. De fleste sider har næppe nogen rang overhovedet. I sit eksempel udgjorde den øverste 3 ud af 10 75-80% af den samlede placering.

Så endelig, her er den originale tweet, der fik mig ned i dette lange nittende kaninhul. Håber du alle nyder det samme!

Vær så god. Hvordan PageRank VIRKELIG virker https://t.co/OO7J0KChsr cc @RyanJones og @JosephKlok & nogen anden villig til at retweetes.

- Dixon (@Dixon_Jones) Oktober 25, 2018

Kilde

Efterlad en kommentar

Dette websted bruger Akismet til at reducere spam. Lær, hvordan dine kommentardata behandles.