Numerator: Wie Google mit Milliarden Unbekannten rechnet

Von

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.

Google-Algorithmus: Das Page-Rank-Verfahren Fotos
REUTERS

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.

Diesen Artikel...
Aus Datenschutzgründen wird Ihre IP-Adresse nur dann gespeichert, wenn Sie angemeldeter und eingeloggter Facebook-Nutzer sind. Wenn Sie mehr zum Thema Datenschutz wissen wollen, klicken Sie auf das i.

Auf anderen Social Networks teilen

  • Xing
  • LinkedIn
  • Tumblr
  • studiVZ meinVZ schülerVZ
  • deli.cio.us
  • Digg
  • reddit
News verfolgen

HilfeLassen Sie sich mit kostenlosen Diensten auf dem Laufenden halten:

alles aus der Rubrik Wissenschaft
Twitter | RSS
alles aus der Rubrik Mensch
RSS
alles zum Thema Numerator
RSS

© SPIEGEL ONLINE 2009
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH

SPIEGEL ONLINE Schließen


  • Drucken Versenden
  • Nutzungsrechte Feedback
  • Zur Startseite
Buchtipp
Holger Dambeck: Numerator
Mathematik für jeden

Anschaulich, spielerisch, praktisch: wie Mathematik unser Leben bestimmt und warum Problemelösen auch ahnungslosen Laien Spaß macht. SPIEGEL-ONLINE-Redakteur Holger Dambeck lädt ein in die faszinierende Welt der Mathematik. Mit einem Vorwort von Albrecht Beutelspacher, dem Gründer des Mathematikums in Gießen.

Goldmann-Verlag; 223 Seiten; 7,95 Euro.

Einfach und bequem: Direkt im SPIEGEL-Shop bestellen.

Fotostrecke
Faszination Mathematik: Bach, Gömböc und Penrose-Parkett

Mini-Web: Linkpopularität entscheidet über Page Rank
SPIEGEL ONLINE

Mini-Web: Linkpopularität entscheidet über Page Rank

Fotostrecke
Web-Konzern: Alles, was Sie über Google wissen müssen