Linkbasiertes Seitenranking

Abgabe: bis 27.6.2010

1. Schreiben Sie ein Programm, das sowohl den Page Rank als auch die von HITS verwendeten Hub und Authority Scores berechnet. Eingabe ist ein Datei, die einen gerichteten Graphen enthält, z.B. als Liste von Kanten der der Form P1 -> P2, wobei die Knoten P1 und P2 URLs und die Kante einen Link von der Seite P1 auf die Seite P2 repräsentieren. Sie können sich aussuchen, ob Sie die iterative Methode aus der Vorlesung implementieren oder das Problem in ein Eigenvektor-Problem umformulieren und dieses mit Hilfe einer Linear-Algebra-Toolbox lösen. Für erstere Methode verwenden sie als Abbruch-Kriterium, dass die Summe der Veränderungen der Gewichte kleiner als 1/10000 ist oder bereits mehr als 10000 Iterationen durchlaufen wurden. Verwenden Sie beim Page Rank d=0.85 als Damping-Faktor.
2. Übergeben Sie den folgenden Graph an ihr Programm. Vergleichen Sie den Page Rank, den Hub und den Authority Score der Knoten und interpretieren Sie diese. Vergleichen Sie auch die Anzahl der Iterationen bis zur Konvergenz.

    

   

    

3. Suchen Sie sich einige Knoten aus und vergleichen den Page Rank für verschiedene Werte von d (inklusive d = 0 und d = 1).
4. Man findet oft auch eine Page-Rank-Formel, deren erster Term (1-d) ist (anstatt (1-d)/n). Experimentieren Sie mit dieser Formel und beschreiben Sie, wie sie sich auf die resultierenden Knotenwerte auswirkt. Interpretieren Sie die Formel im Vergleich zu der Version aus der Vorlesung.
5. Führen Sie für jeden Score (PR, Hub, Authority) eine Link-Spam-Attacke durch, d.h. wählen Sie einen Knoten (aus dem Root-Set) mit niedrigem Score (Sie können für verschiedene Scores verschiedene Knoten wählen) und versuchen Sie, durch Hinzufügen von Links von diesem in andere vorhandene Knoten bzw. durch neue Knoten, die auf diesen Knoten verweisen, den Score des Knotens zu erhöhen.
6. Führen Sie auch eine reine Clique-Attack durch, d.h. bilden Sie einen vollständig vernetzten Graphen und versuchen Sie ihn so in den Graphen zu hängen, dass der Score der Seiten in der Clique dominant wird. Experimentieren Sie mit verschiedenen Clique-Größen.