Die Aufgabe
Eine Anwendung der Markoff-Prozesse ist der Page-Rank-Algorithmus, der von den Google-Gründern angegeben wurde. Näheres dazu finden Sie im Buch von Teschl, S. und Teschl, G.: Mathematik für Informatiker. Band 1: Diskrete Mathematik und lineare Algebra. Das Buch ist als eBook verfügbar.
Gegeben sei folgendes Verlinkungsbeispiel (siehe Grafik rechts).
Die Seiten 1 bis 5 werden als Zustände (in denen sich der Benutzer befindet) verstanden. Alle von einem Zustand ausgehenden Übergangswahrscheinlichkeiten seien gleich.
- Stellen Sie die Übergangsmatrix auf.
- Berechnen Sie ausgehend von dem Eigenwert 1 die Seitengewichte.
- Berechnen Sie die nächsten 10 Vektoren ausgehend von dem Startvektor und interpretieren Sie diese Folge von Vektoren.
Die Aufgabe nennt „Markoff-Prozesse“; das ist eine ältere Schreibweise für Markov-Prozesse. Gemeint ist ein Zufallsablauf in Schritten: Man befindet sich in einem Zustand, und die Wahrscheinlichkeit für den nächsten Zustand hängt nur vom jetzigen ab. Hier sind die fünf Seiten die Zustände, und ein Klick ist ein Schritt.
Die Übergangsmatrix sammelt alle diese Wahrscheinlichkeiten in einer Tabelle. Mit ihr lässt sich ausrechnen, wie sich die Besucher nach jedem Klick auf die Seiten verteilen.
So gehen wir vor:
- Im Graphen die Links zählen und die Matrix aufstellen (Teil a).
- Das Gleichungssystem lösen und die Lösung so skalieren, dass die Summe 1 ist (Teil b).
- Ab dem Startvektor zehnmal mit multiplizieren und die Folge deuten (Teil c).
Die Musterlösung gibt bei b) gerundete Prozentwerte an (18 %, 18 %, 18 %, 27 %, 18 %); wir rechnen mit den exakten Brüchen und erklären den Unterschied in Schritt 8. Zu c) enthält die Musterlösung keine Angabe; die zehn Vektoren stammen aus einem eigenen Python-Lauf.