PageRank-Algorithmus: Unterschied zwischen den Versionen
K |
Ru251 (Diskussion | Beiträge) K |
||
| Zeile 4: | Zeile 4: | ||
Eine Website ist umso wichtiger, um so mehr Links von wichtigen Websites auf sie verweisen. | Eine Website ist umso wichtiger, um so mehr Links von wichtigen Websites auf sie verweisen. | ||
| + | Todo: | ||
| + | * Pagerank-Formel (vereinfachte Fassung ohne Dämpfung) | ||
| + | * alle Gleichungen müssen gleichzeitig gelöst werden. | ||
| + | * -> Aw = w in Matrix-Sprache -> Eigenwertproblem | ||
| + | * es gibt keine EW > 1 | ||
| + | * iterative Berechnung von Vektor w -> alle Pageranks | ||
| + | * dann: Interpretation mit Markow, Pagerank als stationäre Verteilung | ||
| + | |||
| + | == Hyperlink-Übergangsmatrix == | ||
== Vektoriteration == | == Vektoriteration == | ||
Betrachtet man eine diagonalisierbare Matrix A, so gibt es eine Basis aus den Eigenvektoren zu den entsprechenden Eigenwerten. Betrachte nun die Eigenwerte und sortiere sie nach der Größe des Betrags, sodass gilt <math> |λ_{1}|>|λ_{2}|\geq ... \geq |λ_{n}| </math>.Nun wählen wir einen Startvektor und erhalten eine Folge <math> (v^{(i)}) </math>, die durch sukzessives Anwenden von A definiert ist. Es gilt: <math> v^ {(i+1)} = Av^ {(i)} </math>. | Betrachtet man eine diagonalisierbare Matrix A, so gibt es eine Basis aus den Eigenvektoren zu den entsprechenden Eigenwerten. Betrachte nun die Eigenwerte und sortiere sie nach der Größe des Betrags, sodass gilt <math> |λ_{1}|>|λ_{2}|\geq ... \geq |λ_{n}| </math>.Nun wählen wir einen Startvektor und erhalten eine Folge <math> (v^{(i)}) </math>, die durch sukzessives Anwenden von A definiert ist. Es gilt: <math> v^ {(i+1)} = Av^ {(i)} </math>. | ||
| Zeile 10: | Zeile 19: | ||
==Markow-Ketten== | ==Markow-Ketten== | ||
| − | ==Dämpfungsfaktor== | + | ==Verbesserungen - Der Dämpfungsfaktor== |
==Quellen und weiterführende Links== | ==Quellen und weiterführende Links== | ||
* https://homepage.univie.ac.at/Franz.Embacher/Lehre/aussermathAnw/Google.html | * https://homepage.univie.ac.at/Franz.Embacher/Lehre/aussermathAnw/Google.html | ||
* buch dick | * buch dick | ||
Version vom 22. März 2021, 16:16 Uhr
Es gibt mehrere Milliarden Websites im Internet und doch erscheint, wenn wir bei Google beispielsweise nach "Fun Facts Heidelberg" suchen, diese Seite in verschiedenen Browsern unter den ersten zehn. Das liegt daran, dass der Suchbegriff auf einigen der Seiten keine so große Rolle spielt. Man wird feststellen, dass die ersten Ergebnisse die relevantesten sind. Aber wie schafft es die Suchmaschine die Seiten so zu sortieren? Dort kommt der PageRank-Algorithmus ins Spiel, welcher die Seiten über die Anzahl an Links mit Hilfe der linearen Algebra nach ihrer Wichtigkeit sortiert.
Prinzip des PageRank-Algorithmus
Eine Website ist umso wichtiger, um so mehr Links von wichtigen Websites auf sie verweisen.
Todo:
- Pagerank-Formel (vereinfachte Fassung ohne Dämpfung)
- alle Gleichungen müssen gleichzeitig gelöst werden.
- -> Aw = w in Matrix-Sprache -> Eigenwertproblem
- es gibt keine EW > 1
- iterative Berechnung von Vektor w -> alle Pageranks
- dann: Interpretation mit Markow, Pagerank als stationäre Verteilung
Hyperlink-Übergangsmatrix
Vektoriteration
Betrachtet man eine diagonalisierbare Matrix A, so gibt es eine Basis aus den Eigenvektoren zu den entsprechenden Eigenwerten. Betrachte nun die Eigenwerte und sortiere sie nach der Größe des Betrags, sodass gilt [math] |λ_{1}|\gt |λ_{2}|\geq ... \geq |λ_{n}| [/math].Nun wählen wir einen Startvektor und erhalten eine Folge [math] (v^{(i)}) [/math], die durch sukzessives Anwenden von A definiert ist. Es gilt: [math] v^ {(i+1)} = Av^ {(i)} [/math]. Diese Folge konvergiert bei geeigneter Wahl von dem Startvektor gegen einen Eigenvektor v der Matrix A zum Eigenwert [math] λ_{1} [/math]. Falls also k groß genug ist, gilt: [math]Av^{(k)} \approx λ_{1}v^{(k)} [/math].