Die PageRank-Formel: so wird gerechnet

Die Formel hinter PageRank passt in eine Zeile. Was sie bedeutet, wie man sie in Runden ausrechnet und warum der Dämpfungsfaktor 0,85 beträgt, zeige ich hier an einem Beispiel mit drei Seiten.

Kurz gesagt

  • PR(A) = (1 − d) + d · Σ PR(T)/C(T): Jede Seite gibt ihren PageRank zu gleichen Teilen über ihre ausgehenden Links weiter.
  • Der Dämpfungsfaktor d liegt meist bei 0,85. Er sorgt dafür, dass die Rechnung zu einem stabilen Ergebnis kommt.
  • Gerechnet wird in Runden (Iterationen), bis sich die Werte nicht mehr ändern. Bei drei Seiten reichen rund 20 Runden für drei Nachkommastellen.
Inhalt dieser Seite
  1. Die Formel in einer Zeile
  2. Zwei Fassungen: Summe N oder Summe 1
  3. Was der Dämpfungsfaktor macht
  4. Rechenbeispiel mit drei Seiten
  5. Iteration und Konvergenz
  6. Seiten ohne ausgehende Links
  7. Was die Formel heute noch bedeutet
  8. Häufige Fragen

Die Formel in einer Zeile

In ihrem Aufsatz „The Anatomy of a Large-Scale Hypertextual Web Search Engine“ von 1998 geben Sergey Brin und Larry Page den PageRank einer Seite A so an:

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

Die einzelnen Teile:

ZeichenBedeutung
PR(A)PageRank der Seite A, um den es geht
T1 … Tnalle Seiten, die auf A verlinken
PR(T)PageRank einer dieser verlinkenden Seiten
C(T)Zahl der ausgehenden Links dieser Seite
dDämpfungsfaktor zwischen 0 und 1, üblich ist 0,85

In Worten erklärt: Jede Seite verteilt ihren PageRank gleichmäßig auf alle Seiten, auf die sie verlinkt. Seite A sammelt alle Anteile ein, die bei ihr ankommen, multipliziert die Summe mit d und bekommt einen kleinen Grundwert von (1 − d) obendrauf.

Zwei Fassungen: Summe N oder Summe 1

Wer nachrechnet, stolpert schnell über eine Ungereimtheit. Im Aufsatz steht, die PageRanks aller Seiten ergäben zusammen eins. Mit der Formel oben ergeben sie aber die Anzahl der Seiten N. Deshalb findest du in Lehrbüchern meist eine normierte Fassung:

PR(A) = (1 − d) / N + d · Σ PR(Ti) / C(Ti)

Hier ist PageRank eine echte Wahrscheinlichkeit, und alle Werte zusammen ergeben 1. Für die Reihenfolge der Seiten ist es egal, welche Fassung du nimmst: Die normierten Werte sind einfach die Originalwerte geteilt durch N. Der PageRank-Rechner und die Grafik auf der Startseite nutzen die normierte Fassung.

Was der Dämpfungsfaktor macht

Der Dämpfungsfaktor kommt aus dem Random-Surfer-Modell. Man stellt sich einen Nutzer vor, der auf einer Seite einen zufälligen Link anklickt. Mit der Wahrscheinlichkeit d klickt er weiter, mit 1 − d hat er keine Lust mehr und springt auf irgendeine zufällige Seite im Web.

Ohne diesen Sprung gäbe es zwei Probleme. Erstens würde PageRank in Seitengruppen versickern, die nur untereinander verlinken und keinen Weg nach draußen haben. Zweitens käme die Rechnung bei bestimmten Linkstrukturen nie zur Ruhe. Der Faktor sorgt dafür, dass jede Seite einen Mindestwert bekommt und die Iteration sicher zu einem Ergebnis führt.

  • d nahe 0: Links spielen kaum eine Rolle, alle Seiten liegen fast gleichauf.
  • d = 0,85: der übliche Wert. Links bestimmen den Großteil, die Rechnung bleibt stabil.
  • d nahe 1: Links bestimmen fast alles, aber die Berechnung braucht deutlich mehr Runden, und Linkschleifen bekommen übertrieben viel Gewicht.

Im Rechner kannst du den Regler selbst verschieben und zusehen, wie sich die Werte verändern.

Rechenbeispiel mit drei Seiten

Nehmen wir ein kleines Netz aus drei Seiten:

  • A verlinkt auf B und auf C (zwei ausgehende Links)
  • B verlinkt auf C (ein Link)
  • C verlinkt auf A (ein Link)

Mit d = 0,85 und der Originalformel ergeben sich drei Gleichungen:

PR(A) = 0,15 + 0,85 · PR(C)
PR(B) = 0,15 + 0,85 · PR(A) / 2
PR(C) = 0,15 + 0,85 · ( PR(A) / 2 + PR(B) )

Jede Gleichung braucht Werte, die wir noch nicht kennen. Also starten wir mit einer Annahme, zum Beispiel 1 für jede Seite, und setzen immer wieder ein. Nach der ersten Runde gilt:

  • PR(A) = 0,15 + 0,85 · 1 = 1,000
  • PR(B) = 0,15 + 0,85 · 1/2 = 0,575
  • PR(C) = 0,15 + 0,85 · (1/2 + 1) = 1,425

Mit diesen neuen Werten geht es in die nächste Runde. So entwickeln sich die Zahlen:

RundePR(A)PR(B)PR(C)Summe
Start1,0001,0001,0003,000
11,0000,5751,4253,000
21,3610,5751,0643,000
31,0540,7291,2173,000
41,1850,5981,2173,000
51,1850,6541,1623,000
201,1630,6441,1923,000

Ab etwa Runde 20 ändern sich die ersten drei Nachkommastellen nicht mehr. Das Ergebnis: C hat mit 1,192 den höchsten PageRank, knapp vor A mit 1,163, B liegt mit 0,644 deutlich dahinter. In der normierten Fassung wären das 0,397, 0,388 und 0,215.

Interessant ist, warum C vorne liegt: C bekommt die Hälfte von A und den ganzen PageRank von B. A dagegen hat nur einen Zulieferer, nämlich C, bekommt von dem aber alles, weil C nur diesen einen Link setzt. B bekommt nur eine halbe Stimme von A und bleibt deshalb klein. Genau so funktioniert auch die interne Verlinkung deiner Website.

Iteration und Konvergenz

Das wiederholte Einsetzen heißt Potenzmethode. Mathematisch sucht sie den sogenannten Eigenvektor einer großen Matrix, in der steht, welche Seite mit welchem Anteil auf welche andere verlinkt. Du musst das nicht im Detail verstehen. Wichtig ist nur: Die Rechnung kommt verlässlich zu einem stabilen Ergebnis, egal mit welchen Startwerten du beginnst.

Wie schnell das geht, hängt vor allem vom Dämpfungsfaktor ab. In ihrem technischen Bericht von 1999 schreiben Page, Brin, Motwani und Winograd, dass eine Datenbank mit 322 Millionen Links nach rund 52 Runden ausreichend genau war. Das war für die damalige Hardware die eigentliche Leistung: Die Methode skaliert auf das ganze Web.

In echten Netzen gibt es Seiten, die auf nichts verlinken, etwa PDF-Dateien oder schlecht gebaute Unterseiten. Ihr PageRank würde in der Formel einfach verschwinden, und die Summe würde von Runde zu Runde kleiner. Die übliche Lösung: Der Wert solcher Seiten wird auf alle Seiten gleichmäßig verteilt. Im Modell heißt das, der Zufallssurfer tippt an einer Sackgasse eine neue Adresse ein.

Was die Formel heute noch bedeutet

Die Formel von 1998 ist ein Lehrbuchmodell. Google rechnet seit vielen Jahren mit weiterentwickelten Varianten, die zum Beispiel Links unterschiedlich gewichten, je nachdem wo sie stehen und wie wahrscheinlich ein Klick ist. Die Grundaussagen gelten aber weiter:

  • Links von Seiten, die selbst gut verlinkt sind, zählen mehr.
  • Je mehr Links eine Seite setzt, desto weniger gibt jeder einzelne weiter.
  • Eine Seite ohne eingehende Links bekommt nur den Grundwert.

Wie viel Kraft dabei konkret fließt und was du daraus für deine eigene Seite machen kannst, beschreibe ich unter Linkjuice. Die Originalquelle ist übrigens frei lesbar: Brin und Page, 1998, als PDF auf den Seiten der Stanford University.

Häufige Fragen

Warum ist der Dämpfungsfaktor 0,85?

Brin und Page schreiben in ihrem Aufsatz von 1998, dass sie d üblicherweise auf 0,85 setzen. Der Wert ist ein Kompromiss: Er bildet halbwegs realistisch ab, wie oft Nutzer weiterklicken, und lässt die Berechnung trotzdem schnell zu einem Ergebnis kommen. Mathematisch zwingend ist er nicht.

Ergibt die Summe aller PageRanks 1 oder N?

Das hängt von der Fassung ab. In der Originalformel mit (1 − d) ergibt die Summe die Zahl der Seiten N. In der normierten Fassung mit (1 − d)/N ergibt sie 1, und der PageRank ist dann direkt eine Wahrscheinlichkeit. Das Verhältnis der Seiten untereinander ist in beiden Fällen gleich.

Was passiert mit Seiten, die keine Links nach außen haben?

Solche Seiten heißen Dangling Nodes. Würde man sie ignorieren, ginge PageRank verloren. Üblich ist, ihren Wert gleichmäßig auf alle Seiten zu verteilen, als würde der Zufallssurfer an einer Sackgasse einfach irgendwo neu anfangen.

Wie viel PageRank gibt ein einzelner Link weiter?

Den PageRank der verlinkenden Seite mal d, geteilt durch die Zahl ihrer ausgehenden Links. Hat eine Seite den Wert 4 und zehn ausgehende Links, gehen pro Link 0,85 · 4 / 10 = 0,34 weiter. Das ist das Modell von 1998. Google gewichtet Links heute zusätzlich danach, wie wahrscheinlich ein Klick ist.