o-mathe | Das Ranking-Problem » Simulation mit Matrizenrechnung

Simulation mit Matrizenrechnung

Zielsetzung

Im letzten Abschnitt wurde ein verbessertes Surfer-Modell entwickelt, mit dem man mithilfe der Verlinkungsstruktur konkrete Werte für die Relevanz einer Webseite berechnen kann. Dieses Surfer-Modell wurde von den Entwicklern von Google zu Beginn benutzt. Im letzten Abschnitt hast du vermutlich auch bereits erfahren, dass eine konkrete Anwendung des Surfer-Modells zu komplexen Übergangsgraphen führt - und das bereits bei einer sehr einfachen Webseitenwelt mit nur $4$ Webseiten. Wenn man größere Webseitenwelten betrachtet, dann ist es günstig, diese nicht mit Graphen zu erfassen, sondern sie mit Hilfe von Matrizen zu beschreiben. Diesen Weg werden wir hier einschlagen.

Mathematische Beschreibung des erweiterten Surfer-Modells

Hier noch einmal die Vorgaben zum erweiterten Surfer-Modell:

(Erweitertes) Surfer-Modell

Wir gehen von folgenden Annahmen aus:

(A1) Zu Beginn verteilen sich alle Surfer (Besucher:innen) gleichmäßig auf die Webseiten.

(A2) 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.

(A3) 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.

Wir betrachten wieder diese Webseitenwelt.

In der folgenden Übersicht sind die Übergangsraten von Webseite A aus und von Webseite B aus dargestellt.

Übergang	Surf-Rate	Jump-Rate	Erläuterung
$A ⟶ B$	$0.8 \cdot \frac{1}{2} = 0.4$	$0.2 \cdot \frac{1}{4} = 0.05$	Von A aus kann man zwei Webseiten per Link erreichen. Nur $80 %$ folgen diesen Links. $20 %$ springen auf eine beliebige Seite. Diese teilen sich auf die $4$ Seiten gleichmäßig auf.
$A ⟶ C$	$0.8 \cdot \frac{1}{2} = 0.4$	$0.2 \cdot \frac{1}{4} = 0.05$	Von A aus kann man zwei Webseiten per Link erreichen. Nur $80 %$ folgen diesen Links. $20 %$ springen auf eine beliebige Seite. Diese teilen sich auf die $4$ Seiten gleichmäßig auf.
$A ⟶ D$	$0.8 \cdot 0 = 0$	$0.2 \cdot \frac{1}{4} = 0.05$	Von A nach D gibt es keinen Link. $20 %$ springen auf eine beliebige Seite. Diese teilen sich auf die $4$ Seiten gleichmäßig auf.
$A ⟶ A$	$0.8 \cdot 0 = 0$	$0.2 \cdot \frac{1}{4} = 0.05$	Von A nach A gibt es keinen Link. $20 %$ springen auf eine beliebige Seite. Diese teilen sich auf die vier Seiten gleichmäßig auf.
$B ⟶ A$	$0.8 \cdot 0 = 0$	$0.2 \cdot \frac{1}{4} = 0.05$	Von B nach A gibt es keinen Link. $20 %$ springen auf eine beliebige Seite. Diese teilen sich auf die $4$ Seiten gleichmäßig auf.
$B ⟶ C$	$0.8 \cdot 0 = 0$	$0.2 \cdot \frac{1}{4} = 0.05$	Von B nach C gibt es keinen Link. $20 %$ springen auf eine beliebige Seite. Diese teilen sich auf die $4$ Seiten gleichmäßig auf.
$B ⟶ D$	$0.8 \cdot 0 = 0$	$0.2 \cdot \frac{1}{4} = 0.05$	Von B nach D gibt es keinen Link. $20 %$ springen auf eine beliebige Seite. Diese teilen sich auf die $4$ Seiten gleichmäßig auf.
$B ⟶ B$	$0.8 \cdot 1 = 0.8$	$0.2 \cdot \frac{1}{4} = 0.05$	$80 %$ verbleiben auf der Seite B. $20 %$ springen auf eine beliebige Seite. Diese teilen sich auf die vier Seiten gleichmäßig auf.

Aufgabe 1

Die Übergangsraten lassen sich übersichtlich mit Hilfe von Matrizen darstellen. Erkläre die folgende Darstellung und ergänze die fehlenden Teile.

Surfer	Gelegenheitsjumper
$S = (\begin{matrix} 0 & \dots & \dots & \dots \\ 0.4 & \dots & \dots & \dots \\ 0.4 & \dots & \dots & \dots \\ 0 & \dots & \dots & \dots \end{matrix})$	$J = (\begin{matrix} 0.05 & \dots & \dots & \dots \\ 0.05 & \dots & \dots & \dots \\ 0.05 & \dots & \dots & \dots \\ 0.05 & \dots & \dots & \dots \end{matrix})$
$S = \underset{Surfrate}{\underset{⏟}{0.8}} \cdot \underset{Linkmatrix L}{\underset{⏟}{(\begin{matrix} 0 & \dots & \dots & \dots \\ 1 / 2 & \dots & \dots & \dots \\ 1 / 2 & \dots & \dots & \dots \\ 0 & \dots & \dots & \dots \end{matrix})}}$	$J = \underset{Jumprate}{\underset{⏟}{0.2}} \cdot \underset{4 : Webseitenanzahl}{\underset{⏟}{\frac{1}{4}}} \cdot \underset{Einsermatrix I}{\underset{⏟}{(\begin{matrix} 1 & \dots & \dots & \dots \\ 1 & \dots & \dots & \dots \\ 1 & \dots & \dots & \dots \\ 1 & \dots & \dots & \dots \end{matrix})}}$

Aufgabe 2

Mit den Hilfsmatrizen aus Aufgabe 1 kann man jetzt die Prozessmatrix für das verbesserte Surfer-Modell erstellen:

$P = S + J = 0.8 \cdot (\begin{matrix} 0 & \dots & \dots & \dots \\ 0.5 & \dots & \dots & \dots \\ 0.5 & \dots & \dots & \dots \\ 0 & \dots & \dots & \dots \end{matrix}) + 0.2 \cdot \frac{1}{4} \cdot (\begin{matrix} 1 & \dots & \dots & \dots \\ 1 & \dots & \dots & \dots \\ 1 & \dots & \dots & \dots \\ 1 & \dots & \dots & \dots \end{matrix})$

Überprüfe, ob hier ein Austauschprozess beschrieben wird. Weise hierzu nach, dass $P$ eine stochastische Matrix ist.

Aufgabe 3

Nutze ein CAS, um die Grenzverteilung für die Prozessmatrix $P$ zu bestimmen. Mit dem Button [ $\approx$ ] kannst du gerundete Werte bestimmen.

Aufgabe 4

Erstelle ein Ranking für die folgende Webseitenwelt.