Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Lineare Algebra, Eigenwerte, PageRank Algorith

Lineare Algebra, Eigenwerte, PageRank Algorith

Universität / Fachhochschule

Körper

Tags: Eigenwerte bestimmen, Körper

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Hxknmk

Hxknmk aktiv_icon

14:41 Uhr, 24.01.2023

Antworten
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
EV × 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=1k=1 kj
X
wi= aij·wj , wobei aij=Pn δ.


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.
bw

Wir wollen zeigen, dass AN stets den Eigenwert λ =1 besitzt:
(i) Zeigen Sie: Für alle 1 ≤ in 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.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:
 
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.