Suchmaschinen: Page-Rank-Algorithmus

Zufallssurfer Modell

Bei dem bisherigen Zufallssurfer-Modell aus dem letzten Abschnitt stellt man fest, dass sich nach einigen Zeitschritten alle Nutzer beim Knoten D ansammeln.

Daher erweitern wir unser bisheriges Modell um die Annahme, dass sich in jedem Zeitschritt jeweils 15% der Besucher eines jeden Knotens gleichmäßig auf alle Knoten des Netzwerkes verteilen, indem sie zufällig irgendeine andere Webseite ansurfen. Die übrigen 85% verhalten sich wie in dem bisherigen Modell.

Die Gesamtzahl an Nutzer, die in jedem Zeitschritt eine zufällige Webseite ansurfen beträgt

0,15 a_i + 0,15 b_i + 0,15 c_i +0,15 d_i = 0,15 (a_i + b_i +c_i + d_i ) = 0,15

Bezeichnen wir nun noch mit n die Anzahl der Knoten (in dem gewählten Beispiel also n=4), so erhalten wir folgendes iteratives Schema für die jeweiligen Zeitschritte:

In Matrix-Vektor-Schreibweise können wir dieses Schema ausdrücken als

Nun führen wir noch die sogenannte Übergangsmatrix A und die Einsmatrix E und die Iterationsmatrix G wie folgt ein:

Damit können wir das Iterationsschema in Kurzform schreiben als:

Durchführen einiger Iterationsschritte liefert dann:

	i=0	i=1	i=2	...	i=20	i=30
ai	0,25	0,14375	0,1889	...	0,1006	0,1006
bi	0,25	0,14375	0,0986	...	0,0803	0,0803
ci	0,25	0,35625	0,2208	...	0,1485	0,1485
di	0,25	0,35625	0,4917	...	0,6706	0,6706

Die Ergebnisse aus der Tabelle lassen vermuten, dass die prozentualen Anteile für gegen die folgenden feste Werte konvergieren:

Diese festen Grenzwerte nennt man PageRank-Werte der jeweils zugehörigen Webseiten. Sie geben ein Maß für die Wichtigkeit der betreffenden Webseiten an. In unserem Beispiel würden die Webseiten also durch die Suchmaschine in der folgenden Reihenfolge angezeigt werden:

D	wichtigste Webseite
C
A
B	unwichtigste Webseite

Anmerkung 1:

Der Vektor v=(a,b,c,d) wird durch G auf sich selbst abgebildet, also Gv = v. Ein solcher Vektor heißt Eigenvektor der Matrix G. Im Grundstudium der Mathematik, Informatik und der Physik beschäftigt man sich ausführlich mit den weiteren Eigenschaften solcher Eigenvektoren. Im Englischen wird übrigens der Fachbegriff eigenvector verwendet.

Anmerkung 2:

Tatsächlich gibt es einen Satz aus der Mathematik, mit dem sich beweisen lässt, dass das obige Schema unabhängig von der Größe des Graphen stets gegen feste Pagerank-Werte für die prozentualen Anteile an Webseitenbesuchern konvergiert. Der mathematische Satz heißt Theorem von Frobenius-Perron. Der Beweis dieses Satzes ist mit den Mitteln der Schulmathematik leider nicht leicht zugänglich und wird in der Schule daher nicht behandelt.

Aufgabe 1: (Iteration mit Papier und Bleistift)

Führe mindestens zwei weiter der oben angegebenen Iterationen rechnerisch durch. Notiere die prozentualen Anteile für die Zeitschritte i=3 und i=4.

Aufgabe 2: (Iteration mittels Python-Programm)

Schreibe in Python-Programm, dass die oben angegebene Iteration durchführt und berechne damit mindestens 40 der angegebenen Iterationen. Gib die prozentualen Besucherzahlen in den einzelnen Zeitschritten tabellenförmig aus.

Aufgabe 3: (Iteration mittels CAS wxMaxima)

Führe die oben angegebene Iteration mittels des CAS wxMaxima durch. Notiere die prozentualen Besucherzahlen nach 15 und nach 30 Iterationen.

Aufgabe 4: (Gesamtzahl an Nutzern bleibt gleich)

Beweise, dass für alle Zeitschritte der obigen Iteration gilt: a_i + b_i + c_i + d_i = 1 (Tipp: Vollständige Induktion)

Aufgabe 5: (Pagerank-Werte bestimmen)

Gegeben sei das folgende Netz von Webseiten.
### TODO: Graph einfügen ### Bestimme die Pagerank-Werte der einzelnen Webseiten.