PR10 - PageRank10

PageRank 4
PageRank 5
PageRank 6
PageRank 7
PageRank 8
PageRank 9
PageRank 10

Der Yahoo- & ODP-Bonus und seine Auswirkungen:

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:

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:

Bei einer Zuweisung eines Startwertes von 1 ergibt sich das folgende Bild für die Durchführung der Iterationen:

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:

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.