Beschreibung zum PageRanking

1. Überblick über das PageRank-Verfahren

Im Verlauf der letzten Jahre hat sich Google weltweit zur bedeutendsten Suchmaschine entwickelt. Maßgebend verantworlich hierfür war neben einer hohen Performance und einer großen Benutzerfreundlichkeit vor allem die anderen Suchmaschinen teilweise weit überlegene Qualität der Suchergebnisse. Diese Qualität der Suchergebnisse beruht ganz wesentlich auf dem PageRank-Verfahren.

An dieser Stelle soll ein möglichst breiter Überblick über alle Aspekte des PageRank-Verfahrens wiedergegeben werden. Unser Überblick stützt sich dabei im Kern auf Veröffentlichungen der Google-Gründer Lawrence Page und Sergey Brin aus ihrer Zeit als Graduiertenstudenten an der Stanford University.

Vielerorts wird angeführt, dass seit den Forschungsarbeiten am PageRank-Verfahren vor allem angesichts der Dynamik des Internets zu viel Zeit vergangen ist, als dass die veröffentlichten Dokumente immer noch für die Bewertungsmethodik der Suchmaschine Google maßgebend sind. Es soll auch nicht bezweifelt werden, dass im Verlauf der letzten Jahre mit großer Wahrscheinlichkeit zahlreiche Änderungen, Anpassungen und Modifikationen am ursprünglichen PageRank-Algorithmus stattgefunden haben. Allerdings war gerade das PageRank-Verfahren ein wichtiger Faktor für den Erfolg der Suchmaschine Google, womit zumindest das Konzept des PageRank-Verfahrens immer noch grundlegend sein sollte.

2. Das PageRank-Konzept

Im Zuge der Entwicklung des World Wide Webs wurden verschiedene Verfahren zur Bewertung von Webseiten mit dem Ziel der Relevanzbeurteilung durch Suchmaschinen entwickelt. Ein aus unmittelbar einleuchtenden Gründen auch heute immer noch von praktisch allen Suchmaschinen genutzter Maßstab ist das Vorkommen eines Suchbegriffs in den Inhalten einer Webseite. Dieses Vorkommen wird nach den verschiedensten Kriterien wie etwa der relativen Häufigkeit des Vorkommens (der sog. Keyword-Dichte), den Stellen des Vorkommens des Suchbegriffs oder auch der Exponiertheit des Suchbegriffs im Dokument gewichtet.

Aus der Absicht, Suchmaschinen resistent gegen Webseiten zu machen, die auf der Basis von Analysen der inhaltsspezifischen Bewertungskriterien generiert wurden (Doorway Pages), entstand das Konzept der Link-Popularität. Dabei fließt die Anzahl der eingehenden Links für ein Dokument als ein grundsätzliches Kriterium für die Bedeutung einer Webseite in die Relevanzbeurteilung ein. Diesem Ansatz liegt zu Grunde, dass ein Dokument um so wichtiger ist, je häufiger es von anderen verlinkt wird. Hierdurch wird weitestgehend verhindert, dass automatisch generierte "suchmaschinenoptimierte" Webseiten ohne jeglich Einbindung in das WWW oben in den Suchmaschinenergebnissen erscheinen. Es zeigte sich allerdings, dass auch das Konzept der Link-Popularität schnell von Webmastern antizipiert werden konnte, indem sie von ebenso unbedeutenden, automatisch generierten Seiten eingehende Links für Doorway Pages schufen.

Im Gegensatz zum Konzept der Link-Popularität nutzt das PageRank-Konzept nicht einfach die absolute Anzahl eingehender Links für die Beurteilung der Bedeutung einer Webseite. Die Argumentation der Google-Gründer gegen das Konzept der einfachen Link-Popularität war, dass ein Dokument zwar bedeutsam ist, wenn es von vielen anderen verlinkt wird, nicht jedes verlinkende Dokument ist jedoch gleichwertig. Vielmehr sollte einem Dokument - völlig unabhängig von seinen Inhalten - ein hoher Rang zugewiesen werden, wenn es von anderen bedeutenden Dokumenten verlinkt wird.

Die Bedeutsamkeit eines Dokuments bestimmt sich im Rahmen des PageRank-Konzepts also aus der Bedeutsamkeit der darauf verlinkenden Dokumente. Deren Rang wiederum bestimmt sich ebenfalls aus dem Rang verlinkender Dokumente. Die Bedeutsamkeit eines Dokuments definiert sich stets rekursiv aus der Bedeutsamkeit anderer Dokumente. Da - wenn auch über viele hintereinanderfolgende Links hinweg - der Rang eines jeden Dokuments eine Auswirkung auf den Rang eines jeden anderen hat, beruht das PageRank-Konzept letztlich auf der Linkstruktur des gesamten Webs. Obwohl diese ganzheitliche Betrachtung des WWW es nicht vermuten lässt, gelang es Page und Brin das PageRank-Konzept mittels eines relativ trivialen Algorithmus umzusetzen.

Der PageRank Algorithmus

Der ursprüngliche PageRank-Algorithmus wurde von Lawrence Page und Sergey Brin mehrfach beschrieben. Er hat die folgende Form:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

Hierbei ist:
 

  • PR(A) der PageRank einer Seite A,
  • PR(Ti) der PageRank der Seiten Ti, von denen ein Link auf die Seite A zeigt,
  • C(Ti) die Gesamtanzahl der Links auf Seite Ti und
  • d ein Dämpfungsfaktor (Damping Factor),
    wobei 0 <= d <= 1 ist.

Das PageRank-Verfahren bewertet damit grundsätzlich nicht Websites in ihrer Gesamtheit, sondern basiert ausschließlich auf der Beziehung einzelner Webseiten zueinander. Der PageRank einer Seite A bestimmt sich dabei rekursiv aus dem PageRank derjenigen Seiten, von denen ein Link auf die Seite A zeigt.

Der PageRank der Seiten Ti, die auf eine Seite A verlinken, fließt nicht gleichmäßig in den PageRank von Seite A ein. Der PageRank einer Seiten T wird stets anhand der Anzahl C(T) der von Seite T ausgehenden Links gewichtet. Das bedeutet, dass je mehr ausgehende Links eine Seite T hat, umso weniger PageRank gibt sie an Seite A weiter.

Der anhand der Anzahl an ausgehenden Links gewichtete PageRank der Seiten Ti wird nun addiert. Dies hat zur Folge, dass jeder zusätzliche eingehende Link für eine Seite A stets den PageRank dieser Seite A erhöht.

Schließlich wird die Summe der gewichteten PageRanks der Seiten Ti mit dem Dämpfungsfaktor d, der stets zwischen 0 und 1 liegt multipliziert. Hierdurch wird das Ausmaß der Weitergabe des PageRanks von einer Seite auf einer andere verringert.

3.Das Random Surfer Modell

Lawrence Page und Sergey Brin bieten in ihren Veröffentlichungen eine sehr einfache, intuitive Rechtfertigung des PageRank-Algorithmus an. Sie betrachten PageRank-Verfahren als ein Modell zur Abbildung von Benutzer-Verhalten. Hierzu führen sie einen Zufalls-Surfer an, der von einer Webseite zur nächsten jeweils beliebige Links verfolgt, ohne dabei auf Inhalte zu achten.

Der Zufalls-Surfer befindet sich mit einer bestimmten Wahrscheinlichkeit auf einer Website, die sich aus deren PageRank herleiten lässt. Die Wahrscheinlichkeit, dass der Zufalls-Surfer nun einen bestimmten Link verfolgt, ergibt sich dann einzig und allein daraus, aus wievielen Links er die Auswahl hat. Aus diesem Grunde fließt der PageRank einer verlinkenden Seite stets nach der Anzahl Ihrer ausgehenden Links gewichtet in die PageRank Berechnung einer verlinkten Seite ein.

Die Wahrscheinlichkeit, dass der Zufalls-Surfer auf eine Seite gelangt, ist also die Summe der Wahrscheinlichkeiten, mit der er von einer verlinkenden Seite den entsprechenden Link verfolgt. Nun wird allerdings die Wahrscheinlichkeit, mit der der Zufalls-Surfer auf eine Seite gelangt, um den Faktor d gedämpft. Dies hat im Rahmen des Random Surfer Modells den Hintergrund, dass der Zufalls-Surfer nicht unendlich viele Links verfolgt. Nach einer bestimmten Zeit wird er gelangweilt und ruft eine beliebige andere Webseite auf.

Die Wahrscheinlichkeit, mit der der Zufalls-Surfer die Verfolgung von Links nicht abbricht und somit weiterklickt, wird durch den Dämpfungsfaktor d angegeben, der abhängig von der Höhe der Wahrscheinlichkeit einen Wert von 0 bis 1 annimmt. Je höher d ist, um so wahrscheinlicher ist es, dass der Zufalls-Surfer Links verfolgt. Da der Zufalls-Surfer nach dem Abbruch der Link-Verfolgung eine beliebige Seite aufruft, geht die Wahrscheinlichkeit mit er er dies tut, mit dem Wert (1-d) als Konstante in die Berechnung des PageRanks einer jeden Seite ein.

4. Abweichende Formulierung des PageRank-Algorithmus

Lawrence Page und Sergey Brin bieten in ihren Veröffentlichungen zwei unterschiedliche Versionen des PageRank-Algorithmus an. In dieser zweiten Version bestimmt sich der PageRank einer Seite A wie folgt:

PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

Hierbei ist N die Anzahl aller Seiten des Webs. Diese zweite Version des PageRank-Algorithmus unterscheidet sich allerdings nicht grundlegend von der ersten. In der zweiten Version beschreibt der PageRank einer Seite im Sinne des Random Surfer Modells lediglich die tatsächliche Wahrscheinlichkeit, mit der der Zufalls-Surfer nach dem Verfolgen vieler Links eine Seite erreichen wird. Dieser Algorithmus bildet damit eine Wahrscheinlichkeitsverteilung über alle Seiten des Webs ab. Die Summe aller PageRank-Werte des Webs ist damit bei dieser Version des Algorithmus gleich 1.

In der oben genannten, ersten Version erfolgt eine Gewichtung der Wahrscheinlichkeit des Besuchs einer Seite nach der Anzahl der Seiten des Webs. Demnach ist der PageRank in dieser Version im Grunde der Erwartungswert für den Besuch des Zufalls-Surfers auf einer Seite, wenn er hierfür Anläufe in genau der Höhe der Anzahl der Seiten des Webs nimmt. Bestünde das Web also aus 100 Seiten, und eine Seite hat einen PageRank von 2, so würde der Zufalls-Surfer sie bei 100 "Surfgängen" im Mittel zweimal erreichen.

Wie bereits erwähnt, unterscheiden sich die beiden Versionen des Algorithmus sich nicht grundlegend. Letztlich muss der PageRank einer Seite aus der Algorithmus-Version 2 lediglich mit der Anzahl der Webseiten multipliziert werden, um zum PageRank der Algorithmus-Version 1 zu gelangen. Selbst Page und Brin ist in Ihrer wohl bekanntesten Veröffentlichung "The Anatomy of a Large-Scale Hypertextual Web Search Engine" der Fehler unterlaufen, die erste Version des PageRank-Algorithmus als Wahrscheinlichkeitsverteilung zu charakterisieren, bei der die Summe der PageRank-Werte aller Seiten gleich eins sei.

Im Folgenden wird für die weiteren Betrachtungen der oben zuerst genannte Algorithmus verwandt. Dies hat den einfachen Hintergrund, dass Berechnungen hiermit wesentlich einfacher sind, da die Größe des Webs vollkommen außer Acht gelassen werden kann.
 

5. Die Eigenschaften des PageRank

Die Eigenschaften des PageRank sollen jetzt anhand eines Beispieles veranschaulicht werden.

Hierzu wird ein kleines 3-Seiten-Web aus den Seiten A, B und C betrachtet, wobei Seite A sowohl auf Seite B als auch auf Seite C verlinkt. Seite B verlinkt lediglich auf Seite C und Seite C wiederum verlinkt auf Seite A. Der Dämfungsfaktor d wird Angaben von Lawrence Page und Sergey Brin zufolge für tatsächliche Berechnungen üblicherweise auf 0.85 gesetzt. Der Einfachheit halber wird d an dieser Stelle ein Wert von 0.5 zugewiesen, wobei die Höhe von d zwar Auswirkungen auf den PageRank hat, das hier zu erläuternde Prinzip jedoch nicht beeinflusst. Es ergeben sich die folgenden Gleichungen für den PageRank der einzelnen Seiten:

PR(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))

Dieses Gleichungssystem lässt sich sehr einfach für den PageRank der einzelnen Seiten lösen. Es ergeben sich die folgenden Werte:

PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615

Es zeigt sich, dass die Summe der PageRanks aller Seiten gleich drei und somit gleich der Anzahl der Seiten ist. Dies ist keine spezifisches Ergebnis für unser Beispiel, da der PageRank Algorithmus einen Erwartungswert für den Besuch von Seiten bei Anläufen in Höhe der Anzahl der Seiten darstellt.

Für ein kleines 3-Seiten-Beispiel lässt sich ein Gleichungssystem unproblematisch lösen. Das tatsächliche WWW besteht jedoch mittlerweile aus mehreren Milliarden Webseiten, so dass die Lösung eines entsprechenden Gleichungssystems nicht mehr möglich ist.

6. Die iterative Berechnung des PageRank


Aufgrund der Größe des Webs erfolgt in der Praxis der Suchmaschine Google eine näherungsweise, iterative Berechnung des PageRank. Dies bedeutet, dass zunächst jeder Seite ein PageRank zugewiesen wird, und anschließend der PageRank aller Seiten in mehreren Berechnungsrunden ermittelt wird. Diese näherungsweise Berechung soll wiederum anhand unseres kleinen Beispiels demonstriert werden, wobei als Ausganswert für den PageRank einer jeden Seite zunächst 1 angenommen wird.


 

Iteration PR(A) PR(B) PR(C)
0 1 1 1
1 1 0.75 1.125
2 1.0625 0.765625 1.1484375
3 1.07421875 0.76855469 1.15283203
4 1.07641602 0.76910400 1.15365601
5 1.07682800 0.76920700 1.15381050
6 1.07690525 0.76922631 1.15383947
7 1.07691973 0.76922993 1.15384490
8 1.07692245 0.76923061 1.15384592
9 1.07692296 0.76923074 1.15384611
10 1.07692305 0.76923076 1.15384615
11 1.07692307 0.76923077 1.15384615
12 1.07692308 0.76923077 1.15384615



Es zeigt sich, dass sich in unserem Beispiel bereits nach sehr wenigen Iterationen eine sehr gute Näherung an die tatsächlichen Werte ergibt. Für die Berechnung des PageRanks für das komplette WWW werden von Lawrence Page und Sergey Brin ca. 100 Iterationen als hinreichend genannt.

Entscheidend ist, dass die Summe der PageRanks aller Seiten nach der Durchführung der iterativen Berechnung gegen die Anzahl aller Seiten konvergiert. Der durchschnittliche PageRank aller Seiten geht mithin gegen 1. Jede Seite hat einen minimalen PageRank von (1-d). Der theoretisch maximale PageRank einer Seite beträgt dN+(1-d), wobei N die Anzahl aller Webseiten ist. Dieser theoretische Wert käme zustande, wenn sämtliche Webseiten ausschließlich auf eine Seite verlinken, und auch diese wiederum ausschließlich auf sich selbst verlinkt.
nach Oben ...
zurück zur Home