Ein Ranking-Algorithmus

Bestimmung von Rankingwerten

Die Relevanz von Webseiten lässt sich mit dem folgenden Simulationsverfahren bestimmen, bei dem das Surfverhalten einer vorgegebenen Anzahl von Webseitenbesuchern nach einfachen Regeln durchgespielt wird.

ALGORITHMUS PageRank:
Lege die Anzahl der Simulationsschritte fest.
Lege den Surf- und Sprunganteil fest.
Lege die Ausgangsbesucherzahlen fest.
Setze einen Zähler auf 0.
SOLANGE der Zähler kleiner als die Anzahl der Simulationsschritte ist:
    Berechne die neuen Besucherzahlen.
    Erhöhe den Zähler um 1.
Gib die Besucherzahlen (als gesuchte Rankingwerte) aus.

Zur Konkretisierung betrachten wie die folgende sehr einfache Webseitenwelt:

Das oben informell beschriebene Verfahren lässt sich jetzt wie folgt präzisieren:

Wenn man dieses Verfahren in ein Python-Programm übersetzt, dann kann es von einem Computer automatisiert ausgeführt werden.

# Anzahl der Simulationsschritte
anzahlSchritte = 1000
# Surf- und Sprunganteile
p = 0.8
q = 1-p
# Besucherzahlen zu Beginn
n = 1000
a = n/6
b = n/6
c = n/6
d = n/6
e = n/6
f = n/6
# Initialisierung des Zaehlers
zaehler = 0
# wiederholte Berechnung der Besucherzahlen
while zaehler < anzahlSchritte:
    # Bestimmung der neuen Besucherzahlen 
    a_neu = (p*c)/3 +                         \
            (q*(a+b+c+d+e+f))/6 +             \
            (p*f)/6                                      
    b_neu = (p*a)/2 + (p*e) +                 \
            (q*(a+b+c+d+e+f))/6 +             \
            (p*f)/6                                      
    c_neu = (p*a)/2 + (p*b)/2 + (p*d) +       \
            (q*(a+b+c+d+e+f))/6 +             \
            (p*f)/6                                      
    d_neu = (p*c)/3 + (p*b)/2 +               \
            (q*(a+b+c+d+e+f))/6 +             \
            (p*f)/6                                      
    e_neu = 0 +                               \
            (q*(a+b+c+d+e+f))/6 +             \
            (p*f)/6                                      
    f_neu = (p*c)/3 +                         \
            (q*(a+b+c+d+e+f))/6 +             \
            (p*f)/6                                      
    # Übernahme der neu berechneten Besucherzahlen
    a = a_neu
    b = b_neu
    c = c_neu
    d = d_neu
    e = e_neu
    f = f_neu
    # Aktualisierung des Zaehlers
    zaehler = zaehler+1
# Ausgabe der Besucherzahlen
print(a)
print(b)
print(c)
print(d)
print(e)
print(f)

Aufgabe 1

(a) Teste das Programm mit verschiedenen Anzahlen von Simulationsschritten. Was fällt auf, wenn man die Anzahl vergrößert?

(b) Für die oben beschriebene Webseitenwelt erhält man nach mehreren Simulationsschritten folgende Rankingwerte (in alphabetischer Reihenfolge):

>>> 
138.428427512
148.594193607
324.892389413
197.866104955
51.7904570016
138.428427512

Welche Schlüsse kann man jetzt über die Bedeutung der Webseiten ziehen?

(c) Bei einer Suche nach einem Stichwort wird man auf den Webseiten A, B und F fündig. In welcher Reihenfolge werden die Webseiten von einer Suchmaschine angezeigt, die den oben gezeigten Ranking-Algorithmus benutzt.

(d) Wovon hängt ein hoher Rankingwert ab? Begründe deine Aussage.

Aufgabe 2

Die Suchmaschine Google benutzt - in einer Grundversion - das folgende Simulationsprogramm. Vergleiche die hier benutzte Modellierung des Surfverhaltens mit der bisher benutzten Modellierung.

# Anzahl der Simulationsschritte
anzahlSchritte = 100
# Surf- und Sprunganteile
p = 0.8
q = 1-p
# Besucherzahlen zu Beginn
n = 1000
a = n/6
b = n/6
c = n/6
d = n/6
e = n/6
f = n/6
# Initialisierung des Zaehlers
zaehler = 0
# wiederholte Berechnung der Besucherzahlen
while zaehler < anzahlSchritte:
    # Bestimmung der neuen Besucherzahlen
    a_neu = (p*c)/3 +                (q*n)/6
    b_neu = (p*a)/2 + p*e +          (q*n)/6
    c_neu = (p*a)/2 + (p*b)/2+ p*d + (q*n)/6
    d_neu = (p*c)/3 + (p*b)/2 +      (q*n)/6
    e_neu = (p*0) +                  (q*n)/6
    f_neu = (p*c)/3 +                (q*n)/6
    # Übernahme der neu berechneten Besucherzahlen
    a = a_neu
    b = b_neu
    c = c_neu
    d = d_neu
    e = e_neu
    f = f_neu
    # Aktualisierung des Zaehlers
    zaehler = zaehler+1
# Ausgabe der Besucherzahlen
n_neu = a+b+c+d+e+f
print(n_neu)
print(a/n_neu)
print(b/n_neu)
print(c/n_neu)
print(d/n_neu)
print(e/n_neu)
print(f/n_neu)