Markov-Prozesse: PageRank < Eigenwerte < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm]P_1,...,P_n[/mm] eien Menge von Webseiten. Wir schreiben [mm]P_i \to P_j[/mm], wenn es einen Link von der Webseite [mm]P_i[/mm] zur Webseite [mm]P_j[/mm] gibt.
Eine Folge von reellen Zahlen [mm]x_1,...,x_n[/mm] nicht alle gleich 0 heißt Pagerank für die Webseiten [mm]P_1,...,P_n[/mm] wenn es ein [mm]\lambda > 0[/mm] gibt, sodass für jedes [mm]1 \leq i \leq n[/mm] gilt:
[mm]\lambda x_i = \sum_{P_j \to P_i}^{} x_j[/mm]
Das heißt: Für jedes [mm]1 \leq i \leq n[/mm]ist der Pagerank [mm]x_i[/mm] der Webseite [mm]P_i[/mm] proportional zu der Summe der Pageranks [mm]x_j[/mm] der Webseiten [mm]P_j[/mm], die auf die Webseite [mm]P_i[/mm] verlinken, wobei der Proportionalitätsfaktor [mm]\lambda[/mm] dabei nicht von [mm]i[/mm] abhängt.
Ermitteln Sie den Pagerank [mm](x_1,x_2,x_3,x_4)[/mm] für ![[]](/images/popup.gif) dieses Netzwerk. |
Hallo zusammen,
grundsätlich glaube ich eine Lösung gefunden zu haben (indem ich den Grenzvektor ermittelt habe), allerdings wird dabei der Proportionaltätsfaktor überhaupt nicht berücksichtigt – und das kommt mir etwas merkwürdig vor.
Zunächst habe ich aus dem Graphen die folgende Übergangsmatrix erstellt:
[mm]P := \pmat{ 0 & 0,5 & 0 & 0 \\ 0,5 & 0 & 1 & 1 \\ 0 & 0,5 & 0 & 0 \\ 0,5 & 0 & 0 & 0 } [/mm]
Nun muss nur noch das Gleichungssystem
[mm]P * \vektor{x_1 \\ x_2 \\ x_3 \\ x_4} = \vektor{x_1 \\ x_2 \\ x_3 \\ x_4}[/mm]
gelöst werden.
Aus den vier Gleichungen, die sich hier direkt ergeben, habe ich mittels Gauß ermittelt:
[mm]\pmat{ -1 & 0,5 & 0 & 0 \\ 0,5 & -1 & 1 & 1 \\ 0 & 0,5 & -1 & 0 \\ 0,5 & 0 & 0 & -1 } \leadsto \pmat{ 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & -4 \\ 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 } [/mm]
Nun setze ich [mm]x_4 := s[/mm] und erhalte
[mm]x_1-2s = 0 \Rightarrow x_1 = 2s[/mm]
[mm]x_2-4s = 0 \Rightarrow x_2 = 4s[/mm]
[mm]x_3-2s = 0 \Rightarrow x_3 = 2s[/mm]
Also ist der Grenzvektor der gesuchte Pagerank:
[mm] \vektor{2 \\ 4 \\ 2 \\ 1}[/mm]
Ein hübsches Ergebnis, das angesichts des Graphen und der Übergangsmatrix auch plausibel erscheint – aber ist es auch richtig?
Viele Grüße
Patrick
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 So 26.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
