Der PageRank-Algorithmus
Der ursprüngliche
PageRank-Algorithmus wurde von Lawrence Page und Sergey Brin mehrfach beschrieben.
Er hat die
folgende
Form:
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
Hierbei ist:
 |
PR(A) der PageRank einer Seite A, |
|
PR(Ti) der PageRank der Seiten Ti, von denen ein Link
auf die Seite A zeigt, |
|
C(Ti) die Gesamtanzahl der Links auf Seite Ti und |
|
d ein Dämpfungsfaktor (Damping Factor), wobei
0 <= d <= 1 ist. |
Das PageRank-Verfahren
bewertet damit grundsätzlich
nicht Websites in ihrer Gesamtheit, sondern basiert
ausschließlich auf der Beziehung einzelner Webseiten
zueinander. Der PageRank einer Seite A bestimmt sich dabei rekursiv aus
dem PageRank derjenigen Seiten, von denen ein Link auf die Seite A
zeigt.
Der PageRank der Seiten
Ti, die auf eine Seite A verlinken,
fließt nicht gleichmäßig in den PageRank
von Seite A ein. Der PageRank einer Seiten T wird stets anhand der
Anzahl C(T) der von Seite T ausgehenden Links gewichtet. Das bedeutet,
dass je mehr ausgehende Links eine Seite T hat, umso weniger PageRank
gibt sie an Seite A weiter.
Der anhand der Anzahl an
ausgehenden Links gewichtete PageRank der Seiten Ti wird nun addiert. Dies
hat zur Folge, dass jeder
zusätzliche eingehende Link für eine Seite A stets
den PageRank dieser Seite A erhöht.
Schließlich wird die Summe der gewichteten PageRanks
der Seiten Ti mit dem Dämpfungsfaktor d, der stets zwischen 0
und 1 liegt multipliziert. Hierdurch wird das Ausmaß der
Weitergabe des PageRanks von einer Seite auf einer andere verringert.
Das Random Surfer Modell
Lawrence Page und Sergey
Brin bieten in ihren
Veröffentlichungen eine sehr einfache, intuitive
Rechtfertigung des PageRank-Algorithmus an. Sie betrachten
PageRank-Verfahren als ein Modell zur Abbildung von Benutzer-Verhalten.
Hierzu führen sie einen Zufalls-Surfer an, der von einer
Webseite zur nächsten jeweils beliebige Links verfolgt, ohne
dabei auf Inhalte zu achten.
Der Zufalls-Surfer befindet
sich mit einer bestimmten Wahrscheinlichkeit auf einer Website, die sich
aus deren PageRank
herleiten lässt. Die Wahrscheinlichkeit, dass der
Zufalls-Surfer nun einen bestimmten Link verfolgt, ergibt sich dann
einzig und allein daraus, aus wievielen Links er die Auswahl hat. Aus
diesem Grunde fließt der PageRank einer verlinkenden Seite
stets nach der Anzahl Ihrer ausgehenden Links gewichtet in die PageRank
Berechnung einer verlinkten Seite ein.
Die Wahrscheinlichkeit,
dass der Zufalls-Surfer auf eine Seite gelangt, ist also die Summe der Wahrscheinlichkeiten,
mit der er von
einer verlinkenden Seite den entsprechenden Link verfolgt. Nun wird
allerdings die Wahrscheinlichkeit, mit der der Zufalls-Surfer auf eine
Seite gelangt, um den Faktor d gedämpft. Dies hat im Rahmen
des Random Surfer Modells den Hintergrund, dass der Zufalls-Surfer
nicht unendlich viele Links verfolgt. Nach einer bestimmten Zeit wird
er gelangweilt und ruft eine beliebige andere Webseite auf.
Die Wahrscheinlichkeit,
mit der der Zufalls-Surfer die Verfolgung von Links nicht abbricht und somit
weiterklickt, wird durch
den Dämpfungsfaktor d angegeben, der abhängig von der
Höhe der Wahrscheinlichkeit einen Wert von 0 bis 1 annimmt. Je
höher d ist, um so wahrscheinlicher ist es, dass der
Zufalls-Surfer Links verfolgt. Da der Zufalls-Surfer nach dem Abbruch
der Link-Verfolgung eine beliebige Seite aufruft, geht die
Wahrscheinlichkeit mit er er dies tut, mit dem Wert (1-d) als Konstante
in die Berechnung des PageRanks einer jeden Seite ein.
Abweichende Formulierung des
PageRank-Algorithmus
Lawrence Page und Sergey
Brin bieten in ihren
Veröffentlichungen zwei unterschiedliche Versionen des
PageRank-Algorithmus an. In dieser zweiten Version bestimmt sich der
PageRank einer Seite A wie folgt:
PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
Hierbei ist N die Anzahl
aller Seiten des Webs. Diese zweite Version des PageRank-Algorithmus unterscheidet
sich allerdings nicht
grundlegend von der ersten. In der zweiten Version beschreibt der
PageRank einer Seite im Sinne des Random Surfer Modells lediglich die
tatsächliche Wahrscheinlichkeit, mit der der Zufalls-Surfer
nach dem Verfolgen vieler Links eine Seite erreichen wird. Dieser
Algorithmus bildet damit eine Wahrscheinlichkeitsverteilung
über alle Seiten des Webs ab. Die Summe aller PageRank-Werte
des Webs ist damit bei dieser Version des Algorithmus gleich 1.
In der oben genannten,
ersten Version erfolgt eine Gewichtung der Wahrscheinlichkeit des Besuchs
einer Seite nach der Anzahl der
Seiten des Webs. Demnach ist der PageRank in dieser Version im Grunde
der Erwartungswert für den Besuch des Zufalls-Surfers auf
einer Seite, wenn er hierfür Anläufe in genau der
Höhe der Anzahl der Seiten des Webs nimmt. Bestünde
das Web also aus 100 Seiten, und eine Seite hat einen PageRank von 2,
so würde der Zufalls-Surfer sie bei 100 "Surfgängen" im Mittel zweimal
erreichen.
Wie bereits erwähnt, unterscheiden sich die beiden
Versionen des Algorithmus sich nicht grundlegend. Letztlich muss der
PageRank einer Seite aus der Algorithmus-Version 2 lediglich mit der
Anzahl der Webseiten multipliziert werden, um zum PageRank der
Algorithmus-Version 1 zu gelangen. Selbst Page und Brin ist in Ihrer
wohl bekanntesten Veröffentlichung "The Anatomy of a
Large-Scale Hypertextual Web Search Engine" der Fehler unterlaufen, die
erste Version des PageRank-Algorithmus als
Wahrscheinlichkeitsverteilung zu charakterisieren, bei der die Summe
der PageRank-Werte aller Seiten gleich eins sei.
Im Folgenden wird für die weiteren Betrachtungen der
oben zuerst genannte Algorithmus verwandt. Dies hat den einfachen
Hintergrund, dass Berechnungen hiermit wesentlich einfacher sind, da
die Größe des Webs vollkommen außer Acht
gelassen werden kann.
Die Eigenschaften des PageRank
Die Eigenschaften des PageRank sollen jetzt anhand eines
Beispieles veranschaulicht werden.
Hierzu wird ein kleines
3-Seiten-Web aus den Seiten A, B und C betrachtet, 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. Der Dämfungsfaktor d wird Angaben von
Lawrence Page und Sergey Brin zufolge für
tatsächliche Berechnungen üblicherweise auf 0.85
gesetzt. Der Einfachheit halber wird d an dieser Stelle ein Wert von
0.5 zugewiesen, wobei die Höhe von d zwar Auswirkungen auf den
PageRank hat, das hier zu erläuternde Prinzip jedoch nicht
beeinflusst. Es ergeben sich die folgenden Gleichungen für den
PageRank der einzelnen Seiten:
PR(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))
Dieses Gleichungssystem
lässt sich sehr einfach
für den PageRank der einzelnen Seiten lösen. Es
ergeben sich die folgenden Werte:
PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615
Es zeigt sich, dass die
Summe der PageRanks aller Seiten gleich drei und somit gleich der Anzahl
der Seiten ist. Dies ist keine
spezifisches Ergebnis für unser Beispiel, da der PageRank
Algorithmus einen Erwartungswert für den Besuch von Seiten bei
Anläufen in Höhe der Anzahl der Seiten darstellt.
Für ein kleines 3-Seiten-Beispiel lässt sich
ein Gleichungssystem unproblematisch lösen. Das
tatsächliche WWW besteht jedoch mittlerweile aus mehreren
Milliarden Webseiten, so dass die Lösung eines entsprechenden
Gleichungssystems nicht mehr möglich ist.
Die iterative Berechnung des PageRank
Aufgrund der Größe des Webs erfolgt in der
Praxis der Suchmaschine Google eine näherungsweise, iterative
Berechnung des PageRank. Dies bedeutet, dass zunächst jeder
Seite ein PageRank zugewiesen wird, und anschließend der
PageRank aller Seiten in mehreren Berechnungsrunden ermittelt wird.
Diese näherungsweise Berechung soll wiederum anhand unseres
kleinen Beispiels demonstriert werden, wobei als Ausganswert
für den PageRank einer jeden Seite zunächst 1
angenommen wird.
| Iteration |
PR(A) |
PR(B) |
PR(C) |
| 0 |
1 |
1 |
1 |
| 1 |
1 |
0.75 |
1.125 |
| 2 |
1.0625 |
0.765625 |
1.1484375 |
| 3 |
1.07421875 |
0.76855469 |
1.15283203 |
| 4 |
1.07641602 |
0.76910400 |
1.15365601 |
| 5 |
1.07682800 |
0.76920700 |
1.15381050 |
| 6 |
1.07690525 |
0.76922631 |
1.15383947 |
| 7 |
1.07691973 |
0.76922993 |
1.15384490 |
| 8 |
1.07692245 |
0.76923061 |
1.15384592 |
| 9 |
1.07692296 |
0.76923074 |
1.15384611 |
| 10 |
1.07692305 |
0.76923076 |
1.15384615 |
| 11 |
1.07692307 |
0.76923077 |
1.15384615 |
| 12 |
1.07692308 |
0.76923077 |
1.15384615 |
Es zeigt sich, dass sich
in unserem Beispiel bereits nach sehr wenigen Iterationen eine sehr gute
Näherung an die
tatsächlichen Werte ergibt. Für die Berechnung des
PageRanks für das komplette WWW werden von Lawrence Page und
Sergey Brin ca. 100 Iterationen als hinreichend genannt.
Entscheidend ist, dass
die Summe der PageRanks aller Seiten
nach der Durchführung der iterativen Berechnung gegen die
Anzahl aller Seiten konvergiert. Der durchschnittliche PageRank aller
Seiten geht mithin gegen 1. Jede Seite hat einen minimalen PageRank von
(1-d). Der theoretisch maximale PageRank einer Seite beträgt
dN+(1-d), wobei N die Anzahl aller Webseiten ist. Dieser theoretische
Wert käme zustande, wenn sämtliche Webseiten
ausschließlich auf eine Seite verlinken, und auch diese
wiederum ausschließlich auf sich selbst verlinkt.
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
|
