Page-Rank-Algorithmus

Der Page-Rank Algorithmus arbeitet auf Link-Graphen(Gerichteter Graph).
Als Beispiel für einen solchen Link-Graphen dient das Internet. Anhand des Beispiels Internet wird der Algorithmus auch im kurzen aufgezeigt.

Beispiel Page-Rank Algorithmus und das Internet

Für das Beispiel wird der oben gezeigte Link-Graph betrachtet. Jeder Knoten ist eine Seite und jede Kante eine Verlinkung von einer Seite auf eine andere.

Es stellt sich nun die Frage, welche Seite die relevanteste ist und z.B. in der Suche als Erstes angezeigt wird.

Traditionelles Mass:

Das traditionelle Mass für die Relevanz einer Seite ist identisch zur Variante, mit welcher man die Relevanz eines wissenschaftlichen Papers gemessen hat. Man zählt die Anzahl der Zitate (also die Links) auf eine Seite. Die Seite, die so die Meisten Zitate bzw. Links erhält wird als die relevanteste angesehen. Nach traditionellem Mass ist also Seite 2 die relevanteste, da es die Seite ist, auf welche die meisten Links zeigen.

So kann allerdings die Relevanz einer einzelnen Seite selbst manipuliert werden, indem gezielt neue Seiten erstellt werden, welche auf die gewünschte Seite verlinken. Während dieses künstliche Erstellen von Seiten bei wissenschaftlichen Papern noch einigermassen schwer und unpraktisch war, konnten im Internet sehr einfach viele Seiten erstellt werden und auf eine einzige Seite verlinken, um die Relevanz dieser Seite in die Höhe zu treiben.

Page-Rank Algorithmus:

In ihrem Paper “The anatomy of a large-scale hypertextual Web search engine” von 1998 widmen sich Sergey Brin und Lawrance Page diesem Problem und stellen eine Suchmaschine (Google) vor, welche einen anderen Page-Rank Algorithmus verwendet.

Ihr Algorithmus basiert auf den folgenden Prinzipen:

• Zitate von relevanten Seiten zählen mehr
• Zitate von Seiten, welche viele andere Seiten zitieren zählen weniger

Die Relevanz einer einzigen Seite ist:

$$\frac{\text{Summe der Relvanzen der zitierenden Seiten}}{\text{Anzahl der zitierten Seiten}}$$

Beispiel mit dem obigen Link-Graph

Die Relevanz der Seite zwei ist:
$x_2=\frac{x_1}{2}+x_4+x_5\frac{x_6}{4}$
Diese Gleichung kann man nun noch für die anderen 5 Seiten aufstellen.
So erhält man dann ein lineares Gleichungssystem mit 6 Gleichungen und 6 unbekannten.

Das Problem ist aber noch nicht vollständig gelöst, denn $0$ löst immer jedes dieser Gleichungssysteme. Dann hat aber jede Seite einfach eine Relevanz von $0$, was auch nicht hilfreich ist. Es muss also noch ein Faktor in die Gleichungssysteme eingebaut werden, damit $0$ nicht für alle $x$ eine Lösung sein kann.

Dafür wurde der sogenannte Dämpfungsfaktor $d$ eingeführt. Damit der Dämpfungsfaktor das eigentliche Resultat nicht verfälscht sondern nur dafür sorgt, dass $0$ nicht für alle $x$ eine Lösung ist soll dieser möglichst nahe an 1 liegen. Es bietet sich z.B. $d=\frac{7}{8}$ an. Es gibt natürlich noch viele Werte, welche näher an 1 liegen als $\frac{7}{8}$ aber es gilt auch abzuwägen, wie gross der Rechenaufwand wird. So hat sich $\frac{7}{8}$ als geeigneter Wert herausgestellt. Mit Dämfungsfaktor sieht die Berechnung der Relevanz für eine Seite dann folgendermassen aus:
$x_2=(1-d)+d(\frac{x_1}{2}+x_4+x_5\frac{x_6}{4})$
Das Gleichungssystem kann nun für den obigen Link-Graphen gelöst werden. Daraus ergeben sich dann die folgenden Werte:

Die Seite mit der grössten Relevanz ist hier also Seite 3. Seite 2 hat zwar viele andere Seiten, welche auf die Seite verweisen, leidet aber darunter, dass es einen Link von Seite 6 zu Seite 2 gibt, da von der Seite 6 so viele Links auf andere Seiten gehen und somit Seite 6 eine nicht so relevante Seite ist. Seite 3 hingegen hat zwar nur wenige Links, diese Links sind dafür aber von relevanten Seiten.