Weitere Einflussfaktoren im Rahmen des PageRank-Verfahrens

Es wurde bereits vielerorts diskutiert, ob für die PageRank-Berechnung seit der Veröffentlichung der wissenschaftlichen Arbeiten durch Lawrence Page und Sergey Brin weitere Kriterien als nur die einfache Link-Struktur des Webs für die Berechnung des PageRanks hinzugezogen wurden. Lawrence Page selbst skizziert in der Patentschrift zum PageRank-Verfahren die folgenden potentiellen Einflussfaktoren:

	Die Stärke der Hervorhebung eines Links
	Die Position eines Links innerhalb des Dokuments
	Die Distanz zwischen Webseiten
	Die Bedeutung einer verweisenden Seite
	Die Aktualität einer verweisenden Seite

Die Implementierung dieser weiteren Einflussfaktoren würde zunächst auf bessere Annäherung des Random Surfer Modells an tatsächliches Nutzerverhalten abzielen. Mit der Einbeziehung von Hervorhebung und Position eines Links geht man davon aus, das ein Benutzer nicht völlig wahllos klickt, sondern unabhängig vom Ankertext eher die deutlich erkennbaren und unmittelbar sichtbaren Links verfolgt. Mit der Berücksichtigung der anderen Faktoren könnte Google darüber hinaus eine weit größere Flexibilität in der Bestimmung der Bedeutung eines eingehenden Links für eine Webseite erreichen, als durch die bereits erwähnten Methoden.

Ob einzelne dieser Faktoren tatsächlich in das PageRank-Verfahren implementiert sind, ist empirisch kaum zu belegen, und soll deshalb an dieser Stelle auch nicht ausführlich diskutiert werden. Es soll vielmehr erörtert werden, auf welche Art und Weise weitere Einflussfaktoren in den PageRank-Algorithmus implementiert werden könnten und welche Möglichkeiten zur Einflussnahme auf den PageRank seitens Google sich hierdurch ergeben.

Modifizierung des PageRank-Algorithmus

Um weitere Faktoren in das PageRank-Verfahren einfliessen zu lassen, ist der ursprüngliche PageRank-Algorithmus wiederum zu modifizieren. Da wir davon ausgehen müssen, dass für die PageRank-Berechnung weiterhin zahlreiche Iterationen durchgeführt werden, ist hierbei allerdings zu berücksichtigen, dass im Sinne einer möglichst schnellen PageRank-Berechnung für die Einbeziehung weiterer Faktoren zusätzliche Datenbank-Zugriffe im Laufe der Iterationen weitestgehend vermieden werden sollten. Aus diesem Grunde bietet sich der folgende, modifizierte PageRank-Algorithmus an:

PR(A) = (1-d) + d (PR(T1)×L(T1,A) + ... + PR(Tn)×L(Tn,A))

Hier bei stellt L(Ti,A) eine Bewertung des Links, der von der Seite Ti auf die Seite A zeigt, dar. L(Ti,A) tritt damit an die Stelle der Gewichtung des PageRanks von Seite Ti nach der Anzahl deren ausgehender Links durch den Faktor 1/C(Ti). Der Wert L(Ti,A) würde sich aus mehreren einzelnen Faktoren zusammensetzen, die jedoch nur einmal ermittelt werden müssten und dann vor der eigentlichen PageRank-Berechnung in einen einzigen Wert einfließen. Hierdurch vergrößert sich die Anzahl der Datenbankzugriffe nicht, wobei allerdings angemerkt werden muss, dass durch die hier vorgeschlagene Modifikation des PageRank-Algorithmus im Laufe jeder Iteration bei der Bestimmung jedes einzelnen PageRanks ein Zugriff auf eine wesentlich größere Datenbank zu erfolgen hat, als im Falle des ursprünglichen PageRank-Algorithmus, da nun nicht mehr nur die Bewertung von Seiten (anhand der Anzahl ihrer ausgehenden Links) sondern die Bewertung jedes einzelnen Links in die Berechnung einfließt.

Unterschiedliche Bewertung von Links innerhalb einzelner Seiten

Zwei wesentliche von Lawrence Page in der Patentschrift zum PageRank-Verfahren genannte Bewertungskriterien für Links sind deren Grad der Hervorhebung und Position innerhalb eines Dokuments. Es handelt es sich hierbei also um Kriterien, die im Rahmen des Random Surfer Modells einzig die Wahrscheinlichkeit widerspiegeln, mit der der Zufalls-Surfer einen bestimmten Link auf einer Website in Relation zu einem anderen Link auf dieser Website verfolgt. Im ursprünglichen PageRank-Algorithmus entspricht diese Wahrscheinlichkeit dem Term (1/C(Ti)), wobei die Wahrscheinlichkeiten für das Verfolgen von Links von einer Seite dabei jeweils gleich waren.

Eine Zuweisung unterschiedlicher Wahrscheinlichkeiten für das Verfolgen von Links könnte beispielhaft etwa folgendermaßen erfolgen:

Wir betrachten ein Web aus den drei Seiten A, B und C. Jede der Seiten verlinkt jeweils auf jede andere. Links werden nach zwei Bewertungskriterien X und Y gewichtet. X stellt die Hervorhebung eines Links dar. X ist gleich 1, sofern der Links nicht hervorgehoben und gleich 2, sofern der Link etwa fett oder kursiv hervorgehoben ist. Y stellt die Position eines Links im Dokument dar. Y ist gleich 1, sofern der Link in der unteren Hälfte des Dokuments und gleich 3, sofern der Link in der oberen Hälfte des Dokuments erscheint. Nehmen wir einen multiplikativen Zusammenhang zwischen X und Y an, werden die Links aus unserem Beispielweb wie folgt bewertet:


 

X(A,B) × Y(A,B) = 1 × 3 = 3
X(A,C) × Y(A,C) = 1 × 1 = 1
X(B,A) × Y(B,A) = 2 × 3 = 6
X(B,C) × Y(B,C) = 2 × 1 = 2
X(C,A) × Y(C,A) = 2 × 3 = 6
X(C,B) × Y(C,B) = 2 × 1 = 2

Zur Ermittlung der einzelnen Faktoren L sind schließlich die Bewertungen der Links nicht mehr allein nach der Anzahl der ausgehenden Links zu gewichten. Vielmehr erfolgt eine Gewichtung nach der wiederum bewerteten Anzahl der ausgehenden Links. Hierdurch ergeben sich die folgenden Gewichtungsquotienten Z(Ti) für die einzelnen Seiten Ti:

Z(A) = X(A,B) × Y(A,B) + X(A,C) × Y(A,C) = 4
Z(B) = X(B,A) × Y(B,A) + X(B,C) × Y(B,C) = 8
Z(C) = X(C,A) × Y(C,A) + X(C,B) × Y(C,B) = 8

Die einzelnen Bewertungsfaktoren L(T1,T2) für einen Link von Seite T1 nach Seite T2 ergeben sich damit als

L(T1,T2) = X(T1,T2) × Y(T1,T2) / Z(T1)

und haben in unserem Beispiel die folgenden Werte:

L(A,B) = 0.75
L(A,C) = 0.25
L(B,A) = 0.75
L(B,C) = 0.25
L(C,A) = 0.75
L(C,B) = 0.25

Bei einem Dämpfungsfaktor d in Höhe von 0.5 ergeben sich damit die folgenden Gleichungen für die PageRank-Berechnung:

PR(A) = 0.5 + 0.5 (0.75 PR(B) + O.75 PR(C))
PR(B) = 0.5 + 0.5 (0.75 PR(A) + 0.25 PR(C))
PR(C) = 0.5 + 0.5 (0.25 PR(A) + 0.25 PR(B))

Aus der Lösung dieses Gleichungssystems folgen als PageRank-Werte für die einzelnen Seiten:

PR(A) = 819/693
PR(B) = 721/693
PR(C) = 539/693

Zuallererst sehen wir, dass Seite A den höchsten PageRank erhält. Dies ist darin begründet, dass Seite A sowohl von Seite B als auch von Seite C den jeweils stärker bewerteten Link erhält.

Es zeigt sich ferner, dass auch hier bei der Bewertung der einzelnen Links die Summe der PageRank-Werte aller Seiten mit 2079/693 gleich 3 und damit gleich der Anzahl der Seiten ist. Somit können die mittels des derart modifizierten PageRank-Algorithmus ermittelten Werte ohne weitere Normalisierung in die allgemeine Bewertung von Webseiten durch Google einfließen.

Unterschiedliche Bewertung von Links nach Eigenschaften der verweisenden Seite

Neben der unterschiedlichen Bewertung von Links innerhalb einer Seite führt Lawrence Page in der Patentschrift zum PageRank-Verfahren an, dass Links auch nach Kriterien gewichtet werden können, denen eine Bewertung der verweisenden Seite zu Grunde liegt. Dies scheint auf den ersten Blick überflüssig, da es bereits der Grundgedanke des PageRank-Konzepts ist, dass Links einen um so größeren Einfluss haben, je bedeutender die verlinkende Seite ist. Page und Brin erkannten allerdings sehr früh, dass ihr Algorithmus anfällig gegen das "künstliche Aufblähen" des PageRank einzelner Seiten ist.

Eine Beinflussung des PageRank kann in erster Linie dadurch erfolgen, dass Webmaster eine Vielzahl von Webseiten generieren, deren Links den PageRank so distribuieren, dass einzelne Seiten im System eine besondere Bedeutung erlangen. Diese Seiten können dann einen hohen PageRank inne haben, ohne dass von anderen Websites mit hoher Relevanz auf sie verlinkt wird. Hierdurch wird nicht nur das Konzept des PageRank unterwandert, sondern insbesondere auch der Suchmaschinenindex mit einer Vielzahl von Webseiten überflutet, die lediglich zum Zwecke der Beeinflussung des PageRank geschaffen wurden.

Als ein Mittel der Verhinderung dieser Form der Beinflussung zeigt Lawrence Page in seiner Patentschrift die Bewertung von Links anhand der Distanz zwischen verlinkender und verlinkter Seite auf. Hintergrund ist, dass je größer die Distanz zwischen zwei Seiten ist, um so geringer ist die Wahrscheinlichkeit, dass ein und die selbe Person beide Seiten kontrolliert. Kriterium der Distanz zwischen Seiten kann etwa sein, ob Sie auf der selben Domain liegen oder nicht. Damit würden interne Links weniger gewichtet als externe. Aber auch jedes andere Kriterium der Distanz käme laut Page in Frage, also etwa ob Seiten sich auf dem selben Webserver befinden. Letztlich sei auch gerade die Verlinkung durch Websites aus unterschiedlichen geographischen Regionen ein deutliches Indiz für die Relevanz einer Seite.

Als weiteres Indiz für die Bedeutung einer Seite nennt Page die Aktualität der verlinkenden Seite. Die Informationen einer Seite sind mit viel geringerer Wahrscheinlichkeit veraltet, je mehr kürzlich modifizierte Seiten auf sie verlinken. Dagegen bevorzugt das eigentliche PageRank-Verfahren wie auch jedes Verfahren der Messung der Link-Popularität eher ältere Dokumente, die erst im Laufe ihrer Existenz eine Vielzahl eingehender Links erhalten haben und mit einer geringeren Wahrscheinlichkeit als neue Dokumente kürzlich verändert wurden. Grundsätzlich könnten aktuelle Dokumente mittels der bereits erwähnten Gewichtung des Faktors (1-d) besser bewertet werden. Hierdurch erhielten sowohl die aktuellen Dokumente selbst als auch diejenigen Dokumente auf die sie verlinken einen höheren PageRank. Die Aktualität einer Seite ist allerdings nicht zwingend ein Indiz für die Qualität der auf Ihr präsentierten Informationen. Daher ist es unbedingt ratsam, wie von Page vorgeschlagen, nicht die Aktualität einer Seite selbst zu bewerten, sondern vielmehr die Aktualität ihrer eingehenden Links.

Schließlich nennt Page als Kriterium für die Bedeutung eines Links noch die grundsätzliche Bedeutung der verlinkenden Seite. Als Beispiel wird in der Patentschrift zum PageRank Verfahren der Link von der Root-Seite einer Domain genannt. Hier könnte allerdings letztlich seitens Google ganz willkürlich auf das PageRank-Verfahren Einfluss genommen werden.

Um die Bewertung verlinkender Seiten in den PageRank-Algorithnmus aufzunehmen, muss der Bewertungsfaktor aus unserem modifizierten PageRank-Algorithmus nunmehr aus mehreren Einzelfaktoren bestehen. Für einen Link von Seite Ti nach Seite A könnte er wie folgt notiert werden:

L(Ti,A) = K(Ti,A) × K1(Ti) × ... × Km(Ti)

Hierbei stellt K(Ti,A) die weiter oben vorgestellte Bewertung der einzelnen Links innerhalb einer Seite dar. Dazu erfolgt eine Bewertung der Seite Ti nach m Kriterien, die durch die Faktoren Kj(Ti) repräsentiert werden. Für eine Implementierung dieser Modifikationen muss im Falle der Bewertung von Seiten nun nicht mehr nur der PageRank-Algorithmus abgeändert werden, sondern auch das PageRank-Berechnungsverfahren. Dies soll wieder anhand eines Beispiels demonstriert werden.

Wir betrachten das 3-Seiten-Web aus den Seiten A, B und C, wobei Seite A sowohl auf Seite B als auch auf Seite C verlinkt. Seite B verlinkt auf Seite C und Seite C wiederum verlinkt auf Seite A. Alle ausgehenden Links einer Seite werden jeweils als gleichwertig betrachtet. Es erfolgt eine Bewertung der Links nach genau einem seitenspezifischen Kriterium. Ein Link von Seite C sei viermal bedeutender als ein Link von anderen Seiten. Nach entsprechender Gewichtung nach der Anzahl der Seiten ergibt sich das folgende Bild für unsere Bewertungsfaktoren:





 

K(A) = 0.5
K(B) = 0.5
K(C) = 2

Bei einem Dämpfungsfaktor d in Höhe von 0.5 ergeben sich die folgenden Gleichungen für die Berechnung der PageRank-Werte der einzelnen Seiten:

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

Die Lösung dieses Gleichungssystems ergibt die folgenden PageRank-Werte für die einzelnen Seiten:

PR(A) = 4/3
PR(B) = 2/3
PR(C) = 5/6

Es zeigt sich also, dass die Summe der PageRank-Werte nicht mehr gleich der Anzahl der Seiten ist. Dies liegt darin begründet, dass die erfolgte Gewichtung der Seitenbewertung nach der Anzahl der Seiten nicht korrekt war. Zur Ermittlung der korrekten Gewichtung müsste allerdings vorab die Linkstruktur des Webs antizipiert werden, was im Falle des WWW jedoch nicht möglich ist. Aus diesem Grunde ist bei der Bewertung von Links nach seitenspezifischen Faktoren der ermittelte PageRank zu normalisieren, damit kein unbegründet hoher oder geringer Einfluss des PageRank innerhalb der Gesamtbewertung von Seiten entsteht. Bei der iterativen PageRank-Berechnung hätte die Normalisierung nach jeder Iteration zu erfolgen, um unerwünschte Effekte zu minimieren.

Im Falle eines sehr kleinen Webs zeigen sich Verzerrungen des PageRank durch die Bewertungen von Links nach seitenspezifischen Kriterien sehr deutlich. Im Falle des tatsächlichen WWW dürften sich diese Verzerrungen weitestgehend ausgleichen. Es wäre allerdings zu befürchten, dass etwa die Bewertung der Distanz zwischen verlinkenden Webseiten durchaus zu Verzerrungen führen kann, da stark verlinkte Seiten sicherlich überdurchschnittlich dazu tendieren, aus unterschiedlichen geographischen Regionen verlinkt zu werden. Hier besteht allerdings die Möglichkeit zur Antizipation durch Erfahrungswerte aus vorangegangenen Berechnungszyklen, so dass die Normalisierung immer nur minimal sein müsste. Eine Einbeziehung zusätzlicher Bewertungskriterien in das PageRank-Verfahren ist in jedem Falle möglich, dabei allerdings mit einem erhöhten Rechenaufwand verbunden.

Themen-basierter PageRank

PageRank und Google sind geschützte Marken der Google Inc., Mountain View CA, USA. Das PageRank Verfahren unterliegt dem US Patent 6,285,999.

Sämtliche Inhalte dieser Website können im WWW wiedergegeben werden, sofern im unmittelbaren Zusammenhang Angaben zum Copyright erfolgen und ein direkter HTML-Link auf die entsprechende Seite unter pr.efactory.de gesetzt wird.