4. Übungsblatt - Web Mining

Abgabe:: bis 24.6. on-line unter /exercises/

Schreiben Sie ein Programm, das für jeden Knoten eines Graphen

den Page Rank
den Hub Score und den Authority Score

berechnet. Eingabe ist ein gerichteter Graph, z.B. durch Auflistung aller URLs in der Form P1 -> P2 (Seite P1 hat einen Hyperlink auf Seite P2). Abbruch-Kriterium ist, wenn die Summe der Veränderungen der Gewichte einen vorgegebenen, kleinen Wert (z.B. 0.0001) nicht mehr übersteigt, bzw. nach einer vorgegebenen Maximal-Anzahl von Iterationen.

Gegeben Sei folgender Graph:

Vergleichen Sie die Werte von Page Rank, Hub und Authority Score. Beobachten Sie die Verteilung der Gewichte, sowie die Anzahl der Iterationen bis zur Konvergenz und interpretieren Sie die Resultate.
Führen Sie für jeden Score (PR, Hub, Authority) eine Link-Spam-Attacke durch, d.h. wählen Sie einen Knoten mit niedrigem Score (Sie können für verschiedene Scores verschiedene Knoten wählen) und versuchen Sie, durch Hinzufügen von Links in den vorhandenen Knoten bzw. durch neue Knoten in den Graphen den Score des gewählten Knotens zu erhöhen.
Führen Sie eine Clique-Attack durch, d.h. bilden Sie einen vollständig vernetzten Graphen (d.h. für jedes Knotenpaar gibt es einen Link) und versuchen Sie ihn so in den Graphen zu hängen, daß der Score der Seiten in der Clique dominant wird. Experimentieren Sie mit verschiedenen Clique-Größen.
Testen Sie für den Page Rank verschiedene Werte für den Damping Factor d (inklusive d = 0 und d = 1).
Man findet sehr oft auch eine Page-Rank-Formel, deren erster Term (1-d) ist (anstatt (1-d)/n). Experimentieren Sie mit dieser Formel und vergleichen Sie die Resultate mit denen der vorigen Aufgabe. Interpretieren Sie diese Version im Vergleich zu unserer Version.