Googles PageRank-algoritme

Komplett matematisk guide til Googles grunnleggende algoritme for lenkeanalyse

Henrik Bondtofte
20 min lesetid
Matematisk guide
Illustrasjon av Googles PageRank-algoritme
PR(A) = (1-d) + d × Σ(PR(Ti)/C(Ti))

Innholdsfortegnelse

Hva er PageRank?

PageRank er navnet på algoritmen for lenkeanalyse som ble oppfunnet av Sergey Brin og Larry (Lawrence) Page ved Stanford University, og samtidig formelen som la grunnlaget for at Google ble etablert.

Mange tror feilaktig at PageRank ikke lenger er en del av Googles algoritmer. Det er viktig å forstå at PageRank er en av bærebjelkene hos Google og en helt sentral del av søkemotoren.

Enkelt sagt går formelen ut på å tildele tallverdier til hyperlenker for å måle hvor viktig en side er sammenlignet med andre. Med andre ord er PageRank en popularitetsalgoritme basert på siteringsanalyse.

Opphavet til navnet

Det var Larry selv som ga formelen navn, og derav navnet PageRank. Den heter ikke PageRank fordi verdien dekker et helt nettsted. PageRank akkumuleres på alle sidene på et nettsted som Google har tilgang til, ikke på domenenivå.

Vanlig misforståelse

PageRank beregnes på sidenivå, og det betyr at noe slikt som et PageRank-4-domene ikke finnes. Det ville hete et nettsted med en forside som har en PageRank på 4, og det er ikke domenet i seg selv.

Historien om PageRank

1996

Oppfinnelsen

Larry Page og Sergey Brin utvikler BackRub, som senere ble Google, ved Stanford University

Første versjon av PageRank-algoritmen, basert på siteringsanalyse

1998

Patentsøknaden

Stanford University søker patent på PageRank-algoritmen

Patentet US6285999B1 beskriver den matematiske algoritmen i detalj

1998-2000

Google grunnlegges

Google Inc. blir grunnlagt med PageRank som kjernealgoritme

PageRank blir den viktigste rangeringsfaktoren for søkeresultatene

2000-2013

PageRank i verktøylinjen

Google Toolbar viser offentlige PageRank-verdier på en skala fra 0 til 10

Nettredaktører kan se PageRank-scoren til sidene sine i Google Toolbar

2013

Verktøylinjen legges ned

Google slutter å oppdatere de offentlige PageRank-verdiene

PageRank blir et internt Google-verktøy uten offentlig innsyn

2016+

Moderne implementering

PageRank integreres med hundrevis av andre rangeringssignaler

Fortsatt grunnleggende for Google, men kombinert med maskinlæring

Den opprinnelige PageRank-formelen

Grunnformelen for PageRank

PR(A) = (1-d) + d × Σ(PR(Ti)/C(Ti))

PR(A) = PageRank for side A

d = dempingsfaktoren (som regel 0.85)

PR(Ti) = PageRank for side Ti, som lenker til A

C(Ti) = antall utgående lenker fra side Ti

Forenklet versjon

I sin opprinnelige form fordeler formelen vekten likt mellom lenkene som finnes på en side, uansett om det er interne eller eksterne lenker.

Verdi = PageRank + (PageRank fra kilder × 0.85) / antall lenker

Praktisk eksempel

Har du for eksempel 10 utgående lenker på en side, overfører hver lenke 10 % av PageRank-verdien du har mulighet til å gi videre.

PageRank ÷ 10 lenker = 10 % per lenke

Matematisk analyse

Matriserepresentasjon

PageRank kan beregnes med matrisealgebra, der nettet representeres som en overgangsmatrise M:

M = d × H + (1-d)/N × J

Der:
H = Lenkematrise (hij = 1/L(j) hvis j lenker til i, ellers 0)
J = Matrise der alle elementer er 1
N = Antall sider
d = Dempingsfaktor

Beregning av egenvektor

PageRank-vektoren er den dominerende egenvektoren til overgangsmatrisen M:

π = M × π

Der π er PageRank-vektoren og M er overgangsmatrisen

Konvergenskriterium

Algoritmen konvergerer når forskjellen mellom iterasjonene er tilstrekkelig liten:

||π(k+1) - π(k)|| < ε

Der ε som regel er 10⁻⁶ for å oppnå høy presisjon

Dempingsfaktoren (0.85)

Hva er dempingsfaktoren?

Dempingsfaktoren (d = 0.85) uttrykker sannsynligheten for at en bruker fortsetter å klikke på lenker i stedet for å starte et nytt søk. Med andre ord er det 85 % sjanse for at brukeren følger en lenke, og 15 % sjanse for et hopp til en tilfeldig side.

Med dempingsfaktor (d = 0.85)

  • ✓ Hindrer manipulasjon av rangeringene
  • ✓ Håndterer blindveier (sider uten utgående lenker)
  • ✓ Sikrer at algoritmen konvergerer
  • ✓ Modellerer realistisk brukeratferd

Uten dempingsfaktor (d = 1.0)

  • ✗ Rangeringssluk (sider som samler opp all PageRank)
  • ✗ Algoritmen konvergerer ikke alltid
  • ✗ Mer sårbar for manipulasjon
  • ✗ Urealistisk brukermodell

Den matematiske betydningen av dempingsfaktoren

15%
Tilfeldig hopp
(1-d)-leddet
85%
Følger en lenke
d × lenkeleddet
~100
Iterasjoner
før konvergens

Den iterative beregningsprosessen

PageRank beregnes iterativt, og hver iterasjon forbedrer anslaget for PageRank-verdiene til alle sidene:

Den iterative algoritmen

1. Initialiser: PR⁰(i) = 1/N for alle sider i
2. For k = 0, 1, 2, ... til konvergens:
   PR^(k+1)(i) = (1-d)/N + d × Σ(PR^k(j)/L(j))
   der j lenker til i
3. Stopp når ||PR^(k+1) - PR^k|| < ε
Iterasjon 0
Startverdier
PR(i) = 1/N
Iterasjon 1-99
Konvergensprosessen
Gradvis stabilisering
Iterasjon 100+
Konvergens
Stabile verdier

Matrisebasert beregning

Eksempel på nabomatrise

For et enkelt nettverk med fire sider kan vi representere lenkestrukturen som en matrise:

     A    B    C    D
A  [ 0   1/2  1/2   0 ]
B  [1/3   0   1/3  1/3]
C  [1/2   0    0   1/2]
D  [ 0    1    0    0 ]

Matrise H (overgangsmatrise for lenker)

Slik bygges Google-matrisen

G = d × H + (1-d)/N × J

Der J er matrisen med verdien 1/N i hvert element:
     A     B     C     D
A  [0.25  0.25  0.25  0.25]
B  [0.25  0.25  0.25  0.25]
C  [0.25  0.25  0.25  0.25]
D  [0.25  0.25  0.25  0.25]

Den ferdige Google-matrisen (d=0.85)

       A      B      C      D
A  [0.0375  0.4625  0.4625  0.0375]
B  [0.3208  0.0375  0.3208  0.3208]
C  [0.4625  0.0375  0.0375  0.4625]
D  [0.0375  0.8875  0.0375  0.0375]

Visualisering av nettverket

Interaktivt PageRank-nettverk

APR: 2.5BPR: 1.8CPR: 3.2DPR: 1.9

Forklaring til visualiseringen

  • Størrelsen på noden: viser PageRank-verdien
  • Pilene: viser hvilken vei lenken går
  • Animasjonen: simulerer flyten av PageRank
  • Fargene: blått er normalt, lilla er aktiv iterasjon

Praktiske regneeksempler

Interaktiv PageRank-kalkulator

Beregning:

PR(A) = (1-d) + d × (PR(B)/L(B))

PR(A) = (1-0.85) + 0.85 × (5/10)

PR(A) = 0.150 + 0.425

PR(A) = 0.575

Eksempel 1: enkel beregning

Side A får en lenke fra side B, som har PageRank 5.0

Side B har 10 utgående lenker

PR(A) = 0.15 + 0.85 × (5.0/10) = 0.15 + 0.425 = 0.575

Eksempel 2: flere lenker

Side A får lenker fra side B (PR=3.0, 5 lenker) og side C (PR=2.0, 2 lenker)

PR(A) = 0.15 + 0.85 × (3.0/5 + 2.0/2) = 0.15 + 0.85 × 1.6 = 1.51

Moderne mot opprinnelig PageRank

Opprinnelig PageRank (1998-2010)

  • • Den viktigste rangeringsfaktoren
  • • Offentlig tilgjengelig via verktøylinjen
  • • Enkel algoritme basert på lenker
  • • Sårbar for manipulasjon
  • • Månedlige oppdateringer

Moderne PageRank (2010+)

  • • En av flere hundre faktorer
  • • Internt Google-verktøy
  • • Integrert med maskinlæring
  • • Forbedringer som motvirker spam
  • • Oppdateringer i sanntid

Moderne forbedringer

Personalisert PageRank:

Justert etter brukerens interesser og søkehistorikk

Tematisk PageRank:

Vekting etter temarelevans og kontekst

Integrasjon med TrustRank:

Kombinert med tillitssignaler for å beskytte mot spam

Tidsfaktorer:

Vekting av lenker over tid og signaler om ferskhet

Begrensninger og utfordringer

Manipulasjon og spam

  • • Lenkefarmer og PBN-nettverk
  • • Kunstig lenkebytte
  • • Kjøpte lenker brukt til manipulasjon
  • • Kommentarspam og forumspam

Tekniske utfordringer

  • • Beregningskompleksitet for milliarder av sider
  • • Blindveier (sider uten utgående lenker)
  • • Edderkoppfeller og uendelige løkker
  • • Å skalere til oppdateringer i sanntid

Begrensninger ved selve ideen

  • • Ser bare på lenkepopularitet, ikke på innholdet
  • • Favoriserer eldre, etablerte nettsteder
  • • Tar ikke hensyn til brukerens hensikt og kontekst
  • • Statisk modell mot et dynamisk nett

Betydningen av PageRank i dag

Fortsatt grunnleggende

PageRank er fortsatt en kjernedel av Googles algoritme, selv om den nå virker sammen med hundrevis av andre rangeringsfaktorer. Grunntanken om autoritet basert på lenker er fremdeles sentral for hvordan Google vurderer nettsider.

~200
Rangeringsfaktorer
PageRank er én av mange
25+
År i bruk
Siden 1998
Kjerne
Status
Fortsatt grunnleggende

Praktiske konsekvenser for SEO

Lenker betyr fortsatt mye:

Gode lenker fra sider med autoritet har fortsatt høy verdi

Prioriter kvalitet:

Få lenker fra relevante og troverdige kilder

Interne lenker:

Fordel PageRank strategisk på ditt eget nettsted

Helhetlig tilnærming:

Kombiner lenkebygging med innhold og teknisk SEO

Vil du mestre moderne lenkebygging?

Nå som du forstår den matematiske bakgrunnen for PageRank, kan du lære å bruke kunnskapen i praksis i moderne SEO og lenkebygging.

Les boken om lenkebygging