Das Zufallssurfermodell
Verlinkung und die Bedeutung von Webseiten
Wir bewerten Webseiten danach, wie viele andere auf sie verlinken und wie stark verlinkt diese anderen Seiten wiederum sind. Links von Webseiten, auf die selbst viele Links verweisen, werden dabei stärker berücksichtigt als Links, die ihren Ursprung auf Webseiten haben, auf die nur wenige oder gar keine Links verweisen.
In der vorliegenden vereinfachten Webseitenwelt ist das gar nicht so leicht zu beantworten. Die mit C markierte Webseite scheint wichtiger zu sein als die mit A markierte Seite. Aber, wie kann man das nachvollziehbar bestimmen? Ziel ist es, die Verlinkungsstruktur von Webseiten jetzt zahlenmäßig zu erfassen. Das führt uns zu folgendem Problem:
Verlinkungsproblem
Wie kann man mithilfe der Verlinkungsstruktur konkrete Werte für die Relevanz einer Webseite berechnen?
Vermessung der Verlinkung mit einem Surfverfahren
Man benutzt das World Wide Web, indem man von einer Webseite über einen Link zur nächsten „surft“. Wir können dieses Surfverhalten simulieren. Dabei gehen wir davon aus, dass die Nutzerinnen und Nutzer sich einen zufälligen Link zum surfen auswählen. Deshalb spricht man vom Random-Surfer-Modell. Webseiten, auf die viele bedeutende Links verweisen, werden bei der Simulation daran zu erkennen sein, dass dort viele Besucher durch das ziellose Surfen landen.
(Vereinfachtes) Random Surfer Modell
Surfer sind auf die Webseiten zufällig verteilt. In jedem Schritt suchen sich die Surfer einen zufälligen Link auf ihrer Webseite aus und folgen ihm zur nächsten Webseite.
Die folgende Klickstrecke veranschaulicht das Vorgehen:
- Zu Beginn verteilen sich alle Surfer gleichmäßig auf die Webseiten.
- Alle Surfer folgen jeweils im gleichen Takt einem Link auf eine weitere Webseite. Wenn auf einer Webseite mehrere Links vorkommen, dann verteilen sich die Surfer gleichmäßig auf die verschiedenen Links.
Klicke auf die einzelnen Schritte zur Veranschaulichung.
Aufgabe 1
Betrachte die in der Abbildung gezeigte einfache Webseitenwelt. Markiert im Klassenraum oder auf den Schulhof die vier Knoten A, B, C, D, die jeweils einer Webseite entsprechen sollen. Zeichnet auch die Links zwischen den Knoten als Pfeile ein. Verteilt euch nun möglichst gleichmäßig auf die Knoten A,B,C, und D und folgt in jedem Simulationsschritt jeweils alle den eingezeichneten Pfeilen zum nächsten Knoten. Beachtet dabei die Regel (A2). Führt mehrere Simulationsschritte nach diesem Schema durch. Beobachtet, wie sich die Verteilung der Surfer auf die Knoten entwickelt.
Aufgabe 2
Wie viele Nutzer besuchen in der gezeigten Situation nach 1, 2, 3, ... Schritten die verschiedenen Webseiten, wenn zu Beginn auf jeder Webseite 600 Nutzer surfen? Berechne im Kopf und mit dem Taschenrechner für fünf Schritte. Benutze Dezimalzahlen, auch wenn das der Wirklichkeit nicht mehr entspricht.
Trage in die Tabelle deine Ergebnisse auf zwei Nachkommastellen gerundet ein. Die bereits eingetragenen Ergebnisse dienen zur Kontrolle.
| Schritt | A | B | C | D |
|---|---|---|---|---|
| 0 | 600 | 600 | 600 | 600 |
| 1 | ||||
| 2 | 300 | |||
| 3 | 700 | |||
| 4 | 466.67 | |||
| 5 | 750 |
Automatisierung der Berechnung
In der Informatik möchte man Probleme automatisiert lösen. Es soll also nicht mehr jeder einzelne Schritt mit dem Taschenrechner bearbeitet werden, sondern ein Computerprogramm soll alle Schritte automatisch berechnen.
Diese Automatisierung kannst du mit einem Tabellenkalkulationsprogramm bearbeiten (▶ Aufgabe 3) oder mit einer Programmiersprache (▶ Aufgabe 4). Selbst wenn du noch keine Erfahrungen mit Programmiersprachen hast, kannst du versuchen, das Programm in Aufgabe 4 zu verstehen.
Aufgabe 3
Führe die Berechnungen mit einem Tabellenkalkulationsprogramm aus. Führe so viele Simulationsschritte aus, bis sich die Besucherzahlen stabilisieren. Löse so das Rankingproblem für die gegebene Webseitenwelt.
Hilfe für die Tabellenkalkulation ein-/ausblenden
Wir können die folgende GeoGebra-Tabellenkalkulation nutzen. Wenn du auf ein Feld klickst, kannst du hierfür neue Zahlen oder eine Formel zur Berechnung eingeben.
(a) Klicke zweimal auf das Feld A3, um die genutzte Formel „C2/3“ zu sehen. Erkläre diese Formel anhand der Webseiten-Welt.
(b) Sage voraus, welche Formel im Feld B3 stehen müsste. Kontrolliere dann.
(c) Füge in gleicher Art Formeln in C3 und D3 ein.
(d) Markiere die Felder A3 bis D3. Unten rechts erscheint ein blaues kleines Quadrat. Klicke dieses Quadrat an, halte die Maus gedrückt, ziehe es nach unten und lasse es los. So kannst du die Formeln auch in die weiteren Zeilen übertragen, um mehr Simulationsschritte durchzuführen.
Zum Herunterladen: simulation.ggb
Aufgabe 4
Führe die Berechnungen mit Python aus. Ergänze hierzu das Programmgerüst. Führe so viele Simulationsschritte aus, bis sich die Besucherzahlen stabilisieren. Löse so das Rankingproblem für die gegebene Webseitenwelt.
Du hast noch keine Programmier-Erfahrung mit Python?
Das macht nichts! Schau dir den Quelltext unterhalb dieser Aufgabe an. Die grauen Stellen, die mit einem „#“ beginnen, sind Kommentare – sie dienen nur zur besseren Übersichtlichkeit.
Versuche zuerst, das Programm zu verstehen:
- Was geschieht in den ersten 5 Zeilen?
- Wozu dienen die Werte (man sagt „Variablen“) anzahlSchritte und zaehler in Zeile 6 und 8?
- Versuche, den Inhalt von Zeile 9 zu übersetzen.
- Was hat Zeile 10 mit deinen Rechnungen aus Aufgabe 2 zu tun?
Wenn du all das beantwortet hast, bist du in der LAge die Zeilen 11 bis 13 anzupassen und dann das Programm mit dem Knopf oben rechts auszuführen.
Glückwunsch! Du hast dein erstes Python-Programm fertiggestellt.
Aufgabe 5 (Herausforderung)
Die folgende Aufgabe ist für den weiteren Verlauf nicht erforderlich.
Die bisherigen Berechnungen galten immer einer fest vorgegebenen Webseiten-Welt. Sowohl in einem Tabellenkalkulationsprogramm als auch in Python ist es möglich, die Berechnungen für beliebige Welten zu implementieren. Schaffst du das?
