Konstruktion

Das Prinzip des PageRank-Algorithmus ist, dass jede Seite ein Gewicht (PageRank) besitzt, das umso größer ist, je mehr Seiten (mit möglichst hohem eigenen Gewicht) auf diese Seite verweisen. Das Gewicht ${\displaystyle PR_{i}}$ einer Seite ${\displaystyle i}$ berechnet sich also aus den Gewichten ${\displaystyle PR_{j}}$ der auf ${\displaystyle i}$ verlinkenden Seiten ${\displaystyle j}$. Verlinkt ${\displaystyle j}$ auf insgesamt ${\displaystyle c_{j}}$ verschiedene Seiten, so wird das Gewicht von ${\displaystyle PR_{j}}$ anteilig auf diese Seiten aufgeteilt. Folgende rekursive Formel kann als Definition des PageRank-Algorithmus angesehen werden:

${\displaystyle PR_{i}={\frac {1-d}{n}}+d\,\sum _{j=1}^{n}{\frac {PR_{j}}{c_{j}}}}$

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

Analog kann die Gleichung auch als zeilenweise Notation des linearen Gleichungssystems

${\displaystyle M\cdot PR={\frac {1-d}{n}}\mathbf {1} }$

mit dem Spaltenvektor ${\displaystyle PR=(PR_{j})_{j}}$, dem konstanten Spaltenvektor ${\displaystyle \mathbf {1} }$ und der Matrix ${\displaystyle M=(M_{ij})_{ij}}$ mit Koeffizienten

${\displaystyle M_{ij}=\delta _{ij}-d\,L_{ij}}$

interpretiert werden, wobei ${\displaystyle \delta _{ij}}$ das Kronecker-Delta bezeichnet und die Matrix ${\displaystyle L}$ durch

${\displaystyle L_{ij}={\begin{cases}1/c_{j},&{\text{falls Seite }}j{\text{ zu Seite }}i{\text{ linkt}}\\0,&{\text{sonst}}\end{cases}}}$

definiert ist.

Diese Gleichung führt auf das Eigenwertproblem

${\displaystyle P^{T}(PR)=PR}$,

wobei ${\displaystyle P}$ die sogenannte Google-Matrix ist und ${\displaystyle P^{T}}$ die Transponierte der Matrix bezeichnet.

Für ${\displaystyle d<1}$ ist die Lösung des Gleichungssystems eindeutig (Satz von Perron-Frobenius). Ein kleinerer Dämpfungsfaktor ${\displaystyle d}$ führt zu einer homogeneren Verteilung des PageRanks.

Die Lösung des linearen Gleichungssystems kann analytisch oder numerisch erfolgen. Durch Verwendung der Jacobi-Iteration zur numerischen Lösung ergibt sich obige rekursive Gleichung. Andere numerische Verfahren zur Matrixinvertierung, wie das Minimale-Residuum-, das Überrelaxations- oder das Gauß-Seidel-Verfahren, konvergieren jedoch in der Regel schneller.

Zufallssurfermodell

Das Zufallssurfermodell (engl. Random Surfer Model) bietet eine alternative Interpretation des Page-Rank-Algorithmus, welche aus der Stochastik kommt. Normiert man den PageRank auf 1, so kann man das Gewicht einer Seite als Wahrscheinlichkeit interpretieren, dass ein zufälliger Surfer (Zufallspfad) sich auf dieser Seite befindet. Ein zufälliger Surfer bewegt sich durch das Netz, indem er mit der Wahrscheinlichkeit ${\displaystyle d}$ zufällig einen der ausgehenden Links der aktuellen Seite wählt. Mit Wahrscheinlichkeit ${\displaystyle 1-d}$ wählt er eine beliebige neue Seite. Das Modell kann als Markow-Kette verstanden werden, der normierte Page-Rank ist dann die stationäre Verteilung dieser Kette.

Rational Surfer Modell

Das Rational Surfer Modell ist ein von Google 2010 eingereichtes Patent. Es stellt eine Weiterentwicklung des Zufallssurfermodells dar. Hierbei wird die Wichtigkeit eines Links je nach Platzierung nach empirischen Daten unterschieden. Ziel ist es, Links stärker zu gewichten, welche von einem rationalen Surfer mit höherer Wahrscheinlichkeit geklickt werden. Somit soll Linkkauf entgegengewirkt werden.

Wissenschaftliche Forschung und Hochschulwesen

PageRank wird verwendet, um den wissenschaftlichen Einfluss von Forschern zu quantifizieren. Die zugrunde liegenden Zitations- und Kollaborationsnetzwerke werden in Verbindung mit dem Pagerank-Algorithmus verwendet, um ein Ranking-System für einzelne Publikationen zu entwickeln, das sich auf einzelne Autoren überträgt. Der neue Index, der als Pagerank-Index (Pi) bekannt ist, erweist sich im Vergleich zum h-Index als gerechter, da dieser viele Nachteile aufweist.

Für die Analyse von Proteinnetzwerken in der Biologie ist PageRank ebenfalls ein nützliches Werkzeug.

In jedem Ökosystem kann eine abgewandelte Version des PageRank verwendet werden, um die Arten zu bestimmen, die für das Fortbestehen des Ökosystems wichtig sind.

Eine ähnliche neue Anwendung von PageRank besteht darin, akademische Promotionsprogramme auf der Grundlage ihrer Erfolge bei der Einstellung ihrer Absolventen in Fakultätspositionen zu bewerten. Im Sinne von PageRank sind akademische Abteilungen miteinander verbunden, indem sie ihre Lehrkräfte voneinander (und von sich selbst) anwerben.

Internet

Das soziale Netzwerk Twitter benutzt ein angepasstes PageRank-System. Deren Empfehlungsdienst WTF („Who to Follow“) stellt täglich Millionen von Verbindungen zwischen Nutzern auf der Grundlage gemeinsamer Interessen, Verbindungen und anderer verwandter Faktoren her.