PageRank – Das Herzstück der Google-Technologie
In den folgenden Kapiteln wird das dominierende Verfahren zur Relevanzbewertung von Dokumenten, Googles PageRank, vorgestellt. Es soll ein möglichst breiter Überblick über alle Aspekte des Verfahrens gegeben werden. Neben dem theoretischen Ansatz von PageRank wird der zugrundeliegende Algorithmus behandelt. Für die Relevanzoptimierung von Webdokumenten ist eine detaillierte Kenntnis dieses Verfahrens hilfreich.
5.1 Theoretischer Ansatz von PageRank
PageRank (PR – zur Entstehung und Begriffsklärung vgl. Kapitel 3.1.1)
„[...] basiert auf der in der akademischen Welt geltenden Prämisse, dass die Wichtigkeit einer Forschungsarbeit daran gemessen werden kann, wie oft sie in anderen Arbeiten zitiert wird“ (Calishain & Dornfest, 2003, S. 330).
Diese Prämisse wurde von den beiden Google-Gründern Brin und Page einfach auf das WWW übertragen. Die Wichtigkeit eines Webdokuments lässt sich also an der Anzahl der Hyperlinks messen, die von anderen Webdokumenten darauf verweisen (Calishain & Dornfest, 2003, S. 330).
Google stellt das Kernprinzip von PageRank selbst wie folgt dar:
„Im Wesentlichen interpretiert Google ein Link von Seite A auf Seite B als ’Votum’ von Seite A für Seite B. Google bewertet die Wichtigkeit einer Seite nach den erzielten Voten. Außerdem analysiert Google die Wichtigkeit der Seite, die das Votum abgegeben hat. Dabei hat ein Votum von einer Seite, die selbst als ’wichtig’ gewertet wird, ein größeres Gewicht und somit größeren Einfluss auf die Bewertung anderer Seiten. Wichtige, qualitativ hochwertige Seiten werden von PageRank höher eingestuft und demnach auch in den Ergebnissen an einer vorderen Position aufgeführt“ (Google, 2003d).
Die Gewichtung eines Votums ist bei Google also davon abhängig, welchen PageRank und damit wie viele eigene Votes das verweisende Webdokument erhalten hat. Der PageRank selbst drückt sich als Ergebnis in einem numerischen Wert aus (Glöggler, 2003, S. 82) und wird durch einen Algorithmus berechnet (vgl. Kapitel 5.2).
5.2 Der PageRank-Algorithmus
Das PageRank-Verfahren kann an Hand des 1997 veröffentlichten Algorithmus erläutert werden. Es ist verständlich, dass der ursprünglich veröffentlichte Algorithmus an die fortschreitende Entwicklung im WWW angepasst wurde und ständig modifiziert wird (Glöggler, 2003, S. 83).
5.2.1 Definition des PageRank-Algorithmus
Der ursprüngliche PageRank-Algorithmus wurde von den Google-Gründern Larry Page und Sergey Brin wie folgt definiert (Glöggler, 2003, S. 83):
PR(A) = (1 – d) + d(PR(T1)/C(T1) + ….PR(Tn)/C(Tn))
Hierbei ist:
PR(A) = der PageRank Wert von A berechnet aus allen eingehenden Verweisen.
A = das Dokument für den der PageRank Wert ermittelt wird.
d = ein Dämpfungsfaktor zwischen 0 und 1 (oftmals ~ 0,85).
PR(T1) = der PageRank Wert des Dokuments T1 das auf A verweist.
C(T1) = die Gesamtanzahl aller ausgehenden Verweise von T1.
„PR(TN)/C(Tn) bedeutet, dass der Verweiswert für jede Seite die auf A zeigt, aus dem PageRank der Seite n, unter Berücksichtigung der Anzahl aller ausgehenden Verweise von Tn berechnet wird“ (Glöggler, 2003, S.83).
Aus der Formel wird ersichtlich, dass es sich bei PageRank um eine iterative Berechnung des Wertes PR(A) handelt, da zur Berechnung zunächst alle PageRank-Werte PR(n) derjenigen Dokumente erforderlich sind, die auf A verweisen (Glöggler, 2003, S. 83).
Ein neu indexiertes Dokument besitzt also zunächst keinen PageRank. Diesem Problem wird mit der Zuordnung eines initialen Wertes begegnet, welcher durch Statistische Gewichtungsmodelle wie TF (vgl. Kapitel 4.2.2) oder einer differenzierten Bewertung der Position von Schlüsselwörtern (vgl. Kapitel 4.2.4) bestimmt werden kann. Der Dämpfungsfaktor d stellt innerhalb des Algorithmus eine Individualisierungsvariable dar und reflektiert den Faktor, den ein Dokument einem anderen Dokument von dem eigenen Wert zuweisen kann. Die Individualisierungsvariable dient zur Feineinstellung der Berechnungsmethode und bedeutet, dass ein Dokument einem anderen Dokument durch einen ausgehenden Verweis nicht seinen vollen Wert zuweisen kann. (Glöggler, 2003, S. 84).
5.2.2 Iterative Berechnung des PageRanks
Das iterative Verfahren der PageRank-Berechnung soll an Hand eines Beispiels mit den vier Dokumenten A, B, C, D verdeutlicht werden:
In der Ausgangssituation erhält jedes Dokument zur Vereinfachung den PageRank-Wert 1. Die unterschiedlichen, ausgehenden Verweise werden durch die Pfeile dargestellt. Zunächst wird der Dämpfungsfaktor d mit einem Wert von 0,85 angewendet.
Der PageRank-Wert für die Dokumente wird dann wie folgt berechnet (Glöggler, 2003, S. 84f):
· Dokument A: Der um d bereinigte Wert für Verweise von A ist
d * PR(TA) = 1 * 0,85 = 0,85. Da A auf zwei Dokumente verweist, ist
d (PR(TA)/C(TA)) = 0,85 / 2 = 0,425. Als Ergebnis des iterativen Prozesses wird also den Dokumenten B und C jeweils der Wert 0,425 zu ihren bisherigen Werten zugewiesen.
· Dokument B: Dokument B besitzt nur einen ausgehenden Verweis. B weist also dem Dokument C am Ende des iterativen Prozesses den Wert 1 x 0,85 = 0,85 zu.
· Dokumente C und D: Dokument C besitzt einen ausgehenden Verweis auf A, weshalb der Wert des Verweises auf A gleichfalls 0,85 ist. Analog ergibt sich der Wert für den Verweis von D auf C.
In Abbildung 13 wird ersichtlich wie sich die einzelnen PageRank-Werte der Dokumente nach der ersten Iteration entwickeln. Da der Kern des PageRank-Verfahrens darauf beruht, dass besser verlinkte Dokumente auch einen höheren Wert zugewiesen bekommen, wird der iterative Prozess mindestens ein zweites Mal durchgeführt. Bei erneuter Anwendung des Verfahrens ergeben sich folgende PageRank-Werte:
Abbildung 14: PageRank – zweite Iteration (Glöggler, 2003, S. 86)
Das Ergebnis zeigt auf, dass die Dokumente auf die am häufigsten verwiesen wird, den höchsten PageRank-Wert erhalten. Dokument D erhält keinen Verweis von einem anderen Dokument und weist deshalb auch bei mehrmaligen Iterationen immer nur den initialen Wert aus (Glöggler, 2003, S. 86).
Bereits nach wenigen Iterationen ergibt sich eine sehr gute Näherung an die tatsächlichen Werte. Um den PageRank für das komplette WWW zu berechnen werden von Larry Page und Sergey Brin ca. 100 Iterationen als hinreichend genannt (Sobek, 2002).
5.2.3 Das Random Surfer Modell
Die Google-Gründer rechtfertigen in ihren Veröffentlichungen den PageRank-Algorithmus mit einem Modell zur Abbildung des Benutzer-Verhaltens, dem sog. Random Surfer Modell. Dabei führen sie einen Zufalls-Surfer an, der von einer Webseite zur nächsten jeweils beliebige Verweise verfolgt, ohne dabei auf die Inhalte zu achten (Sobek, 2002).
Die Wahrscheinlichkeit mit der sich der Zufalls-Surfer auf einer Webseite befindet, lässt sich aus dem PageRank der Webseite herleiten. Ein bestimmter Verweis wird von dem Zufalls-Surfer nun verfolgt, wobei sich die Wahrscheinlichkeit, welcher Verweis verfolgt wird, einzig und allein aus der Anzahl der Verweise ergibt, aus denen der Benutzer auswählen kann. Aufgrund dessen fließt der PageRank einer verweisenden Webseite stets nach der Anzahl der ausgehenden Verweise gewichtet in die Berechnung des PageRanks einer Webseite, auf die verwiesen wird, ein (Sobek, 2002).
Die Wahrscheinlichkeit, dass der Zufalls-Surfer auf eine Webseite gelangt, ist also die Summe der Wahrscheinlichkeiten, mit der er von einer verweisenden Webseite den entsprechenden Verweis verfolgt. Die Wahrscheinlichkeit mit der ein Zufalls-Surfer auf eine Webseite gelangt wird um den Faktor d gedämpft. Die Dämpfung erfolgt aufgrund der Tatsache, dass ein Zufalls-Surfer nicht unbegrenzt viele Verweise verfolgt, sondern nach einer bestimmten Zeit eine beliebige andere Webseite aufruft. Je höher d ist, um so wahrscheinlicher ist es, dass der Zufalls-Surfer Verweise verfolgt. Da nach dem Abbruch der Verweis-Verfolgung eine beliebige Webseite aufgerufen wird, geht die Wahrscheinlichkeit mit der ein Benutzer dies durchführt, mit dem Wert (1-d) als Konstante in die Berechnung des PageRanks jeder Webseite mit ein (Sobek, 2002).
5.2.4 Weitere Einflussfaktoren im Rahmen des PageRank-Verfahrens
Für die Berechnung des PageRanks sind noch weitere Einflussfaktoren als nur die einfache Verweis-Struktur des WWW zu berücksichtigen. Larry Page selbst skizziert in der Patentschrift (Page, 1998) zum PageRank-Verfahren die folgenden potentiellen Einflussfaktoren (Sobek, 2002):
· Die Stärke der Hervorhebung eines Verweises
· Die Position eines Verweises innerhalb des Dokuments
· Die Distanz zwischen Webseiten
· Die Bedeutung eines verweisenden Dokuments
· Die Aktualität eines verweisenden Dokuments
Welche dieser Faktoren tatsächlich in das PageRank-Verfahren implementiert sind, ist empirisch kaum zu belegen. Die Implementierung würde zunächst auf bessere Annäherung des Random Surfer Modells (vgl. Kapitel 5.2.3) an tatsächliches Nutzerverhalten abzielen. Durch die Einbeziehung von Hervorhebung und Position eines Verweises wird berücksichtigt, dass ein Benutzer nicht völlig unüberlegt einen Verweis anklickt, sondern unabhängig vom Ankertext eher deutlich erkennbare und unmittelbar sichtbare Verweise verfolgt. Durch die anderen Faktoren könnte Google eine weit größere Flexibilität in der Bestimmung der Bedeutung eines eingehenden Verweises für eine Webseite erreichen (Sobek, 2002).
Glöggler sieht neben der Anzahl der eingehenden Verweise insbesondere die Qualität der verweisenden Seite als weiteren Einflussfaktor an:
„Die Qualität einer Seite kann sich z.B. durch ihre besondere Bedeutung im Web oder durch eine thematische Ähnlichkeit zum Verweis ausdrücken. Besondere qualitative Bedeutung für Google haben in diesem Zusammenhang intellektuell bewertete Webkataloge wie z.B. Yahoo oder der Katalog des Open Directory Project, die manuell einen besonders hohen Page-Rank-Wert zugeordnet bekommen haben“ (Glöggler, 2003, S. 86).
5.2.5 Problematik des Konzepts
Google erzielt durch das PageRank-Verfahren hervorragende Suchergebnisse. Allerdings bringt das Konzept auch eine Reihe von Problemen mit sich. Neue Webseiten können zu Beginn nur durch den kombinierten Einsatz weiterer Gewichtungsmethoden, wie beispielsweise dem Term Frequency Algorithmus (vgl. Kapitel 4.2.2) oder einer differenzierten Gewichtung von Keywords in Abhängigkeit ihrer Lage (vgl. Kapitel 4.2.4), eine relativ gute Platzierung bei Google erhalten (Glöggler, 2003, S. 182).
Mittelfristig werden bei einem dominierenden Einsatz des Verfahrens bereits bekannte Webseiten bevorzugt. Hochwertige, aber weniger bekannte Webauftritte werden dementsprechend benachteiligt. Google und andere Suchmaschinen, die Link Popularity einsetzen, begegnen dem Problem mit einer mittlerweile reduzierten Dominanz des Verfahrens und setzen weiterhin auch auf Statistische Gewichtungsmodelle (vgl. Kapitel 4.2). Im Hinblick auf die Relevanzoptimierung stellt PageRank aber nach wie vor das entscheidende Verfahren zur Relevanzbewertung von Dokumenten dar (Glöggler, S. 178-182).
5.3 Möglichkeiten den PageRank einzusehen
Für Webseiten-Betreiber ist es wichtig den aktuellen PageRank der eigenen Webdokumente zu kennen, um dadurch auch die Wirksamkeit von Relevanzoptimierungen kontinuierlich überprüfen zu können. In der Suchergebnisliste von Google (vgl. Kapitel 4.1.3) wird der numerische PageRank-Wert allerdings nicht angezeigt. Um diesen in Erfahrung zu bringen ist entweder eine Suche im Google-Verzeichnis oder die Nutzung der Google Toolbar erforderlich.
5.3.1 PageRank-Wert über das Google-Verzeichnis
Das Google-Verzeichnis ermöglicht eine katalogbasierte Suche, wobei Webseiten bestimmten Kategorien zugeordnet sind. Die Kategorien enthalten wiederum Unterkategorien. Der Aufbau ist dem Verzeichnis von Yahoo ähnlich. In der tiefsten Ebene wird eine Trefferliste mit direkten Links angezeigt, wobei der PageRank als kleiner, grüner Farbbalken links neben dem Link [1] dargestellt wird (Wimmeroth & Brochhagen, 2003, S. 19). Die Links werden nach absteigendem PageRank [2] aufgelistet (Google, 2003i):
Die Anzeige erfolgt auf einer Skala von 1 bis 7 (höchster Wert = 7), wobei der genaue numerische Wert nicht angezeigt wird. Er kann aber über die zweigeteilte Balkengrafik bzw. die Breite von deren Einzelgrafiken bestimmt werden (Sobek, 2002).
5.3.2 PageRank-Wert über die Google-Toolbar
Die Google Toolbar ist ein Browser-Plugin für den Microsoft Internet Explorer, welches komfortable Suchfunktionen bereitstellt. Zum Funktionsumfang zählt die Darstellung des PageRanks der aktuell besuchten Webseite (vgl. Abb. 16). Im Gegensatz zum Google Directory werden bei der Toolbar Abstufungen zwischen den numerischen Werten 0 bis 10 vorgenommen (höchster Wert = 10). Die Toolbar kann kostenlos von Google bezogen werden (Google, 2004f).
Dieser Artikel ist ein kleiner Auszug meiner Studienarbeit “Relevanzoptimierung und Ranking-Verfahren der Suchmaschine Google”
Download der kompletten Studienarbeit (mit Abbildungen):
http://www.wissen24.de/vorschau/25665.html
Mehr Info zu PageRank – Das Herzstück der Google-Technologie
