PageRank – Zu Geschichte und Funktionsweise von Googles zentralem Ranking-Algorithmus

Maßgeblich für den Erfolg Googles dürfte die Qualität der Suchergebnisse gewesen sein. Das Ranking bei Google basierte von Beginn an grundlegend auf einem Algorithmus namens PageRank, dessen Grundzüge von den beiden Google-Gründern 1998 publiziert wurden (Brin/Page 1998). Da das Ranking eines der entscheidenden Aufgaben einer Web-Suchmaschine ist und PageRank laut Google (2009) zwar nicht der einzige, aber der wichtigste Ranking-Mechanismus der Google-Suche ist, lohnt es sich, die Funktionsweise von PageRank näher zu betrachten.

Der PageRank-Algorithmus basiert zunächst auf dem Prinzip der Linkpopularität. Während klassische algorithmische Suchmaschinen die Rangfolge der Ergebnisse danach gewichteten, wie oft und an welcher Stelle die Suchworte in dem im Index der Suchmaschine gespeicherten Webinhalten vorkommen – also nach dem Inhalt der Seite – ermittelt Google den Wert einer Webseite nach der Anzahl und Qualität der Links, die auf die Webinhalte verweisen. Dem liegt die Annahme zugrunde, dass Inhalte mit großem inhaltlichen Wert im Web häufiger verlinkt werden als andere, und dass Seiten mit großem inhaltlichen Wert wertvollere Links als andere Seiten setzen, oder anders ausgedrückt: Je mehr Seiten auf eine Webseite verweisen, und je höher die - ebenfalls durch den PageRank ermittelte - Gewichtung der verweisenden Seite, desto höher wird die Seite gewichtet, die Ziel der Verweise ist. PageRank ist damit eine gewichtende Version des Modells der einfachen Linkpopularität, welche sich auf die bloße Anzahl der eingehenden Links beschränkt.

PageRanks Vorfahren: Soziometrie, Bibliometrie und Journal Impact Factor

Das dem PageRank zugrunde liegende Prinzip der Gewichtung erwies sich als außerordentlich erfolgreich für das Ranking der Suchergebnisse von Suchmaschinen.

Bemerkenswert ist allerdings, dass die Grundidee bereits vorher in anderen Kontexten entwickelt wurde. Die Bibliometrie, die Gesamtheiten von Publikationen empirisch untersucht, hat sich schon früh zur Aufgabe gemacht, durch die Analyse von Zitierungen quantitative Maße für die Wichtigkeit und Bedeutsamkeit wissenschaftlicher Publikationen zu entwickeln (Kleinberg 1998). So schlug Garfield (1972), auf den sich Page und Brin in ihrem Papier zum PageRank beziehen, den Impact Factor (oder auch Journal Impact Factor) einer wissenschaftlichen Zeitschrift vor, der sich aus der Anzahl der Zitierungen der Zeitschrift in den vorherigen zwei Jahren durch andere Zeitschriften bestimmt.

Wenn man dieses Prinzip auf die Struktur des World Wide Web übertragen würde, hieße dies, dass sich die Bedeutung einer Website aus der Anzahl der Links ermitteln ließe, die auf sie zeigen, was dem Prinzip der einfachen Linkpopularität entsprechen würde.

Spätere bibliometrische Modelle wie das von Pinksi und Narin (vgl. 1976) beziehen, ähnlich wie Googles PageRank, die Bedeutung der Quelle von Links bei der Bewertung von Webseiten, zusätzlich auch die Bedeutung der Zeitschrift mit ein, durch die die Zitierung erfolgt – wobei sich deren Bedeutung wiederum durch die Bedeutung der auf sie verweisenden Zitierungen bestimmt:

“We observe that the impact factor is a ranking measure based fundamentally on a pure counting of the in-degrees of nodes in the network. Pinski and Narin [1976] proposed a more subtle citation-based measure of standing, stemming from the observation that not all citations are equally important. They argued that a journal is 'influential' if, recursively, it is heavily cited by other influential journals.” (Kleinberg 1998)

Auch das von Page 1998 angemeldete Patent auf den PageRank erstreckt sich nicht nur auf die Linkanalyse von Webseiten, sondern allgemein auf das Ranking miteinander verbundener Elemente einer Datenbank, wobei Webinhalte und Hypermedia-Systeme, aber auch Datenbanken von Dokumenten, die Zitierungen enthalten, als Anwendung exemplarisch aufgeführt werden (vgl. Brin/Page 1998).

Inspiriert von der PageRank-Methode schlugen Bollen et al. (2006) schließlich eine Weiterentwicklung des Journal Impact Factor vor, das dessen Prinzip der Gewichtung von Verweisen bzw. Zitierungen miteinbezieht.

Auch in der Soziometrie, die als Teilgebiet der empirischen Sozialforschung Beziehungen zwischen Mitgliedern einer Gruppe untersucht, wurden dem PageRank ähnliche Methoden entworfen. So entwickelte Katz bereits 1953 bestehende Verfahren zur Ermittlung des sozialen Status von Gruppenmitgliedern weiter, indem er auch den Status derjenigen mit einbezog, die den Status anderer beurteilen:

“The purpose of this paper is to suggest a new method of computing status, taking into account not only the number of direct 'votes' received by each individual but, also, the status of each individual who chooses the first, the status of each who chooses these in turn, etc. ” (Katz 1953: 39)

Interessant erscheint des weiteren, dass der PageRank Vorteile algorithmischer Suchmaschinen mit denen von redaktionell erstellten Web-Verzeichnissen vereint: Zwar erfolgt der Vorgang der Zusammenstellung des Index wie bei klassischen algorithmischen Systemen automatisiert, die Grundlage für die Bewertung stellen allerdings Links auf Web-Inhalte dar, die häufig manuell, also durch menschliche Auswahl gesetzt werden. Es handelt sich damit um kein rein technisches System, sondern um eine Kombination aus menschlicher Auswahl und maschineller Berechnung.

Literatur

Bollen, Johan/Rodriguez, Marko A./Van de Sompel, Herbert (2006): Journal Status. In: Scientometrics 69/3. Brin, Sergey/Page, Lawrence (1998): The Anatomy of a Large-Scale Hypertextual Web Search Engine. In: Computer Networks and ISDN Systems. Online: http://infolab.stanford.edu/~backrub/google.html Garfield, Eugene (1972): Citation analysis as a tool in journal evaluation. In: Science, 178, 471–479. Google (2009): Google-Technologie. Online: http://www.cs.cornell.edu/home/kleinber/auth.pdf Katz, Leo (1953): A New Status Index Derived from Sociometric Analysis. In: Psychometrika 18/1, 39-43 Kleinberg, Jon M. (1998): Authoritative Sources in a Hyperlinked Environment. Online: http://www.cs.cornell.edu/home/kleinber/auth.pdf Pinski, G./Narin, F.: (1976): Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics. In: Information Processing and Management, 12, 297–312.
Home