Der PageRank Algorithmus ist ein Verfahren, eine Menge verlinkter Dokumente, wie zum Beispiel das Welt Weite Netz, anhand ihrer Struktur zu bewerten, beziehungsweise zu messen. Dabei wird jedem Element eine Maßeinheit, der PageRank, aufgrund der verlinkten Seiten zugeordnet. Dieser Algorithmus wurde von Larry Page (deshalb auch PageRank) und Sergey Brin an der Stanford University entwickelt und patentiert. Er diente Google, dem von Page und Brin gegründeten Unternehmen, als Grundlage für die Bewertung von Web-Seiten.

Das Prinzip ist: Je mehr Links auf eine Seite verlinken, desto größer ist das Gewicht dieser Seite. Je größer das Gewicht der verlinkenden Seiten ist, desto größer ist der Effekt. Der PageRank Algorithmus ahmt einen zufällig durch das Netz surfenden User nach. Die Wahrscheinlichkeit, mit der jener auf eine Website stößt, korreliert mit dem PageRank.

 

Das Prinzip des PageRank Algorithmus ist, dass jede Seite ein Gewicht, den PageRank, besitzt, dass desto größer ist, je mehr Seiten mit möglichst großem eigenem Gewicht auf diese Seite verlinken. Das Gewicht, also der PR einer Seite i berechnet sich also aus den Gewichten PR_j der auf i verlinkenden Seiten j. Verlinkt j auf insgesamt C_j verschiedene Seiten, so wird das Gewicht von PR_j anteilig auf diese Seiten aufgeteilt. Folgende Formel kann als Definition des PageRank Algorithmus angesehen werden:

Dabei ist N die Gesamtanzahl der Seiten und d ein Dämpfungsfaktor zwischen 0 und 1, mit dem ein kleiner Anteil des Gewichts (1 − d) einer jeden Seite abgezogen und gleichmäßig auf alle Seiten verteilt wird. Dies ist notwendig, damit das Gewicht nicht zu Seiten „abfließt“, die auf keine andere Seite verweisen. Oft wird obige Formel auch ohne den Normierungsfaktor 1 / N angegeben.

Die Gleichung kann sowohl als Eigenvektorproblem der Matrix

als auch (für d < 1) als Lösung des linearen Gleichungssystems

mit

interpretiert werden, wobei δ_ij das Kronecker-Delta bezeichnet. Die Lösung des linearen Gleichungssystems

kann analytisch oder numerisch erfolgen. Für d < 1 ist die Lösung des Gleichungssystems eindeutig. Durch Verwendung der Jacobi Iteration zur numerischen Lösung ergibt sich obige rekursive Gleichung. Andere numerische Verfahren zur Matrixinvertierung, wie das Minimale-Residuum-Verfahren oder die Gauss-Seidel-Methode, konvergieren jedoch in der Regel schneller.

Der heute von Google verwendete Algorithmus hat vermutlich nicht mehr exakt diese Form, basiert aber auf dieser Formel. Alternative Algorithmen sind das Verfahren der Hubs und Authorities von Jon Kleinberg, der Hilltop- und der TrustRank Algorithmus.

 

Normiert man den PageRank auf 1, so kann man das Gewicht einer Seite als Wahrscheinlichkeit interpretieren, dass ein zufälliger Surfer (siehe Zufallspfad) sich auf dieser Seite befindet. Ein zufälliger Surfer bewegt sich dabei wie folgt durch das Netz: Mit Wahrscheinlichkeit d wählt er zufällig einen ausgehenden Link der aktuellen Seite; mit Wahrscheinlichkeit 1 − d wählt er eine beliebige neue Seite. Um Probleme mit Seiten ohne ausgehende Links zu vermeiden, können bei diesen Links zu allen vorhandenen Seiten hinzugefügt werden.

 

Informationen über den PageRank lassen sich aus der Google-Toolbar und dem Google-Verzeichnis ersehen. Der von der Google Toolbar angezeigte PageRank liegt zwischen 0 und 10, der Wert im Verzeichnis zwischen 0 und 7. Beide Werte bilden den realen PageRank auf einer logarithmischen Skala ab und geben das Ergebnis als abgerundeten, ganzzahligen Wert wieder.

Der in der Google-Toolbar angezeigte PageRank wurde damals alle dreißig Tage aktualisiert. Heute ist das Intervall zwischen den Updates angestiegen, auf etwa hundert Tage.

Diese Informationen basieren auf einem Wikipedia Artikel.