Google’s PageRank-algoritme, uitgelegd

5 min


95

Eerder vandaag deelde Dixon Jones van Majestic  op Twitter  een grondige, begrijpelijke uitleg over hoe PageRank eigenlijk werkt. 

Ik heb het zelf bekeken en vond het een goed moment om dit wilde stukje wiskunde opnieuw te bekijken dat de afgelopen 20 jaar behoorlijk deuk heeft gemaakt in de wereld.

Als een sidenote weten we vanaf 2017 dat terwijl PageRank in 2016 werd verwijderd van de Toolbar, het nog steeds een belangrijk onderdeel vormt van het algehele ranking-algoritme  en daarom de moeite waard is om te begrijpen.

Jones begint met de eenvoudige – of in elk geval ongecompliceerde – formule.

pagerank-algoritme

Voor diegenen die niet van wiskunde houden, of die misschien een paar technische termen zijn vergeten sinds de laatste calculusklasse, zou deze formule als volgt voorgelezen worden:

“De PageRank van een pagina in deze iteratie staat gelijk aan 1 minus een dempingsfactor plus voor elke link naar de pagina (behalve links naar zichzelf), voeg de paginarang van die pagina toe, gedeeld door het aantal uitgaande links op de pagina en verminderd door de dempingsfactor. “

Terug naar het originele Google-document

Op dit punt gaat Jones in de video verder naar een eenvoudiger, nog steeds bruikbare versie van de berekening. Hij haalt uit, een gemakkelijke 5-knoops visualisatie en brengt het ranking-algoritme in kaart boven 15 iteraties. Goed spul.

Persoonlijk wilde ik iets meer van de wiskunde, dus ging ik terug en las de volledige versie van ” De anatomie van een grootschalige hypertextuele zoekmachine voor het web ” (een natuurlijke eerste stap). Dit was het papier geschreven door Larry Page en Sergey Brin in 1997. Aka het document waarin ze Google presenteerden , gepubliceerd op de Stanford Computer Science Department. (Ja, het is lang en ik zal vanavond een beetje laat werken. Allemaal leuk!)

Hoe is dit voor een openingszin: ” In dit artikel presenteren we Google , een prototype van een grootschalige zoekmachine die veel gebruik maakt van de structuur die in hypertekst aanwezig is. 

Casual, per hun algemene, doorlopende stijl.

Als een extra leuk feit, werd ons eigen Zoekmachinehorloge geciteerd in dat Google-debuut! Door niemand anders dan Page en Brin zelf, die verklaarden dat er al in november 1997 al 100 miljoen webdocumenten waren.

Hoe dan ook, weer aan het werk.

Zo werd de PageRank-berekening oorspronkelijk gedefinieerd:

“Academische bronvermelding is op het web toegepast, grotendeels door citaties of backlinks naar een bepaalde pagina te tellen. Dit geeft enige benadering van het belang of de kwaliteit van een pagina. PageRank breidt dit idee uit door links van alle pagina’s even niet mee te tellen en door te normaliseren op basis van het aantal links op een pagina. PageRank is als volgt gedefinieerd:

We gaan ervan uit dat pagina A pagina’s T1 … Tn heeft die erop wijzen (dwz citaten zijn). De parameter d is een dempingsfactor die kan worden ingesteld tussen 0 en 1. Gewoonlijk stellen we d in op 0,85. Er zijn meer details over d in de volgende sectie. C (A) wordt ook gedefinieerd als het aantal links dat van pagina A uitgaat. De PageRank van een pagina A wordt als volgt gegeven:

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

Merk op dat de PageRanks een kansverdeling vormen over webpagina’s, dus de som van de PageRanks van alle webpagina’s zal een zijn.

PageRank of  PR (A)  kan worden berekend met behulp van een eenvoudig iteratief algoritme en komt overeen met de belangrijkste eigenvector van de genormaliseerde koppelingsmatrix van het web. Ook kan een PageRank voor 26 miljoen webpagina’s binnen een paar uur worden berekend op een werkstation van gemiddelde grootte. Er zijn veel andere details die buiten het bestek van dit document vallen. “

Wat betekent dat?

Draag bij ons! Dit is onze formule opnieuw:

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

Merk op dat dit hetzelfde is als de bovenstaande afbeelding, behalve dat de foto het tweede deel van de vergelijking “vereenvoudigt” door een hoofdletter sigma (Σ) te vervangen, wat het symbool is voor een wiskundige optelling, dwz doe deze formule voor alle pagina’s 1 door n en voeg ze vervolgens toe.

Dus om de PageRank van gegeven pagina A te berekenen, nemen we eerst 1 min de dempingsfactor (d). D is meestal ingesteld als .85, zoals te zien in hun originele papier.

Vervolgens nemen we de PageRanks van alle pagina’s die naar en van pagina A verwijzen, voegen deze toe en vermenigvuldigen zich met de dempingsfactor van 0,85.

Niet zo slecht, toch? Makkelijker gezegd dan gedaan.

PageRank is een iteratief algoritme

Misschien hebben je ogen over dit deel geglazuurd, maar Brin en Sergey hebben het woord ‘eigenvector’ in hun definitie gebruikt. Ik moest het opzoeken.

Blijkbaar spelen eigenvectoren een prominente rol in differentiaalvergelijkingen. Het voorvoegsel “eigen” komt uit het Duits voor “juist” of “kenmerkend”. Er bestaan ​​ook eigenwaarden en eigenvergelijkingen.

Zoals Rogers  in zijn klassieke paper over PageRank aangaf , is de grootste afhaalmogelijkheid voor ons over het eigenvector-stuk dat het een soort wiskunde is waarmee je met meerdere bewegende delen kunt werken. “We kunnen doorgaan en de PageRank van een pagina berekenen  zonder de uiteindelijke waarde van de PR van de andere pagina’s te kennen . Dat lijkt vreemd, maar in principe krijgen we elke keer dat we de berekening uitvoeren een nadere schatting van de uiteindelijke waarde. Dus alles wat we moeten doen is de waarde die we berekenen onthouden en de berekeningen vele malen herhalen totdat de cijfers niet veel veranderen. “

Of met andere woorden, het belang van de eigenvector is dat PageRank een iteratief algoritme is . Hoe vaker u de berekening herhaalt, hoe dichter u bij de nauwkeurigste cijfers komt.

PageRank gevisualiseerd in Excel

In zijn video krijgt Jones vrijwel direct het leuke gedeelte, daarom is het zo effectief in slechts 18 minuten. Hij laat zien hoe PageRank wordt berekend met het voorbeeld van 5 websites die van en naar elkaar linken.

Hij brengt het vervolgens weer terug naar de berekeningen in Excel:

En laat zien hoe je zou itereren door de rij met getallen onderaan te nemen en de berekening te herhalen.

Als je dit doet, beginnen de getallen uiteindelijk te egaliseren (dit was na slechts 15 iteraties):

Of zoals sommigen misschien deze foto onderschrijven, “Eigenvectors in the Wild.”

Andere interessante observaties die Jones opwerpt:

  1. Verbindingsaantallen (alleen totale getallen) zijn een slechte statistiek. We moeten meer geven om de rang van elke pagina.
  2. Het is de rangorde op paginaniveau die telt, niet de domeinautoriteit . PageRank heeft alleen naar afzonderlijke pagina’s gekeken.
  3. De meerderheid van de pagina’s heeft nauwelijks enige rang. In zijn voorbeeld was de top 3 van de 10 goed voor 75-80% van het totale klassement.

Dus eindelijk, hier is de originele tweet die me door dit lange, meeslepende konijnenhol heen heeft gehaald. Ik hoop dat jullie allemaal hetzelfde zullen genieten!

Dixon@Dixon_Jones

Here you go. How PageRank REALLY works https://blog.majestic.com/company/understanding-googles-algorithm-how-pagerank-works/  cc @RyanJones and @JosephKlok & anyone else willing to retweet.

How PageRank Really Works: Understanding Google –

Understanding the inner workings of Google’s PageRank can be quite difficult so how did SEO’s figure it out? Here’s how to understand Google’s algorithm.

blog.majestic.com

99 people are talking about this

Erwin@delaatbusiness.com
Dag, Hulp nodig met internet marketing of websites maken? neem dan contact op

0 Comments

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *

Choose A Format
Personality quiz
Series of questions that intends to reveal something about the personality
Trivia quiz
Series of questions with right and wrong answers that intends to check knowledge
Poll
Voting to make decisions or determine opinions
Story
Formatted Text with Embeds and Visuals
List
The Classic Internet Listicles
Countdown
The Classic Internet Countdowns
Open List
Submit your own item and vote up for the best submission
Ranked List
Upvote or downvote to decide the best list item
Meme
Upload your own images to make custom memes
Video
Youtube, Vimeo or Vine Embeds
Audio
Soundcloud or Mixcloud Embeds
Image
Photo or GIF
Gif
GIF format