Vereinfachtes Zufallssurf-Modell
Als Modell für ein Netz aus Webseiten betrachten wir 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:innen des oben angegebenen Netzes aus vier Webseiten simulieren. Dazu nehmen wir an, dass sich zu Beginn alle Nutzer:innen des Gesamtsystem gleichmäßig auf alle Webseiten verteilen. Mit den Kleinbuchstaben {a,b,c,d} bezeichnen wir den Anteil an Nutzer:innen, 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: $$ \begin{array}{c} a_0 = 0,25 \\ b_0 = 0,25 \\ c_0 = 0,25 \\ d_0 = 0,25 \end{array} $$Nun wechseln alle Nutzer:innen 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 Nutzer:innen eines Knotens, welche dem jeweiligen Link auf eine nächste Webseite folgen. In unserem Modell bleibt also keine Nutzer:in auf ihrer bisherigen Webseite (mit Ausnahme der Nutzer:innen auf Knoten D) und keine Nutzer:in 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: $$ \begin{array}{cccccccc} a_{i+1} & = & & & & 0,5 c_i & & \\ b_{i+1} & = & 0,5 a_i & & & & & \\ c_{i+1} & = & 0,5 a_i & + & 1 b_i & & & \\ d_{i+1} & = & & & & 0,5 c_i & + & 1 d_i \end{array} $$ In Matrix-Vektor-Schreibweise können wir dieses Schema ausdrücken als $$\left(\begin{array}{c} a_{i+1}\\ b_{i+1}\\ c_{i+1}\\ d_{i+1} \end{array}\right) = \left(\begin{array}{cccc} 0 & 0 & 0,5 & 0\\ 0,5 & 0 & 0 & 0\\ 0,5 & 1 & 0 & 0\\ 0 & 0 & 0,5 & 1 \end{array}\right) \left(\begin{array}{c} a_{i}\\ b_{i}\\ c_{i}\\ d_{i} \end{array}\right)$$ Nun führen wir noch die sogenannte Übergangsmatrix A ein: $$A=\left(\begin{array}{cccc} 0 & 0 & 0,5 & 0\\ 0,5 & 0 & 0 & 0\\ 0,5 & 1 & 0 & 0\\ 0 & 0 & 0,5 & 1 \end{array}\right) \;\;\;\;\;\ \vec{v}_{i}=\left(\begin{array}{c} a_{i}\\ b_{i}\\ c_{i}\\ d_{i} \end{array}\right)$$ Damit können wir das Iterationsschema in Kurzform schreiben als: $$\vec{v}{}_{i+1}=A\vec{v}_{i}$$ 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 |
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 (mit den angegebenen Bruchteilen an wechselnden Nutzenenden) jeweils alle den eingezeichneten Pfeilen zum nächsten Bereich. Führt mehrere Zeitschritte nach diesem Schema durch.Notiert in jedem Zeitschritt die Anzahl an Besucher:innen auf der jeweiligen Webseite. Berechnet anschließend für die einzelnen Zeitschritte die prozentuale Anteile der Besucher:innen jeder Webseite bezogen auf die Gesamtzahl aller Nutzer:innen und vergleicht eure Ergebnisse mit den in der Tabelle angegebenen.
