Suchmaschinen: Page-Rank-Algorithmus

Vereinfachtes Zufallssurfer Modell

Als Modell für ein Netz aus Webseiten betrachten den folgenden gerichteten gerichteten Graphen aus Internetseiten. Die so genannten Knoten {A,B,C,D} des Graphen repräsentieren die einzelnen Webseiten. Die Verlinkungen zwischen den Webseiten sind als so genannte gerichtete Kanten dargestellt. Die Pfeilrichtung gibt jeweils die Richtung der Links an.

Intuitiv könnte man ein Maß für die Wichtigkeit der einzelnen Webseiten dadurch bestimmen, indem man zählt, wie viele eingehende Links auf diese Webseite verweisen. Je mehr eingehende Links eine Webseite hat, umso mehr Bedeutung wird ihr von den auf sie verweisenden Webseiten beigemesssen. Hat eine Webseite umgekehrt selbst wenig ausgehende Links, so könnte dies ein Indiz dafür sein, dass diese Webseite besonders wichtig sein könnte.

Aufgabe 1: (Schätzen des Pageranks)

Versuche, die Webseiten aus der obigen Abbildung intuitiv nach deren Wichtigkeit für das gesamte Netzwerk zu ordnen.

Simulation des Surfverhaltens

Wir wollen nun das Surf-Verhalten der Nutzer des oben angegebenen Netzes aus vier Webseiten simulieren. Dazu nehmen wir an, dass sich zu Beginn alle Nutzer des Gesamtsystem gleichmäßig auf alle Webseiten verteilen. Mit den Kleinbuchstaben {a,b,c,d} bezeichnen wir den Anteil an Nutzern, welche die jeweils zugehörigen Webseiten {A,B,C,D} aufgerufen haben. Führen wir noch einen Index für den Zeitschritt einer dynamischen Simulation ein, so erhalten wir also zu Beginn der Simulation: a₀ = 0,25
b₀ = 0,25
c₀ = 0,25
d₀ = 0,25

Nun wechseln alle Nutzer des Systems in jedem Zeitschritt die Webseiten, indem sie sich gleichmäßig auf alle ausgehenden Links verteilen. Die im Diagramm angegebenen Kantengewichte entsprechen jeweils dem Anteil an Nutzern eines Knotens, welche dem jeweiligen Link auf eine nächste Webseite folgen. In unserem Modell bleibt also kein Nutzer auf seiner bisherigen Webseite (mit Ausnahme der Nutzer auf Knoten D) und kein Nutzer verlässt das System.

Nun betrachten wir die Wechsel zwischen den verschiedenen Webseiten in jedem Zeitschritt etwas genauer. Mit dem obigen Modell erhalten wir das folgende iterative Schema für die jeweiligen Zeitschritte i: In Matrix-Vektor-Schreibweise können wir dieses Schema ausdrücken als Nun führen wir noch die sogenannte Übergangsmatrix A 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
ai	0,25	0,125	0,1875	...	0,001
bi	0,25	0,125	0,0625	...	0,000
ci	0,25	0,375	0,1875	...	0,002
di	0,25	0,375	0,5625	...	0,997

Man beobachtet, dass sich nach i=20 Iterationen fast alle Nutzer des Netzes auf der Webseite D ansammeln, da diese keinen ausgehenden Link zu einer anderen Webseite hat. Damit ist das bisherige Modell noch nicht besonders realistisch, so dass es im nächsten Abschnitt noch weiter verfeinert wird.

Aufgabe 2: (Iteration im Rollenspiel)

Markiert im Klassenraum oder auf den Schulhof wie im obigen Diagramm angegeben vier Bereiche {A,B,C,D}, die jeweils einer Webseite entsprechen sollen. Zeichnet auch die Links zwischen den Bereichen als Pfeile ein. Verteilt euch nun möglichst gleichmäßig auf die Knoten A,B,C, und D und folgt in jedem Zeitschritt jeweils alle den eingezeichneten Pfeilen zum nächsten Bereich. Führt mehrere Zeitschritte nach diesem Schema durch. Notiert in jedem Zeitschritt die Anzahl an Besuchern auf der jeweiligen Webseite. Berechnet anschließend für die einzelnen Zeitschritte die prozentuale Anteile der Besucher jeder Webseite bezogen auf die Gesamtzahl aller Nutzer und vergleicht eure Ergebnisse mit den in der Tabelle angegebenen.

Aufgabe 3: (Rechnerische Iteration mit Papier und Bleistift)

Führe mindestens zwei weitere der oben angegebenen Iterationen rechnerisch durch und notiere die ermittelten prozentualen Anteile für i=3 und i=4.

Aufgabe 4: (Iteration mittels Python-Programm)

Schreibe in Python-Programm, dass die oben angegebene Iteration durchführt und berechne damit mindestens 20 der angegebenen Iterationen. Gib die prozentualen Besucherzahlen in den einzelnen Zeitschritten tabellenförmig aus. Vergleiche die ermittelten prozentualen Besucherzahlen in jedem Zeitschritt ggf. mit den Ergebnissen aus Aufgabe 2 und 3.

Aufgabe 5: (Iteration mittels CAS wxMaxima)

Führe die oben angegebene Iteration mittels des CAS wxMaxima durch (CAS steht für Computer-Algebra-System). Gib die prozentualen Besucherzahlen nach zwanzig Iterationen an.

Aufgabe 6: (Gesamtzahl an Nutzern bleibt gleich)

Beweise, dass für alle Zeitschritte i der obigen Iteration gilt: a_i + b_i +c_i +d_i = 1