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.