Zum Inhalt
Alle Apps

PageRank

Über diese App

Eigenen Linkgraphen bauen, Transitionsmatrix live ansehen und Random Surfer Schritt für Schritt (auch rückwärts oder zehnfach) durch den Graphen wandern lassen — die PageRank-Werte konvergieren sichtbar mit Interpretation.

Die Idee hinter PageRank

PageRank stellt sich das Web als gerichteten Graphen vor, durch den ein „Random Surfer“ wandert. Mit Wahrscheinlichkeit d folgt er zufällig einem ausgehenden Link, mit Wahrscheinlichkeit 1 − d springt er zu einer beliebigen Seite. Der PageRank einer Seite ist die Wahrscheinlichkeit, mit der sich der Surfer auf lange Sicht dort aufhält. Berechnet wird er per Potenziteration: p′[j] = (1 − d)/n + d · Σᵢ p[i] · P[i][j]. Der Dämpfungsfaktor, oft d = 0,85, sorgt dafür, dass Sackgassen und Zyklen die Wanderung nicht festhalten und die Lösung eindeutig ist.

Was die App zeigt

Ein Beispielgraph mit Knoten und Pfeilen, dessen Kreisgröße den aktuellen PageRank zeigt. Wandernde Punkte simulieren den Surfer bei jedem Schritt. Ein Matrix-Panel zeigt die Übergangswahrscheinlichkeiten transponiert, sodass jede Spalte die Verteilung eines Ausgangsknotens ist; Knoten ohne ausgehende Pfeile sind markiert. Das PageRank-Panel nennt den führenden und den letzten Knoten und meldet, ob sich die Verteilung stabilisiert hat.

Selbst ausprobieren

Füge Knoten hinzu und ziehe Kanten, indem du erst den Start-, dann den Zielknoten anklickst; ein Klick auf einen Pfeil löscht ihn. Gehe einzelne Schritte vor, zurück oder zehn auf einmal und beobachte, wie Δ kleiner wird. Verändere den Dämpfungsfaktor d und vergleiche die Ergebnisse. Achte darauf, wie ein Knoten an Rang gewinnt, wenn ein bereits wichtiger Knoten auf ihn verlinkt.

Häufige Fragen

Wie funktioniert der PageRank-Algorithmus?
PageRank bewertet Knoten eines Linkgraphen nach der Wahrscheinlichkeit, mit der ein zufälliger Surfer sie auf lange Sicht besucht. Ein Link überträgt einen Teil der Bedeutung der verlinkenden Seite, aufgeteilt auf all ihre ausgehenden Links. Der Vektor wird iterativ berechnet, bis er sich kaum noch ändert.
Wozu dient der Dämpfungsfaktor beim PageRank?
Der Dämpfungsfaktor d ist die Wahrscheinlichkeit, einem Link zu folgen; mit 1 − d springt der Surfer zu einem zufälligen Knoten. Dadurch bleibt er nicht in Sackgassen oder geschlossenen Zyklen hängen, und die stationäre Verteilung ist eindeutig. Ein üblicher Wert ist 0,85.
Was hat PageRank mit Eigenvektoren zu tun?
Der PageRank-Vektor ist die stationäre Verteilung einer Markov-Kette und damit ein Eigenvektor der (gedämpften) Übergangsmatrix zum Eigenwert 1. Die Potenziteration multipliziert einen Startvektor immer wieder mit dieser Matrix und nähert sich so dem Eigenvektor an.
Was kann ich in der App ausprobieren?
Du baust einen eigenen Graphen aus Knoten und Pfeilen, stellst den Dämpfungsfaktor ein und lässt den Random Surfer Schritt für Schritt, rückwärts oder zehnfach laufen. Die Matrix wird live aktualisiert, und eine Textzeile sagt, ob die Werte konvergiert sind. In dieser App verteilen Knoten ohne ausgehende Pfeile ihre Wahrscheinlichkeit an sich selbst.

Fach: Machine Learning

Mehr aus Machine Learning

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps