Suchmaschinen beginnen ihre Arbeit damit, spiders auszuschicken, die das World Wide Web durchforsten, den Inhalt von Webseiten in Datenbanken speichern und auf ihrem Weg allen Hyperlinks folgen, denen sie begegnen. Ziel dieser emsigen Tätigkeit ist es, Inhalte und Vernetzungsstruktur des WWW in einer - mehr oder weniger vollständigen - "Momentaufnahme" abzubilden und für die Auswertung von Suchanfragen zu benutzen. Jede Anfrage löst eine Suche nach Textstellen in den erfassten Daten aus und wird in Form einer Liste von Treffern beantwortet. Seit den frühen Tagen des WWW stellt sich dabei die Frage: in welcher Reihenfolge werden die Treffen dem Anfragesteller präsentiert? Wie kann bewerkstelligt werden, dass die Liste der Treffer mit den "relevanten" und "wichtigen" Webseiten beginnt? Dieses Problem wurde - in einer für BenutzerInnen befriedigenden Weise - zuerst von der Suchmaschine Google gelöst. Die Idee besteht darin, jede erfasste Webseite - zunächst ganz unabhängig von jeglicher Suchanfrage - mit einem Bewertungsindex zu versehen, d.h. Webseiten nach ihrer "Wichtigkeit" zu ordnen. Neben anderen Kriterien (um die es uns hier nicht gehen soll) ist dieses Ranking die wichtigste Grundlage für die Reihung der Treffer. Googles Bewertungsmethode
PageRank wurde im Jahr
1998 von Sergey Brin und Lawrence Page an der Stanford University entwickelt.
Obwohl nicht alle Details offengelegt wurden, ist die Grundidee bekannt.
Ihr wenden wir uns nun zu.
Ausgangspunkt ist das WWW als vernetztes System. Es besteht aus elektronischen Dokumenten (die wir einfach Webseiten nennen), und die Hyperlinks (kurz: Links), d.h. Verweise auf andere derartige Dokumente enthalten können. Enthält eine Webseite x einen Link, der auf die Webseite y verweist, so sagen wir einfach, dass "x auf y verweist". Um die Sache nicht komplizierter als nötig zu machen, nehmen wir an, dass alle Webseiten bekannt sind und nur statische (von Benutzer-Eingaben unabhängige) Daten beinhalten. Insbesondere soll von jeder Webseite x eindeutig feststehen, auf welche anderen Webseiten sie verweist, und welche anderen Webseiten auf x verweisen. Das ist ein klarer Fall für einen gerichteten Graphen, dessen Ecken die Webseiten und dessen (gerichtete, als Pfeile gezeichnete) Kanten die Hyperlinks darstellen. Die elementaren Beziehungsstrukturen sind:
Gerichtete Kanten dürfen nicht doppelt vorkommen. (Enthält die Seite x zwei Links auf y, so wird das nur einmal gezählt). Ein kleines Spielzeug-WWW sieht beispielsweise so aus: Den Webseiten (Ecken) haben wir die Namen x1, x2,...x6 gegeben. Worin könnte nun ein Bewertungsschema von Webseiten, das lediglich die durch Hyperlinks definierte Vernetzungsstruktur des WWW ausnutzt, bestehen? Wie kann festgestellt werden, wie "relevant" eine Webseite x ist?
Formalisieren wir diese Idee. Für jede Webseite x definieren wir:
Weiters bezeichnen wir den Bewertungsindex (englisch: PageRank) einer Seite x, den wir im Folgenden definieren wollen, mit R(x). Die zuvor verbal formulierte Idee wurde von Brin und Page in die Form
gegossen. Dabei ist d ein "Dämpfungsfaktor", der üblicherweise gleich 0.85 gesetzt wird (in jedem Fall aber größer als 0 und kleiner als 1 sein muss). Wir werden weiter unten ein paar Worte über ihn sagen. Ist jeder Webseite ein solcher Bewertungsindex zugeordnet, so werden die Treffer einer Suchanfrage in der Reihenfolge absteigender Werte diese Größe präsentiert. Nehmen wir Formel (1) ein bisschen unter die Lupe: Die Summe erstreckt sich über die Elemente von S(x), d.h. über alle Seiten, die auf x verweisen. Jede solche Seite y liefert einen Beitrag, der proportional zu ihrem "Wert" R(y) und umgekehrt proportional zur Anzahl C(y) der von ihr wegweisenden Links ist. (Man kann diese Summe auch so betrachten: Jede Seite y trägt zu anderen Seiten insgesamt einen Beitrag R(y) bei, der gleichmäßig auf alle Seiten, auf die y verweist, aufgeteilt wird). Zuletzt wird gewichtet: Der Beitrag zu R(x) von anderen Seiten (die soeben besprochene Summe) wird mit d multipliziert, und ein kostenloser Beitrag, den jede Seite automatisch bekommt, wird addiert. (Man beachte, dass die Summe der beiden Gewichte 1 - d und d gleich 1 ist). Wir sehen sofort, dass der Bewertungsindex auch auf der rechten Seite vorkommt - dort allerdings für die Elemente von S(x). Handelt es sich also bei (1) um eine Rekursionsformel? Leider nein, denn wenn x einen Link auf eine der in S(x) enthaltenen Seiten enthält, hängt deren Bewertungsindex von jenem von x ab, womit R(x) auch auf der rechten Seite von (1) steht. Tatsächlich haben wir es hier mit einem Gleichungssystem gigantischen Ausmaßes zu tun, denn der Formel (1) muss genau genommen der Zusatz "für alle x ÎE" gegeben werden. Jede Webseite x trägt eine Variable R(x) bei: Die Anzahl der Variablen ist gleich der Anzahl aller Webseiten! Dieses Gleichungssystem ist linear-inhomogen, und kein Computer könnte es in einer angemessenen Zeit exakt lösen. Allerdings stehen für derartige Gleichungen näherungsweise Lösungsmethoden zur Verfügung. Bevor wir aber darüber nachdenken, stellt sich eine viel grundsätzlichere Frage, nämlich, ob das System überhaupt (und wenn ja, wieviele) Lösungen besitzt! Exerzieren wir das zuerst anhand des oben angegebenen Spielzeug-WWW durch. Es ergeben sich folgende Gleichungen:
Hier widerspiegelt sich die allgemeine in (1) definierte Struktur : Jede Seite trägt mit jedem Link zu anderen Seiten bei. So kommt etwa R(x5)/3 in dieser Eigenschaft 3 mal vor. Wie eine kleine Berechnung ergibt, besitzt das System für 0 < d < 1 genau eine Lösung. Wir geben sie hier wieder für d = 0.85 (auf zwei Stellen gerundet) wieder:
Seite x5
gewinnt das Rennen, gefolgt von x3.
(Intuitiv hätte man das nicht erwartet, da auf x3 mehr Links
weisen als auf x5).
Stellen wir also nun die Frage, ob die Berechung immer so problemlos funktioniert.
Das Gleichungssystem (1) kann in Matrixform dargestellt werden. Dazu werden die Webseiten, d.h. die Ecken, in beliebiger Weise durchnummeriert: Wir nennen sie x1, x2,...xn. Nun kann eine n×n-Matrix A (die so genannte Link-Matrix) definiert werden, deren Eintragungen die Beiträge 1/C(y) von Gleichung (1) sind:
Insbesondere sind alle Diagonalelemente von A gleich 0. Alle von 0 verschiedenen Eintragungen einer Zeile sind untereinander gleich. Die Summe der Eintragungen der j-ten Zeile ist 1, wenn von xj zumindest ein Link ausgeht, ansonsten 0. Für unser obiges Spielzeug-WWW sieht die Matrix A so aus:
Weiters werden die Bewertungsindizes zu einem n-dimensionalen Zeilenvektor R = (R(x1), R(x2),...R(xn)) zusammengefasst, und D bezeichnet den n-dimensionalen Zeilenvektor, dessen Komponenten alle gleich 1 - d sind. Gleichung (1) kann dann in der Form
geschrieben werden, wobei das Produkt R A im Sinne der Matrizenmultiplikation zu bilden ist. Bezeichnet I die n×n-Einheitsmatrix, so wird das zu
Ein solches System besitzt genau dann eine eindeutige Lösung R, wenn die Matrix I - d A invertierbar ist. (Die Lösung ist dann klarerweise durch R = D (I - d A)-1 gegeben). Satz: Ist 0 < d < 1, so ist die Matrix I - d A invertierbar. Beweis:
Damit ist gezeigt, dass das Gleichungssystem (1) für jede denkbare Struktur des WWW genau eine Lösung besitzt: Ist d einmal gewählt, bekommt jede Webseite einen wohldefinierten Bewertungsindex. Jedes R(x) hat mindestens den Wert 1 - d, ist also immer positiv. Nach oben sind die Bewertungsindizes durch die Größe des Web beschränkt. Übungsaufgaben:
Um die Bewertungsmethode besser zu verstehen, fragen wir nun, wozu der "Dämpfungsfaktor" d in Formel (1) dient. Wäre die natürliche Wahl nicht d = 1? Der Zweck der Größe d besteht darin, eine Pathologie zu vermeiden. Angenommen, eine Webseite x3 hat einen gewissen, von 0 verschiedenen Bewertungsindex. Nun werden zwei Seiten x1 und x2 hinzugefügt und folgendermaßen verlinkt: Der Rest des WWW "hängt" gewssenmaßen an x3 - wir haben ihn hier nur angedeutet. Sehen wir uns die Sache quantitativ an: Mit (1) lauten die Gleichungen für R(x1) und R(x2) so:
Was ändert
sich durch die Hinzufügung von x1
und x2
im restlichen Web? Da x3
nun einen wegweisenden Link mehr
besitzt als vorher, wiegt seine Stimme für die Seiten,
auf die es bisher schon verwiesen hat, ein bisschen weniger (C(x3)
ist um 1
gewachsen), aber man würde sich keine dramatischen Änderungen
erwarten. Wird allerdings d = 1
gesetzt, so ergibt sich aus (8)
aber
während der Wert von R(x3) durch das Hinzufügen von x1 und x2 nicht berührt wird. Wir sehen, dass diese Ausdrücke für d = 1 nicht wohldefiniert sind. Ist d sehr nahe bei 1, so bekommen x1 und x2 ungerechtfertigterweise einen hohen Bewertungsindex. Um ihn ein bisschen zu "dämpfen" - daher der Name "Dämpfungsfaktor" -, wird mit Augenmaß ein mittlerer Wert für d gewählt.
Das Gleichungssystem (1) näherungsweise zu lösen, ist gar nicht so schwierig. Das von Google verwendete Verfahren ist ein iteratives: Zunächst werden die erfassten Seiten (in beliebiger Weise) durchnummeriert, und dann wird Gleichung (1) der Reihe nach auf die Elemente x, d.h. die Webseiten angewandt. Wann immer für ein auf der rechten Seite vorkommendes y noch kein Bewertungsindex berechnet wurde, wird dieser gleich einem beliebigen Anfangswert (beispielsweise 1 - d) gesetzt. Wann immer zuvor ein (Näherungs-)Wert für R(y) berechnet wurde, wird dieser verwendet. Sind alle Seiten auf diese Weise behandelt, wird die gesamte Prozedur wiederholt, und nach einer genügend großen Anzahl von Duchgängen (Google benötigt dafür etwa 50 und führt die Berechnung in mehreren Stunden durch) ändern sich die Bewertungsindizes kaum mehr und werden abgespeichert. Von Zeit zu Zeit werden alle Bewertungsindizes auf den neuesten Stand gebracht. Für kleine Spielzeug-WWWs ist es nicht schwierig, dieses Verfahren in Form eines Computerprogramms zu implementieren.
Googles Bewertungskonzept
hat also einen gut durchdachten Hintergrund, und der Erfolg dieser Suchmaschine
zeigt, dass es sich auch in der Praxis bewährt.
Texte der Entwickler von PageRank:
Auf zahlreichen Seiten wird diskutiert, wie Websites gestaltet werden müssen, um möglichst hohen Bewertungsfaktoren zu erzielen. Beispiele: Zwei Kurzmeldungen über kommerziell motivierte Manipulationsversuche von PageRank: |
¬ Von Bäumen, Wurzeln und Blättern, Tieren und Menschen |
Übersicht |
Der Bayessche Satz der Wahrscheinlichkeistrechnung ® |