Fotostrecke

Google-Algorithmus: Das Page-Rank-Verfahren

Foto: DARREN STAPLES/ REUTERS

Numerator Wie Google mit Milliarden Unbekannten rechnet

Ein Leben ohne Suchmaschinen? Für alle, die viel im World Wide Web unterwegs sind, eine geradezu absurde Vorstellung. Bei der Berechnung der Trefferlisten nutzt Google ein erstaunlich simples mathematisches Verfahren, das sogar Milliarden von Internetseiten in den Griff bekommt.

Wer bei Google einen Suchbegriff eintippt, bekommt binnen Sekundenbruchteilen die Ergebnisse angezeigt. Eigentlich erstaunlich, besteht das Web doch aus einem unüberschaubaren Wust an Web-Seiten. Dass die Suchmaschine Google so schnell Trefferlisten ausspucken kann, hängt auch mit einem mathematischen Algorithmus zusammen, mit dem jede einzelne Web-Seite immer wieder neu bewertet wird.

Page Rank heißt das Verfahren, das Google permanent durchführt. Die Schätzungen zufolge 30 bis 50 Milliarden Web-Seiten im Google-Index werden dabei immer wieder in eine Rangliste sortiert. Das entscheidende Kriterium beim Page Rank sind Links, die auf eine Web-Seite führen. Link ist jedoch nicht gleich Link: Kommt er von einer hoch gerankten Seite, dann erbt auch die verlinkte Seite einen Teil des Rankings dieser Seite.

Mathematisch gesehen, ist Googles Page Rank von 30 Milliarden Web-Seiten nichts anderes als die Lösung eines linearen Gleichungssystems mit 30 Milliarden Unbekannten. Das klingt zunächst nach einer kaum lösbaren Aufgabe, sie ist mithilfe leistungsstarker Computer aber zu meistern.

Das Konzept des Zufalls-Surfers

Die beiden Google-Gründer Sergey Brin und Larry Page haben das Page-Rank-Verfahren schon vor über zehn Jahren entwickelt . Letztlich steckt dahinter das Konzept eines Surfers, der sich zufällig durchs Web bewegt. Wie groß ist die Wahrscheinlichkeit, dass er sich zu einem bestimmten Zeitpunkt auf einer bestimmten Web-Seite befindet? Diese Wahrscheinlichkeit entspricht dem Page Rank der Seite.

Der Zufalls-Surfer startet auf einer beliebigen Web-Seite und klickt dann mit einer Wahrscheinlichkeit von d einen der Links an, die auf dieser Seite zu finden sind (0

Mit welcher Wahrscheinlichkeit treffen wir den Surfer auf der Web-Seite a? Brin und Page haben zwei Fälle unterschieden:

  1. Der Surfer hat das Klicken abgebrochen und landet durch direkte Eingabe der Web-Seite zufällig auf a. Wenn es im Netz genau N Web-Seiten, gibt, dann beträgt die Wahrscheinlichkeit für diesen Fall (1-d)/N.
  2. Der Surfer kommt von einer anderen Web-Seite, wir nennen sie i, über einen direkten Link zu a. Wir wissen ja bereits, dass unser Zufallsnutzer nur mit einer Wahrscheinlichkeit von d überhaupt Links folgt. In die Berechnung fließt außerdem ein, wie viele Links ci es überhaupt auf der Seite i gibt und wie groß die Wahrscheinlichkeit pi ist, dass sich der Surfer überhaupt auf der Web-Seite i befindet. Die Chance, dass der Surfer über den Link von der Seite i zur Seite a kommt, ist deshalb d*pi/ci. Wenn wir zudem annehmen, dass genau k der insgesamt N Seiten auf a verlinken, ist die Wahrscheinlichkeit dafür, dass der Surfer über einen dieser k Links zu a kommt gleich d(p1/c1 + p2/c2 + … +pk/ck)

Fassen wir nun die beiden Fälle zusammen, dann ist die Google-Formel komplett:

pa = (1-d)/N + d(p1/c1 + p2/c2 + … +pk/ck)

Letztlich haben die Google-Gründer mit ihrer Formel festgelegt, dass jene Seiten, die beim zufälligen Surfen häufiger angesteuert werden, auch höher gewertet werden. Eine Vereinfachung - aber eine sehr erfolgreiche. Denn heute dominiert Google den Suchmaschinenmarkt unangefochten, was sehr viel mit der revolutionären Suchtechnologie zu tun hat.

Ausgerechnet: Der Page Rank für ein Mini-Web aus drei Seiten

Ein simples Beispiel eines Mini-Internets aus drei Web-Seiten verdeutlicht, wie dieses Ranking-System in der Praxis funktioniert. Von der Seite A führt ein Link zu B, von B je einer zu A und C. Von C gibt es nur eine Verknüpfung zu A (siehe Abbildung). Damit erhalten wir folgendes Gleichungssystem:

pA = (1-d)/3 + d(pB/2 + pC)
pB = (1-d)/3 + d(pA)
pC = (1-d)/3 + d(pB/2)

Nun lösen wir das Gleichungssystem und verwenden dabei d=0,15, ein Wert, den Google nach eigenen Angaben in der Ranking-Berechnung nutzt.

pA = 0,2833 + 0,075 pB + 0,15 pC
pB = 0,2833 + 0,15 pA
pC = 0,2833 + 0,075 pB

Setzt man den Ausdruck für pB aus Gleichung zwei in die erste und in die dritte Gleichung ein, und den Ausdruck für pC dann wiederum in die erste, erhält man die Lösung:

pA = 0,355
pB = 0,336
pC = 0,308

Wir haben gesehen, dass bei unserem Mini-Web aus drei Web-Seiten letztlich ein lineares Gleichungssystem mit drei Unbekannten gelöst werden muss. Bei 30 Milliarden Web-Seiten besteht das System aus 30 Milliarden Gleichungen mit 30 Milliarden Unbekannten. Man kann einen solchen Gleichungskoloss übrigens auch als quadratische Matrix darstellen und steckt damit mittendrin in der Matrizenrechnung. Für alle, die damit vertraut sind: Der gesuchte Page Rank entspricht dann dem sogenannten Eigenvektor der Matrix.

Suchmaschinenoptimierung als Geschäftsmodell

Bei der Lösung dieses gigantischen Gleichungssystems nutzt Google ein iteratives Verfahren. Das heißt, dass jeder einzelnen Seite ein mehr oder weniger willkürlicher Page Rank zugewiesen und in die rechte Seite der Gleichungen eingesetzt wird. Daraus erhält man neue Page-Rank-Werte, die wiederum eingesetzt werden, und so weiter. Nach etwa hundert Iterationen kommt man auf diese Weise auch bei Systemen mit Millionen Gleichungen der exakten Lösung sehr nah.

Damit ist aber noch nicht erklärt, wie die Trefferliste einer Google-Anfrage zustande kommt. Der Page Rank einer Seite ist nur einer von mittlerweile 200 bis 300 Faktoren, die in die Berechnung einfließen. Hinzu kommen etwa die Textinhalte der Web-Seite, im HTML-Code steckende Schlüsselwörter (Tags), der Titel der Seite und weitere Kriterien wie beispielsweise der Zeitpunkt der letzten Aktualisierung.

Die Details der Trefferlistenberechnung hält Google geheim, etwa welches Gewicht Schlüsselwörter im Vergleich zum Seitentitel haben. Allerdings können Experten durch den Vergleich von Web-Seiten und Trefferlisten Rückschlüsse auf die aktuelle Kalkulationsmethode ziehen - und damit sogar Geld verdienen. Suchmaschinenoptimierung  heißt das Geschäft, bei dem Web-Seiten so lange an den gerade angewandten Google-Algorithmus angepasst werden, bis sie bei Suchanfragen immer möglichst weit oben in der Trefferliste landen. Ein ständiges Katz- und Mausspiel, denn Google betreibt bei seinen Algorithmen ein permanentes Feintuning.

An der eigentlichen Page-Rank-Berechnung hat sich seit dem Start von Google bis heute kaum etwas geändert. Allerdings greift Google mittlerweile in Einzelfällen ein, wenn das Ranking durch sogenannte Linkfarmen massiv manipuliert wird. Das sind Tausende verschiedener Web-Seiten, die mit dem alleinigen Zweck betrieben werden, durch eine Vielzahl von Links zu einigen wenigen Seiten deren Ranking nach oben zu treiben. Wird eine Linkfarm als solche identifiziert, dann bestraft Google die manipulierten Seiten mit einem Page Rank von null - sie sind somit bei Suchanfragen praktisch nicht mehr auffindbar.

Dieser Text ist ein Auszug aus dem Buch "Numerator - Mathematik für jeden", das im Goldmann-Verlag erschienen ist.

Mehr lesen über Verwandte Artikel