PageRank

Das PageRank-Verfahren (Page et al. 1998) ist nach seinem Erfinder Lawrence Page benannt und bildet eine wesentliche Grundlage der Suchmaschine Google (Brin u. Page 1998). PageRank ordnet jedem indexierten Dokument einen statischen PageRank-Wert zu, der also unabhängig von einer gestellten Suchanfrage besteht.
PageRank basiert auf dem Modell eines random surfer, also eines angenommenen Web-Nutzers, der das Web abwandert, indem er auf jeder gefundenen Seite wahllos einen Link verfolgt, um zur nächsten Seite zu kommen. Hier folgt er wieder einem Link, usw. Eine Ausnahme bildet die Möglichkeit, dass der Nutzer „sich langweilt“, die Seite verlässt und an einer neuen, zufällig gewählten Stelle des Netzes wieder einsteigt.
Der PageRank-Wert einer Seite soll die Wahrscheinlichkeit angeben, mit der dieser Nutzer auf diese Seite stößt.

Der klassische PageRank-Algorithmus

PageRank zählt die Anzahl der eingehenden Links auf eine Seite (die „backlinks"). Die Grundannahme lautet, dass stark verlinkte Seiten „wichtiger" sind als Seiten, auf die nur wenige Links verweisen (Page et al. 1998, 3). Allerdings können Seiten auch wichtig sein, wenn zwar nur wenige Links auf diese verweisen, diese Links aber von selbst besonders bedeutenden Seiten kommen. Es ist intuitiv verständlich, dass ein Link von der Homepage von Yahoo bedeutender ist als zehn Links von privaten Homepages. Deshalb geht das PageRank-Verfahren davon aus, dass eine Seite hoch bewertet werden soll, wenn die Summe der Wertigkeit der auf sie zeigenden Links hoch ist. (Page et al. 1998, 3)

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

Der PageRank einer Seite PR(A) wird aus den PageRank-Werten der auf diese Seite verweisenden Dokumente berechnet, wobei jede Seite nicht ihren eigenen PageRank-Wert weitergibt, sondern diesen auf die durch sie verlinkten Seiten verteilt. C gibt die Anzahl der ausgehenden Links auf einer Seite an. Eine Seite „vererbt" also ihren eigenen PageRank geteilt durch die Anzahl ihrer ausgehenden Links. Dadurch erfolgt ein Ausgleich zwischen Seiten, die viele ausgehende Links haben und solchen mit wenigen.
Für die Berechnung des PageRank einer Seite werden die PageRanks der verweisenden Seiten zusätzlich jeweils mit einem Dämpfungsfaktor reduziert, der zwischen 0 und 1 liegen kann. Die so gewonnenen PageRanks der auf eine Seite verweisenden Seiten werden addiert, dazugezählt wird noch die Subtraktion von Eins und dem Dämpfungsfaktor. So wird für jedes Dokument ein PageRank-Wert ermittelt, der später im Ranking der Dokumente angewendet wird.
Abbildung 8.2 zeigt eine einfache Berechnung der PageRank-Werte für ein Netz aus vier Webseiten, wobei in dieser vereinfachten Darstellung der Dämpfungsfaktor nicht berücksichtigt ist. Für jedes Dokument ist sein PageRank-Wert innerhalb des Kastens angegeben; der Wert, der auf ein verlinktes Dokument vererbt wird, ist an der jeweiligen Pfeilspitze angegeben.
Das erste Dokument (links oben in der Abbildung) hat selbst einen PageRank-Wert von 100 und zwei Links, die auf weitere Dokumente verweisen. Jedes dieser Dokumente erhält einen PageRank von 50 vererbt, also den halben Wert des Ursprungsdokuments. Das zweite Dokumente (rechts oben in der Abbildung) erhält so einerseits einen Wert von 50 vom ersten Dokument, andererseits weitere drei Punkte vom dritten Dokument (links unten). Dieses hat selbst einen PageRank-Wert von neun, den es allerdings auf drei ausgehende Links verteilt, also jedem den Wert drei vererbt.

Abb. 8.2. Einfache PageRank-Berechnung (Page et al. 1998, 4)

Deutlich wird in diesem Beispiel also, dass die Wertigkeit von Links sehr unterschiedlich sein kann. Im Beispiel ist ein Link vom ersten Dokument offensichtlich wesentlich mehr wert als einer vom dritten Dokument. Diese unterschiedliche Bewertung der Links ist die große Stärke des PageRank-Verfahrens.
Die Schwierigkeit in der Berechnung der PageRank-Werte liegt in der großen Menge der zu berücksichtigenden Verweise; in die Berechnung müssen schließlich alle Verweise aus allen erfassten Dokumenten eingehen. Zu Beginn der Berechnung wird jedem Dokument der gleiche Ausgangswert zugeteilt, wobei dieser keinen Einfluss auf die späteren Endwerte hat, die Wahl des Ausgangswerts aber die Performance verbessern kann (Page et al. 1998, 7). Basierend auf den Ausgangswerten werden für jedes Dokument nun in einem iterativen Prozess die PageRank-Werte immer weiter angenähert, wobei sich die Werte von Durchgang zu Durchgang immer weniger verändern, so dass ein Cut-off-Wert festgelegt werden kann, nach dem die Berechnung abbricht.
Als Ergebnis ist nun jedem Dokument ein statischer Wert zugeteilt, der in das Ranking als „Qualitätsindikator" mit eingehen kann. Dieser Wert ist also unabhängig von einer gestellten Suchanfrage und bleibt dem Dokument fest zugeordnet. Ein großer Vorteil dieses statischen PageRank-Werts liegt darin, dass dieser in dem Moment, in dem eine Suchanfrage gestellt wird, bereits festliegt und entsprechend keine Rechenzeit notwendig wird. Anfragebezogene linktopologische Algorithmen sind aufgrund der komplexen Berechnungen nur eingeschränkt im Echtbetrieb einsetzbar.
Allerdings stellt der statische PageRank-Wert auch den Hauptkritikpunkt an dem Verfahren dar (vgl. u.a. Haveliwala 2002): Der statische Wert bevorzugt im Ranking Dokumente, die allgemein populär sind, egal ob sie für die Suchanfrage relevant sind oder nicht. Nur die ergänzenden textstatistischen Verfahren bestimmen das ob der Relevanz, PageRank ergänzt das Ranking um den Faktor der allgemeinen Bedeutung einer Seite. Ob die als allgemein am bedeutendsten angesehene Seite aber auch die für die Suchanfrage relevanteste Seite ist, bleibt dahingestellt. Chakrabarti (2003, 212) spricht in diesem Zusammenhang von einer künstlichen Entkoppelung von Relevanz und Qualität bei PageRank.
Ein weiterer Kritikpunkt ist der Bezug des Wertes auf einzelne Seiten anstatt auf ganze Sites. Mandl (2003a, [8]) gibt folgendes Beispiel:
„So kann es passieren, dass eine qualitativ sehr gute Site insgesamt hohe Werte erreicht, dass allerdings auf die darin enthaltene Linksammlung wenig verwiesen wird und sie dadurch keine hohe Autorität zugewiesen bekommt."
Zu ähnlichen Problemen kann es bei neuen Dokumenten kommen, wenn diesen noch kein PageRank-Wert zugeordnet wurde. Sie erhalten zwar theoretisch durch die Verlinkung innerhalb ihrer eigenen Site sofort bei Auffinden durch die Suchmaschine einen Wert von der verlinkenden Seite vererbt. De facto ist dies aber nicht der Fall, da die aufwendige Neuberechnung aller PageRank-Werte nur in größeren Intervallen durchgeführt werden kann. Neuere Seiten werden so im Ranking potenziell benachteiligt; im Anwendungsfall (in der Suchmaschine Google) scheinen aber Ausgleichsfaktoren berücksichtigt zu werden, die neue Dokumente bevorzugen (vgl. Lewandowski 2004b, 310).

Weiterentwicklungen: Reranking

Wie gezeigt wurde, bevorzugt eine statische Qualitätsbewertung von Dokumenten, wie sie im PageRank-Verfahren eingesetzt wird, generell stark verlinkte Dokumente, wobei das Qualitätsurteil unabhängig von der tatsächlichen Suchanfrage ist. Um diesen Nachteil auszugleichen, können Verfahren des Reranking eingesetzt werden. Diese berechnen aufgrund der Linkstruktur einer bereits durch andere Verfahren (z.B. textstatistische Verfahren oder Verfahren, die eine statische Qualitätsbewertung mit einbeziehen) ermittelten Treffermenge die Qualität der gefundenen Dokumente hinsichtlich der Suchanfrage und sortieren die bereits vorhandene Trefferliste auf dieser Basis neu. Solche Verfahren sind vor allem als sinnvolle Ergänzung zu PageRank zu sehen.
Im Patent von Bharat (2004) wird ein Reranking-Verfahren beschrieben. Zu Beginn wird ein regulärer Rankingalgorithmus eingesetzt. Aus der gewonnenen Ergebnismenge wird ein Ausschnitt gebildet; im Patent werden als Beispiel die Top 1000 Dokumente genannt. Für jedes dieser Dokumente werden alle Dokumente innerhalb der Trefferliste ermittelt, die auf dieses verweisen. Mit Hilfe der ermittelten Hyperlinkstruktur innerhalb der Treffermenge wird mit dem üblichen Verfahren der Linktopologie ein sog. local score ermittelt. Dieser Wert wird am Ende wieder mit dem ursprünglichen Rankingwert (old score) verbunden, so dass ein neues Ranking entsteht. Der Ablauf der Ermittlung der neuen Rankingwerte der Dokumente ist schematisch in Abbildung 8.3 dargestellt. Zu beachten ist, dass das Reranking nach diesem Verfahren für jedes einzelne Dokument berechnet werden muss.
Der Vorteil dieses Rankingverfahrens ist, dass bei der Ermittlung des Local Score nur diejenigen Seiten berücksichtigt werden, die tatsächlich auch das Thema der Suchanfrage behandelt. Denn die Treffermenge wurde ja bereits durch den Term-Document-Abgleich ermittelt. Im Gegensatz zu Verfahren wie PageRank, die jeden Hyperlink werten, egal ob er von einer thematisch verwandten Seite kommt oder nicht, ergeben sich Qualitätsvorteile. Interessant ist weiterhin, dass im Patent auch die Möglichkeit beschrieben wird, mit der Zielseite verwandte Seiten, die einen Hyperlink auf diese enthalten, bei der Bewertung auszuschließen. Das beschriebene Verfahren hierfür ist das, welches im „Hilltop"-Algorithmus beschrieben wird (vgl.Kapitel 8.4).
Problematisch an diesem Verfahren erscheint die benötigte Zeit, um die Local Scores zu errechnen. Diese Berechnung muss ja für jede Suchanfrage „on the fly" geschehen und kann nicht wie bei statischen Verfahren wie PageRank vorher geleistet werden.

Abb. 8.3. Reranking nach Bharat (2004)