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 Hyperlink-Matrix ist einer Adjazenzmatrix (siehe auch IPI, Übungsblatt 9, Aufgabe 1) ähnlich. Während bei der Adjazenzmatrix der Eintrag immer gleich eins ist, wenn der entsprechende Knoten von dem Anfangsknoten erreicht werden kann, muss bei der Hyperlink-Matrix noch eine Änderung vorgenommen werden. Da die gesuchten Ranks die Wahrscheinlichkeiten mit welchen man auf den jeweiligen Websites landet angeben, müssen die Einträge so angepasst werden, dass sie zusammen maximal eins (also 100%) ergeben. Da es für die Berechnung der Ranks später einfacher ist, betrachten wir die Hyperlink-Matrix so, dass die Website von welcher wir ausgehen durch die jeweilige Zeile repräsentiert wird und die Zielseiten sich in den Spalten wiederfinden (transponiert im Vergleich zu der Adjazenzmatrix).

Sei nun [math]H[/math] unsere Hyperlinkmatrix [math]n[/math] die Anzahl der Links, die von der betrachteten 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} \text{, falls unsere Seite einen Link auf die entsprechende Seite besitzt}\\ 0 \text{ sonst} \end{cases} [/math]

Auf der Diagonalen von [math]H[/math] stehen nur Nullen, da eine Website sich nicht selbst verlinkt.

Beispiel

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

Diagonale keine Einträge

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 ausgedrü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 nächstes soll es darum gehen, wie man diese berechnet. Dazu verwenden wir ein iteratives Verfahren.

• es gibt keine EW > 1
• iterative Berechnung von Vektor w -> alle Pageranks
• dann: Interpretation mit Markow, Pagerank als stationäre Verteilung

Iterative Lösung des Eigenproblems

Wir nutzen das folgende allgemeine Ergebnis:

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 starten wir mit der Matrix und einem Startvektor und multiplizieren dann iterativ von links mit [math]H[/math]. SDies konvergiert (unter geeigneten Startbedingungen) gegen einen Eigenvektor zum Eigenwert 1, denn in unserem Fall kann es keine Eigenwerte größer 1 geben. Dieser Eigenvektor ist dann die Lösung zum obigen Problem und beinhaltet alle PageRanks.

Markow-Ketten

Wir wollen nun noch eine intuitivere und schönere Erklärung dazu geben, was hier geschieht. Dazu kommen Markow-Ketten zum Einsatz.

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