Der Yahoo-Bonus und seine Auswirkungen auf
die Suchmaschinen-Optimierung
Vielfach wird angenommen,
das einige Websites von Google eine spezielle PageRank-Bewertung erhalten,
die einen manuellen Eingriff
erfordert und sich nicht direkt aus dem ursprünglichen
PageRank-Algorithmus ergibt. Zu diesen Websites zählen z.B.
die Verzeichnisse Yahoo und Open Directory Project (dmoz.org). Im
Rahmen der Suchmaschinen-Optimierung hätte diese Annahme zur
Folge, dass ein Eintrag in die genannten Verzeichnisse für den
PageRank von besonderer Bedeutung ist.
 Ein häufig genannter Ansatz für die
besondere Bewertung spezieller Websites ist, dass diesen für
die iterative Berechnung des PageRank ein höherer Startwert
zugewiesen wird. Diese mögliche Vorgehensweise soll anhand
eines sehr einfachen Beispiels überprüft werden. Wir
betrachten ein 2-Seiten-Web, bei dem jede der beiden Seiten jeweils
ausschließlich auf die andere verlinkt. Der einen Seite wird
ein Startwert von 10 zugewiesen, der anderen ein Startwert von 1. Der
Dämpfungsfaktor d wird in diesem Beispiel auf 0.1 gesetzt, da
bei einem geringen Dämpfungsfaktor der PageRank im Zuge der
Iterationen schneller konvergiert. Damit ergeben sich folgende Formeln
für die PageRank-Berechnung:
PR(A) = 0.9 + 0.1 PR(B)
PR(B) = 0.9 + 0.1 PR(A)
Die PageRank-Werte ergeben sich im Laufe der Iterationen wie
folgt:
| Iteration |
PR (A) |
PR (B) |
| 0 |
1 |
10 |
| 1 |
1.9 |
1.09 |
| 2 |
1.009 |
1.0009 |
| 3 |
1.00009 |
1.000009 |
Es wird unmittelbar ersichtlich,
dass die PageRank-Werte trotz
der Vergabe besonderer Startwerte für die Berechnung jeweils
gegen 1 konvergieren, so wie es auch ohne die Vergabe spezieller
Startwerte zu erwarten gewesen wäre. Bei ausreichend vielen
Iterationen hat somit der Startwert keinerlei Auswirkung auf den
PageRank. Auswirkungen würden sich lediglich ergeben, wenn nur
wenige Iterationen durchgeführt werden. Hier ist allerdings zu
bedenken, dass sich etwa in unserem Beispiel die PageRank-Relation
zwischen den beiden Seiten direkt nach der ersten Iteration umkehrt.
Hierzu sei angemerkt, dass für die rekursive Berechnung
jeweils die PageRank-Werte der aktuellen Iteration und nicht etwa der
vorherigen genutzt wurden. Wären die Werte der vorherigen
Iteration genutzt worden, würde die PageRank-Relation
alterieren.
Modifikation des PageRank-Algorithmus
Dass eine Zuweisung spezieller
Startwerte ohne Auswirkungen bleibt, bedeutet jedoch nicht, dass Websites
nicht durch einen Eingriff
in den PageRank-Algorithmus bevorzugt werden können. So
beschreibt Lawrence Page bereits in seiner Patentschrift zum
PageRank-Verfahren (United States Patent 6,285,999) die
Möglichkeit für die besondere Bewertung spezieller
Webseiten. Der Ausgangspunkt für seine Überlegungen
ist, dass der Zufalls-Surfer aus dem Random Surfer Modell zwar mit
einer starr festgelegten Wahrscheinlichkeit aufhört, Links zu
verfolgen, dann aber im Gegensatz zum ursprünglichen
PageRank-Algorithmus nicht mehr mit der gleichen Wahrscheinlichkeit
eine Webseite für einen erneuten Start seines Surf-Vorgangs
auswählt. Es entspricht schließlich dem normalen
Verhalten eines Internet-Nutzers, dass er als Ausgangspunkt mit einer
höheren Wahrscheinlichkeit etwa eines der genannten
Verzeichnisse Yahoo oder ODP wählt.
Damit die besondere Bewertung
einzelner Webseiten in dieser
Form in den ursprünglichen PageRank Algorithmus
einfließen kann, muss er um einen weiteren Erwartungswert
erweitert werden. Die entsprechende Formel hat dann folgendes Aussehen:
PR(A) = E(A) (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
Hierbei ist (1-d) jetzt
die Wahrscheinlichkeit, mit der der Zufalls-Surfer das Weiterverfolgen von
Links abbricht und E(A) die nach
der Anzahl der Webseiten gewichtete Wahrscheinlichkeit, mit der der
Zufalls-Surfer die Seite A danach aufruft. Bei E handelt es sich dabei
wiederum um einen Erwartungswert, dessen Durchschnitt über
alle Seiten gleich 1 ist, damit der Durchschnitt der PageRank-Werte
weiterhin gegen 1 konvergiert und nicht etwa durch die besondere
Bewertung spezieller Seiten schwankt und somit der PageRank einen
unregelmäßigen Einfluss auf die Gesamtbewertung von
Seiten einnimmt.
In unserem Beispiel liege
nach dem Abbruch des Surfvorgangs durch den Zufalls-Surfer die Wahrscheinlichkeit
für den Aufruf
von Seite A bei 10% und die Wahrscheinlichkeit für den Aufruf
von Seite B bei 90%. Damit ist bei einem 2-Seiten-Web E(A)=0.2 und
E(B)=1.8. Für die Ermittlung der PageRank Werte der beiden
Seiten ergeben sich bei einem Dämpfungsfaktor d=0.5 hierdurch
die folgenden Gleichungen:
PR(A) = 0.2 × 0.5 + 0.5 × PR(B)
PR(B) = 1.8 × 0.5 + 0.5 × PR(A)
Die Lösung dieses
Gleichungssystems ergibt die
folgenden PageRank-Werte:
PR(A) = 11/15
PR(B) = 19/15
Die Summe der beiden PageRank-Werte
liegt weiterhin bei 2. Die
höhere Wahrscheinlichkeit für das Aufrufen von Seite
B nach dem Abbruch spiegelt sich in ihrem höheren
PageRank-Wert wider. Die gleichmäßige Verlinkung der
beiden Seiten untereinander vermindert jedoch ganz deutlich die
Auswirkung der höheren Aufrufwahrscheinlichkeit auf den
PageRank.
Es ist also möglich, eine besondere Gewichtung
einzelner Seiten in den PageRank-Algorithmus einfließen zu
lassen, ohne dass dessen Charakter grundsätzlich
verändert werden müsste. Fraglich bleibt jedoch, nach
welchen Kriterien die Gewichtung erfolgen kann. In der Patentschrift
zum PageRank-Verfahren nennt Lawrence Page hierzu explizit die Nutzung
tatsächlichen Benutzerverhaltens. Daten zum
tatsächlichen Nutzerverhalten werden von Google über
die Google Toolbar gesammelt. Das besondere hierbei ist, dass nicht
einmal allzu große Datenmengen verarbeitet werden
müssten, wie dies der Fall wäre, wenn eine Bewertung
ausschließlich auf Nutzerverhalten basieren würde.
Eine begrenzte Stichprobe wäre durchaus ausreichend, um
zumindest die 1.000 oder 10.000 wichtigsten Anlaufstellen im Web zu
ermitteln. Der PageRank-Algorithmus wäre dann in der Lage,
über die Link-Struktur des Webs die Lücken zu
füllen.
Die Ausführungen zum Einfließen
tatsächlichen Benutzerverhaltens in das PageRank-Verfahren
sind natürlich pure Spekulation. Ob überhaupt eine
besondere Gewichtung spezieller Seiten stattfindet, wird letztlich ein
Geheimnis der Google-Verantwortlichen bleiben.
Dennoch Zuweisung bestimmter Startwerte?
Obwohl die Zuweisung bestimmter
Startwerte für die
PageRank-Berechnung bei hinreichend vielen Iterationen wirkungslos
für das Ergebnis der Berechnung bleibt, kann eine
entsprechende Vorgehensweise durchaus sinnvoll sein.
Wir betrachten hierzu unser
3-Seiten-Beispiel aus den Seiten A, B und C, 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. Den Dämfungsfaktor d setzen wir in
diesem Falle für die Berechnungen auf 0.75. Hierdurch ergeben
sich die folgenden Gleichungen für die iterative Berechnung
des PageRanks der einzelnen Seiten:
PR(A) = 0.25 + 0.75 PR(C)
PR(B) = 0.25 + 0.75 (PR(A) / 2)
PR(C) = 0.25 + 0.75 (PR(A) / 2 + PR(B))
Grundsätzlich muss
den einzelnen Seiten kein Startwert vor Beginn der Iterationen zugewiesen
werden. Sie haben in
diesem Falle einen Wert von 0 und es ergibt sich das folgende Bild:
| Iteration |
PR(A) |
PR(B) |
PR(C) |
| 0 |
0 |
0 |
0 |
| 1 |
0.25 |
0.34375 |
0.60156 |
| 2 |
0.70117 |
0.51294 |
0.89764 |
| 3 |
0.92323 |
0.59621 |
1.04337 |
| 4 |
1.03253 |
0.63720 |
1.11510 |
| 5 |
1.08632 |
0.65737 |
1.15040 |
| 6 |
1.11280 |
0.66730 |
1.16777 |
| 7 |
1.12583 |
0.67219 |
1.17633 |
| 8 |
1.13224 |
0.67459 |
1.18054 |
| 9 |
1.13540 |
0.67578 |
1.18261 |
| 10 |
1.13696 |
0.67636 |
1.18363 |
| 11 |
1.13772 |
0.67665 |
1.18413 |
| 12 |
1.13810 |
0.67679 |
1.18438 |
| 13 |
1.13828 |
0.67686 |
1.18450 |
| 14 |
1.13837 |
0.67689 |
1.18456 |
| 15 |
1.13842 |
0.67691 |
1.18459 |
| 16 |
1.13844 |
0.67692 |
1.18460 |
| 17 |
1.13845 |
0.67692 |
1.18461 |
| 18 |
1.13846 |
0.67692 |
1.18461 |
| 19 |
1.13846 |
0.67692 |
1.18461 |
| 20 |
1.13846 |
0.67692 |
1.18461 |
| 21 |
1.13846 |
0.67692 |
1.18461 |
| 22 |
1.13846 |
0.67692 |
1.18462 |
Bei einer Zuweisung eines
Startwertes von 1 ergibt sich das
folgende Bild für die Durchführung der Iterationen:
| Iteration |
PR(A) |
PR(B) |
PR(C) |
| 0 |
1 |
1 |
1 |
| 1 |
1 |
0.625 |
1.09375 |
| 2 |
1.07031 |
0.65137 |
1.13989 |
| 3 |
1.10492 |
0.66434 |
1.16260 |
| 4 |
1.12195 |
0.67073 |
1.17378 |
| 5 |
1.13034 |
0.67388 |
1.17928 |
| 6 |
1.13446 |
0.67542 |
1.18199 |
| 7 |
1.13649 |
0.67618 |
1.18332 |
| 8 |
1.13749 |
0.67656 |
1.18398 |
| 9 |
1.13798 |
0.67674 |
1.18430 |
| 10 |
1.13823 |
0.67684 |
1.18446 |
| 11 |
1.13835 |
0.67688 |
1.18454 |
| 12 |
1.13840 |
0.67690 |
1.18458 |
| 13 |
1.13843 |
0.67691 |
1.18460 |
| 14 |
1.13845 |
0.67692 |
1.18461 |
| 15 |
1.13845 |
0.67692 |
1.18461 |
| 16 |
1.13846 |
0.67692 |
1.18461 |
| 17 |
1.13846 |
0.67692 |
1.18461 |
| 18 |
1.13846 |
0.67692 |
1.18461 |
| 19 |
1.13846 |
0.67692 |
1.18462 |
Wird nunmehr den Seiten
ein initialer PageRank zugewiesen, der
der tatsächlichen PageRank-Verteilung etwas mehr entspricht
(1.1 für Seite A, 0.7 für Seite B und 1.2
für Seite C), ergibt sich das folgende Bild:
| Iteration |
PR(A) |
PR(B) |
PR(C) |
| 0 |
1.1 |
0.7 |
1.2 |
| 1 |
1.15 |
0.68125 |
1.19219 |
| 2 |
1.14414 |
0.67905 |
1.18834 |
| 3 |
1.14126 |
0.67797 |
1.18645 |
| 4 |
1.13984 |
0.67744 |
1.18552 |
| 5 |
1.13914 |
0.67718 |
1.18506 |
| 6 |
1.13879 |
0.67705 |
1.18483 |
| 7 |
1.13863 |
0.67698 |
1.18472 |
| 8 |
1.13854 |
0.67695 |
1.18467 |
| 9 |
1.13850 |
0.67694 |
1.18464 |
| 10 |
1.13848 |
0.67693 |
1.18463 |
| 11 |
1.13847 |
0.67693 |
1.18462 |
| 12 |
1.13847 |
0.67692 |
1.18462 |
| 13 |
1.13846 |
0.67692 |
1.18462 |
Es zeigt sich, dass je
näher die zugewiesenen
Startwerte der tatsächlichen Verteilung kommen, die
PageRank-Werte offenbar um so schneller konvergieren. Damit
wären weniger Iterationen für die PageRank-Berechnung
erforderlich, was insbesondere angesichts eines stets wachsenden Webs
die Lieferung von auf einer aktuelleren Datanbasis gestützten
Suchmaschinenergebnissen ermöglichen kann. Ausgangspunkt
für eine hinreichend exakte Annahme könnten dabei
für Seiten, die bereits den jeweils vorhergegangenen
Berechnungszyklus durchlaufen haben, die PageRank-Werte aus diesem
vorhergegangenen Berechnungszyklus sein. Neu in den Index aufgenommenen
Seiten könnte dann ein initialer PageRank von 1 zugewiesen
werden, der sich dann bereits nach der ersten Iteration sehr schnell
dem tatsächlichen Zustand angleicht.
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
|
