Weitere Einflussfaktoren für den PageRank™:
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 PageRank™ 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 PageRank™ 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 PageRank™
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 einer Seite:
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:
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.
Bei 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.
|
