i

Modellerweiterung

Probleme der vereinfachten Random Surfer

Auf der letzten Seite sind wir von diesem Random Surfer Modell ausgegangen:

(Vereinfachtes) Random Surfer Modell

  1. Zu Beginn verteilen sich alle Surfer gleichmäßig auf die Webseiten.
  2. 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.

Aufgabe 1

Betrachte diese erweiterte Webseitenwelt.

Graph mit Sackgasse

(a) Beschreibe, worin sich die neue Welt von der vorherigen unterscheidet.

(b) Führe in dieser neuen Welt einige Simulationsschritte durch, bis dir ein Problem auffällt. Achte insbesondere auf den Pfeil von E zu sich selbst.

Hilfestellung zur Berechnung

Diese Abbildung gibt direkt die Übergangswahrscheinlichkeiten an.

Graph mit Sackgasse

(c) Erläutere die Schwierigkeit, die sich hier ergibt, wenn man mit dem bisherigen Surfermodell die Bedeutung von Seiten ermitteln möchte.

(d) (für Schnelle) Automatisiere die Berechnungen mit einer Tabellenkalkulation oder mit Python.

Tabellenkalkulation ein-/ausblenden

Zum Herunterladen: simulation2.ggb

Python-Programm ein-/ausblenden

Ein Lösungsansatz

Das Problem besteht beim vereinfachten Random Surfer Modell darin, dass er in eine „Link-Sackgasse“ geraten kann. Mit unserem Verfahren bleibt er dann für immer auf dieser Webseite.

Aufgabe 2

(a) Mache Vorschläge, wie das Problem der Link-Sackgassen gelöst werden kann.

(b) Als wir uns das Patent zu PageRank angesehen haben, war ein Satz ausgelassen. Blende dir diesen ein und überlege, wie das gemeint sein könnte.

Patent ein-/ausblenden

„A method assigns importance ranks to nodes in a linked database, such as any database of documents containing citations, the world wide web or any other hypermedia database. The rank assigned to a document is calculated from the ranks of documents citing it. In addition, the rank of a document is calculated from a constant representing the probability that a browser through the database will randomly jump to the document. The method is particularly useful in enhancing the performance of search engine results for hypermedia databases, such as the world wide web, whose documents have a large variation in quality.“ [1]

Gelegenheitsjumper

Auf Links zu klicken ist nicht die einzige Möglichkeit, sich im World Wide Web zu bewegen. Man kann jederzeit, z.B. weil man in einer Link-Sackgasse steckt, die zuletzt besuchte Seite aufrufen, eine beliebige bekannte Webseite (mit ihrer URL) aufrufen oder ganz mit dem Surfen aufhören.

Der zweite der drei Vorschläge, also einfach eine beliebige Seite aufzurufen, ist besonders einfach umsetzbar. Wir ergänzen das Surfer Modell entsprechend:

Random Surfer Modell

  1. Zu Beginn verteilen sich alle Surfer gleichmäßig auf die Webseiten.
  2. In jedem Schritt folgt der Großteil der Surfer (z.B. 80%) 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.
  3. In jedem Schritt springen die übrigen Surfer (hier also 20%) zu einer beliebigen anderen Webseite. Sie teilen sich dabei gleichmäßig auf alle zur Verfügung stehenden Webseiten auf. Wir nennen sie die Gelegenheitsjumper.
Gelegenheitsjumper

Aufgabe 3

(a) Erkläre, wie die in der Abbildung gezeigten Berechnungsformeln zustande kommen.

(b) Führe eine automatisierte Simulation durch – mit einer Tabellenkalkulation oder mit Python.

Tabellenkalkulation ein-/ausblenden

Zum Herunterladen: simulation3.ggb

Python-Programm ein-/ausblenden

Aufgabe 4 (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?

Quellen

Suche

v
2.1.2.2.4
inf-schule.de/algorithmen/grundlagen/bedeutung/fallstudie_pagerank/modellerweiterungen
inf-schule.de/2.1.2.2.4
inf-schule.de/@/page/fU1OkS76az3Q2woC

Rückmeldung geben