Pagerank

Diese Folge ist ein Türchen im Adventskalender 2025 von
Wissenschaftspodcasts.de.

Es ist schon schwer genug, sich geeignete Weihnachtsgeschenke zu
überlegen, aber mit einer Idee muss diese dann auch erst im Netz
gefunden werden. Für Kaffee-Trinker gibt es die Zwei-Wege oder
two-way Kaffe-Tasse oder Physik in der Hand mit dem Handkocher
von Empirie. Aber wie findet Google bei Stichworten die richtigen
Seiten? Wörter wie Kaffee oder Tasse sind auf vielen Seiten zu
finden, eine Suche einfach nach Wörtern wird viel zu viele
Ergebnisse liefern. Der Grund, warum Google den
Suchmaschinenmarkt umgekrempelt hat, liegt daran, dass sie das
Problem mit einem Modell betrachteten: Einerseits werden Wörter
auf Seiten gesucht, andererseits werden sie nach einer Art
Relevanz sortiert. 


Eine Art der Relevanz könnte sein, auf welchen Webseiten Menschen
sich häufiger befinden. Die Webseiten sind im Hypertext
geschrieben und bestehen aus Text und Links wie ein Graph aus
Knoten, den Seiten, und Kanten, den Links. Eine Strategie häufige
aufgesuchte Seiten zu finden, ist die Simulation von zufälligen
Klicks von Menschen. Das Modell sind also Menschen, die dumm auf
Links klicken. Das ist ein stochastischer Prozess. Wenn alle
Links gleich "groß" und "sichtbar" sind, ist Gleichverteilung
beschreibbar als Markov-Kette. Die Wahrscheinlichkeiten aller
Seiten liefern eine Übergangsmatrix mit Wahrscheinlichkeiten in
den Spalten. Das Matrix-Vektor-Produkt liefert dann die
Wahrscheinlichkeit der nächsten Seiten. Ist aber so ein Prozess
der Wahrscheinlichkeiten zufälliger Klicks überhaupt
konvergent? 


Wenn es eine Konvergenz gibt, so wird das Ergebnis der
Wahrscheinlichkeiten stabil und stellt den Eigenvektor zum
höchsten Eigenwert dar. Das beschriebene Verfahren des zufälligen
Weiterklickens zum Berechnen der Wahrscheinlichkeiten ist die
Potenzmethode zur Bestimmung des Eigenvektors zum größten
Eigenwert. Das Verfahren wurde von Sergey Brin and Lawrence Page
erdacht und auch etwas dadurch stabilisiert, dass eine gewisse
Wahrscheinlichkeit festgelegt wurde, mit der Menschen auf einer
Seite verbleiben statt weiter zu klicken. Insgesamt wird das
Ergebnis dann in logarithmischer Skala PageRank genannt und hilft
die Seiten mit den richtigen Stichworten nach Relevanz zu
sortieren.