Aufgabe:Aufgabe 1. PageRank Algorithmus
Eine Anwendung von Eigenwerttheorie ist das Ranking von Webseiten. Die grundlegende Idee ist hierbei: Eine Webseite ist umso wichtiger, je mehr ”wichtige“ Webseiten auf diese verweisen.
Sei n ∈ N. Wir modellieren ein Internet durch einen Graphen N = (V,E). Die Knoten V = {v1, . . . , vn} beschreiben hierbei die verschiedenen Webseiten. Verweist die Webseite vi auf die Webseite vj so geben wir dies durch eine gerichtete Kante zwischen vi und vj an. Formal ist also1
E ⊂ V × V.
Der naive Ansatz für eine Formel für die Wichtigkeit wi der i-ten Webseite vi wäre nun einfach die Anzahl der Webseiten vj zu zählen, die auf vi verweisen und diese mit ihrer jeweiligen Wichtigkeit wj zu skalieren:
Xn 1, falls vj auf vi verweist, wi = δij ·wj, mit δij = 0, sonst.
j=1
Hierbei könnten aber kleinere Webseiten einen Vorteil erlangen, indem sie sich in großer Zahl gegenseitig verlinken. Man normiert daher die Koeffizienten der Wichtigkeiten (die wir der Einfachheit nach wie vor wi nennen) wie folgt2:
n
δij j=1 k=1 kj
X
wi= aij·wj,wobeiaij=Pn δ.
(20 Punkte)
Auf den ersten Blick wirkt dies rekursiv, da man um die Wichtigkeit wi einer Webseite zu berechnen bereits die Wichtigkeiten wj aller Webseiten kennen muss. Die letzte Gleichung lässt sich aber als Eigenwertgleichung interpretieren:
Man definiert dazu die Matrix AN := (aij)1≤i,j≤n sowie den Vektor w = (wj)1≤j≤n und erhält
n
wi =Xaij ·wj ⇔ w=AN ·w.
j=1
Die Frage nach der Existenz eines Rankings ist also die Frage, ob es einen Eigenvektor w von AN zum Eigenwert λ = 1 gibt. In diesem Fall entsprechen die Einträge wi dieses Vektors w den Wichtigkeiten der Webseiten, und man erhält das gewünschte Ranking.
1Die Notwendigkeit gerichteter Kanten ergibt sich daraus, dass die Verlinkung einseitig sein kann: vi verweist auf vj aber vj nicht auf vi. Man beachte, dass wir in Aufgabe 4) auf Blatt 9 nur ungerichtete Graphen betrachtet hatten.
2Wir betrachten nur Beispiele, in denen auf jede Webseite mindestens einmal verwiesen wird; d.h. wir haben stets Pnk=1 δkj ̸= 0 für alle j.
b/w
Wir wollen zeigen, dass AN stets den Eigenwert λ = 1 besitzt:
(i) Zeigen Sie: Für alle 1 ≤ i ≤ n ist die Summe aller Einträge der j-ten Spalte von AN gleich 1. Folgern Sie daraus, dass die Zeilen von AN − In linear abhängig sind.
(ii) Folgern Sie aus (i), dass die Dimension dim(E1) des Eigenraums E1 zum Ei- genwert λ = 1 von AN mindestens 1 ist.
Problem/Ansatz: Ich habe leider gar keinen Ansatz für diese Aufgabe, bin echt ratlos und dankbar für Hilfe.
