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.
PageRank
und Google sind geschützte Marken der Google Inc., Mountain
View CA, USA. Das PageRank Verfahren unterliegt dem US Patent
6,285,999.
Copyright by pr.efactory.de
|
