PageRank-Algorithmus

Es gibt mehrere Milliarden Websites im Internet und doch erscheint, wenn wir bei Google beispielsweise nach "Fun Facts Heidelberg" suchen, die Vorlesungsseite in verschiedenen Browsern unter den ersten zehn. Das liegt daran, dass der Suchbegriff auf einigen der Seiten keine so große Rolle spielt. Man wird feststellen, dass die ersten Ergebnisse die relevantesten sind. Aber wie schafft es die Suchmaschine die Seiten so zu sortieren? Dort kommt der PageRank-Algorithmus ins Spiel, welcher die Seiten über die Anzahl an Links mit Hilfe von linearer Algebra nach ihrer Wichtigkeit sortiert.

Hyperlink-Übergangsmatrix

Die Grundlage für unsere Überlegungen bildet eine quadratische Matrix, mit einer Spalte für jede Websites im Internet. Wir betrachten nun für jede Website die Links auf dieser, wobei doppelte nur einfach gezählt werden. Dass eine solche Verbindung zwischen zwei Websites besteht, soll jetzt, wie bei einer Adjazenzmatrix (siehe auch IPI, Übungsblatt 9, Aufgabe 1) in das entsprechende Feld unserer Hyperlink-Matrix eingetragen werden. Anders als bei der Adjazenzmatrix, in der jeder Eintrag gleich eins ist, wenn der entsprechende Knoten von dem Anfangsknoten erreicht werden kann, führen wir hier eine Abwandlung durch: bei der Hyperlink-Matrix werden die Einträge so angepasst, dass die Summe der Spalten stets eins ergibt. Da es für die Berechnung der Ranks später einfacher ist, stellen wir die Hyperlink-Matrix so auf, dass die Website von welcher wir ausgehen durch die jeweilige Spalte repräsentiert wird und die Zielseiten sich in den Zeilen wiederfinden (transponiert im Vergleich zu der Adjazenzmatrix).

Sei nun [math]H[/math] unsere Hyperlinkmatrix, [math]n_j[/math] die Anzahl der Links, die von der [math]j[/math]-ten Website auf andere Websites verweisen. Der Eintrag an der Stelle [math]h_{ij}[/math] ist dann also wie folgt:

[math]h_{ij}=\begin{cases} \frac{1}{n} \quad \text{, falls unsere Seite einen Link auf die } i\text{-te Seite besitzt}\\ 0 \quad \text{ sonst} \end{cases} [/math]

Das heißt, die Summe jeder einzelnen Spalte ergibt immer eins und auf der Diagonalen von [math]H[/math] stehen nur Nullen, da eine Website sich nicht selbst verlinkt.

Beispiel

Betrachten wir nun folgendes stark vereinfachtes Internet und stellen die entsprechende Matrix auf:

• 

Betrachten wir nun die erste Spalte unserer Matrix, also die Website [math]A[/math] und zu welchen Seiten sie einen Link besitzt. Es gibt einen Pfeil nach [math]B[/math] und einen nach [math]D[/math]. Insgesamt gehen also zwei Links von [math]A[/math] weg, das heißt [math]n = 2[/math]. Die erste Spalte sieht deswegen wie folgt aus:

[math]\begin{pmatrix} 0\\ \frac{1}{2}\\ 0\\ \frac{1}{2}\\ 0 \end{pmatrix}[/math]

Da auf der Website [math]A[/math] zwei andere Websites verlinkt sind, sind die Einträge jeweils [math]\frac{1}{2}[/math]. Es fällt auf, dass auf der Website [math]C[/math] drei weitere Websites verlinkt sind, nämlich [math]A[/math], [math]B[/math] und [math]E[/math]. Das heißt, hier sind die Einträge jeweils [math]\frac{1}{3}[/math]. Die dritte Spalte sieht also wie folgt aus:

[math]\begin{pmatrix} \frac{1}{3}\\ \frac{1}{3}\\ 0\\ 0\\ \frac{1}{3} \end{pmatrix}[/math]

Die anderen Spalten folgen analog und wir gelangen zu folgender Hyperlink-Matrix:

[math]H=\begin{pmatrix} 0 & 0 & \frac{1}{3} & 0 & 0\\ \frac{1}{2} & 0 & \frac{1}{3} & 1 & \frac{1}{2}\\ 0 & \frac{1}{2} & 0 & 0 & 0\\ \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2}\\ 0 & \frac{1}{2} & \frac{1}{3} & 0 & 0 \end{pmatrix}[/math]

Prinzip des PageRank-Algorithmus

Eine Website ist umso wichtiger, um so mehr Links von wichtigen Websites auf sie verweisen. Dies soll jetzt in einer Zahl ausgedrückt werden. Sei also [math]a[/math] eine Website mit PageRank [math]R(a)[/math], für eine beliebige Seite [math]x[/math] sei [math]L(x)[/math] die Anzahl der (verschiedenen) Links, die auf [math]x[/math] vorkommen. Sei zudem [math]B_a[/math] die Menge der Websites, die einen Link zu [math]a[/math] besitzen. Dann lässt wird der Grundgedanke von PageRank durch die folgende Formel ausdrücken:

[math]R(a) = \sum_{x \in B_a} \frac{R(x)}{L(x)} [/math].

(Würde man nicht durch [math]L(x)[/math] teilen, sondern einfach die Summe der Ranks der Seiten in [math]B_a[/math] betrachten, so würden Seiten mit sehr vielen Links viel stärker ins Gewicht fallen als etwa Seiten mit nur einem Link darauf.) Offenbar handelt es sich um eine Art rekursive Definition: Man muss zur Berechnung eines PageRanks die PageRanks anderer Websites kennen. Es bleibt also nichts, als alle diese Gleichungen simultan zu lösen (LGS!). Wir versuchen also diese Gleichungen in LA-Sprache zu übersetzen, wobei wir von der Matrix aus dem vorigen Abschnitt Gebrauch machen.

Sei [math]w[/math] der Spaltenvektor mit den PageRank-Werten der einzelnen Seiten ([math]i[/math]-te Komponente zu [math]i[/math]-ter Website). Mann kann sich anhand der Definition der Matrixmultiplikation leicht überlegen, dass das obige LGS äquivalent ist zu [math]Hw = w[/math].

Wir erkennen eine bekannte Form: es handelt sich hier um ein Eigenvektorproblem. Zunächst müssen wir zwei Dinge abhaken. Erstens müssen wir klären, dass es überhaupt eine nicht-triviale Lösung [math]w[/math] gibt, zweitens muss man sich fragen, wieso diese, mit der Zusatzbedingung, dass die Summe der Einträge in [math]w[/math] gleich 1 ist, eindeutig ist.

Im nächsten Abschnitt wollen wir diese Lösung iterativ berechnen.

Iterative Berechnung der Lösung

Dazu nutzen wir ein Ergebnis aus der LA (Potenzmethode):

Betrachtet man eine diagonalisierbare Matrix A, so gibt es eine Basis aus den Eigenvektoren zu den entsprechenden Eigenwerten. Betrachte nun die Eigenwerte und sortiere sie nach der Größe des Betrags, sodass gilt [math] |λ_{1}|\gt |λ_{2}|\geq ... \geq |λ_{n}| [/math].Nun wählen wir einen Startvektor und erhalten eine Folge [math] (v^{(i)}) [/math], die durch sukzessives Anwenden von A definiert ist. Es gilt: [math] v^ {(i+1)} = Av^ {(i)} [/math]. Diese Folge konvergiert bei geeigneter Wahl von dem Startvektor gegen einen Eigenvektor v der Matrix A zum Eigenwert [math] λ_{1} [/math]. Falls also k groß genug ist, gilt: [math]Av^{(k)} \approx λ_{1}v^{(k)} [/math].

In der Anwendung wählen wir einfach einen Startvektor, etwa einen Einheitsvektor und multiplizieren iterativ [math]H[/math] von links. Wir erhalten (unter geeigneten Startbedingungen) Konvergenz gegen einen Eigenvektor zum Eigenwert 1, denn es gibt hier keine größeren Eigenwerte als 1. Dieser stellt dann eine Lösung des LGS dar und enthält damit die gesuchten Page-Ranks.

Beispiel

Wir betrachten weiterhin das Beispiel aus dem Abschnitt Hyperlink-Übergangsmatrix mit der Matrix [math]H[/math] und wählen als Startvektor den folgenden Einheitsvektor:

[math]v=\begin{pmatrix} 1\\ 0\\ 0\\ 0\\ 0 \end{pmatrix}[/math]

Das bedeutet, dass wir bei Website [math]A[/math] starten. Nun multiplizieren wir die Matrix [math]H[/math] von links an den Vektor und erhalten

[math]H \cdot v=\begin{pmatrix} 0 & 0 & \frac{1}{3} & 0 & 0\\ \frac{1}{2} & 0 & \frac{1}{3} & 1 & \frac{1}{2}\\ 0 & \frac{1}{2} & 0 & 0 & 0\\ \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2}\\ 0 & \frac{1}{2} & \frac{1}{3} & 0 & 0 \end{pmatrix}\cdot\begin{pmatrix} 1\\ 0\\ 0\\ 0\\ 0 \end{pmatrix}=\begin{pmatrix} 0\\ \frac{1}{2}\\ 0\\ \frac{1}{2}\\ 0 \end{pmatrix}[/math]

Multiplizieren wir die Matrix ausreichend oft erneut von links an den aktuellen Vektor, so erhalten wir folgenden Vektor:

[math]r=\begin{pmatrix} 0,061\\ 0,364\\ 0,182\\ 0,152\\ 0,242 \end{pmatrix}[/math]

Dies ist der Eigenvektor zum Eigenwert 1 unserer Matrix [math]H[/math]. Eine andere Möglichkeit zur Berechnung dieses Vektors ist, zunächst die Matrix ausreichend oft zu potenzieren und anschließend den Vektor [math]v[/math] von rechts zu multiplizieren. Das funktioniert, da gilt [math]Hv^{i}=H^{i}v[/math].

Markow-Ketten

Jetzt wollen wir eine schöne und intuitive Sichtweise dafür geben, was hier passiert. Das ist die Theorie der Markow-Ketten (hier sehr seicht abgehandelt!). Dabei geht es um eine Menge von Zuständen mit Übergangswahrscheinlichkeiten zwischen diesen. Hier stellt unsere Menge der Webseiten die Zustandsmenge dar und die Matrix [math]H[/math] die Übergangsmatrix. Die Interpretation ist die, dass ein zufälliger Surfer von einer beliebigen Website einen der Links zufällig anklickt und dann auf einer der anderen Websites landet. Multipliziert man z. B. die Übergangsmatrix an den ersten Einheitsvektor, so erhält man die Wahrscheinlichkeiten, wo der zufällige Surfer sich nach einem Schritt befindet, wenn er auf der ersten Website gestartet ist.

Potenziert man diese Übergangsmatrix, etwa [math]H^k[/math], so erhält man in den Zellen die Übergangswahrscheinlichkeiten von einem Zustand (Spalte) zu einem anderen (Zeile) in genau [math]k[/math] Übergangsschritten. Das kann man sich leicht anhand der Matrixmultiplikation überlegen. Der Gedanke liegt nahe, dass diese Matrixpotenzen konvergieren, denn irgendwann spielen die Einzelübergänge keine große Rolle mehr; man erhält eine eine Matrix mit lauter gleichen Spalten (das kann man mit Matrixcalc sehr gut ausprobieren!). Das liegt daran, dass die Multiplikation mit jedem stochastischen Vektor (das ist ein Spaltenvektor mit nicht negativen Einträgen, die sich zu 1 ergänzen), wie etwa einem der Einheitsvektoren das gleiche ergibt: der Start spielt keine Rolle mehr, man erhält im Grenzwert eine Aufenthaltswahrscheinlichkeit für jeden der Zustände.

Die oben beschriebene Konvergenz findet allerdings nur unter gewissen Voraussetzungen statt. Um diese soll es jetzt kurz gehen.

Quellen und weiterführende Links

• https://homepage.univie.ac.at/Franz.Embacher/Lehre/aussermathAnw/Google.html
• https://en.wikipedia.org/wiki/PageRank
• https://de.wikipedia.org/wiki/Google-Matrix
• Arens, T. (et al.): Mathematik, Springer 2008