Hilfe bei umfangreicher Aufgabe zum PageRank

Question

Da alle Aufgaben aufeinander aufbauen, stelle ich sie zusammen in einer Frage. Ich hoffe, ihr kennt euch mit dem PageRank aus und könnt mich schlauer machen.

Aufgabenstellung:

Aufgabe 1)
Erstelle die PageRank-Gleichungen für folgendes Web mit den Seiten A, B und C wobei A zu B und C, B zu C, C zu A verlinkt. Der Dämpfungsfaktor soll 0,5 betragen.

Verwende dabei einmal Formel (I) und einmal Formel (II).
(I) PR(Z) = (1 – d) + d * Summe aus (PR(R) / abgehende Links von R)
(II) PR(Z) = (1 – d) / 3 + d * Summe aus (PR(R) / abgehende Links von R) 
R = jede Seite, die auf Z verlinkt

Aufgabe 2)
Führe alle Schritte wie in Aufgabe 1 durch. Der Dämpfungsfaktor soll nun 0,75 betragen.

Aufgabe 3)
Löse die so entstandenen Gleichungssysteme. Welche PageRank-Werte ergeben sich?

Aufgabe 4)
Führe mit dem Jacobi-Iterationsverfahren für Gleichungssystem (a) Iterationen durch. Wann konvergieren die Werte bis auf 8 Nachkommastellen genau? Der Startwert soll 1 betragen.

Lösungsansatz Aufgabe 1
(a) Gleichungen mit (I):
PR(A) = (1 – 1/2) + 1/2 * PR(C) / 1 = 1/2 + 1/2 * PR(C)
PR(B) = (1 – 1/2) + 1/2 * PR(A) / 2 = 1/2 + 1/4 * PR(A)
PR(C) = (1 – 1/2) + 1/2 * (PR(A) / 2 + PR(B) / 1) = 1/2 + 1/4 * PR(A) + 1/2 * PR(B)

(b) Gleichungen mit (II):
PR(A) = (1 – 0,5) / 3 + 1/2 * PR(C) / 1 = 1/6 + 1/2 * PR(C)
PR(B) = (1 – 0,5) / 3 + 1/2 * PR(A) / 2 = 1/6 + 1/4 * PR(A)
PR(C) = (1 – 0,5) / 3 + 1/2 * (PR(A) / 2 + PR(B)/1) = 1/6 + 1/4 * PR(A) + 1/2 * PR(B)

Lösungsansatz Aufgabe 2
(c) Gleichungen mit (I):
PR(A) = (1 – 3/4) + 3/4 * PR(C) / 1 = 1/4 + 3/4 * PR(C)
PR(B) = (1 – 3/4) + 3/4 * PR(A) / 2 = 1/4 + 3/8 * PR(A)
PR(C) = (1 – 3/4) + 3/4 * (PR(A) / 2 + PR(B) / 1) = 1/4 + 3/8 * PR(A) + 3/4 * PR(B)

(d) Gleichungen mit (II):
PR(A) = (1 – 3/4) / 3 + 3/4 * PR(C) / 1 = 1/12 + 3/4 * PR(C)
PR(B) = (1 – 3/4) / 3 + 3/4 * PR(A) / 2 = 1/12 + 3/8 * PR(A)
PR(C) = (1 – 3/4) / 3 + 3/4 * (PR(A) / 2 + PR(B) / 1) = 1/12 + 3/8 * PR(A) + 3/4 * PR(B)

Lösungsansatz Aufgabe 3
Lösung für (a)
(1) PR(A) = 1/2 + 1/2 * PR(C)
(2) PR(B) = 1/2 + 1/4 * PR(A)
(3) PR(C) = 1/2 + 1/4 * PR(A) + 1/2 * PR(B)

(1) umformen zu PR(C) (4):
(4) PR(A) = 1/2 + 1/2 * PR(C) | * 2
(4) 2 * PR(A) = 1 + PR(C) | – 1
(4) PR(C) = 2 * PR(A) – 1

PR(A) ermitteln -> (2) und (4) in (3) einsetzen:
2 * PR(A) – 1 = 1/2 + 1/4 * PR(A) + 1/2 * (1/2 + 1/4 · PR(A))
2 * PR(A) – 1 = 1/2 + 1/4 * PR(A) + 1/4 + 1/8 * PR(A)
2 * PR(A) – 1 = 3/4 + 3/8 * PR(A) | – 3/8 * PR(A)
13/8 * PR(A) – 1 = 3/4 | + 1
13/8 * PR(A) = 7/4 | : 13/8 bzw. * 8/13
PR(A) = 14/13 bzw. 1,07692307

PR(B) ermitteln -> Wert für PR(A) in (2) einsetzen:
PR(B) = 1/2 + 1/4 * 14/13
PR(B) = 1/2 + 7/26
PR(B) = 10/13 bzw. 0,76923077

PR(C) ermitteln -> Wert für PR(A) in (4) einsetzen:
PR(C) = 2 * 14/13 – 1
PR(C) = 28/13 – 13/13
PR(C) = 15/13 bzw. 1,15384615

Bis hierhin hat alles funktioniert. Die im Folgenden errechneten Werte sollten exakt 1/3 von den Werten bei (a) betragen, also z.B. PR(A) = 14/39, PR(B) = 10/13 und PR(C) = 15/39.

Lösung für (b):
(1) PR(A) = 1/6 + 1/2 * PR(C)
(2) PR(B) = 1/6 + 1/4 * PR(A)
(3) PR(C) = 1/6 + 1/4 * PR(A) + 1/2 * PR(B)

(1) umformen zu PR(C) (4):
(4) PR(A) = 1/6 + 1/2 * PR(C) | * 2
(4) 2 * PR(A) = 1/3 + PR(C) | – 1/3
(4) PR(C) = 2 * PR(A) – 1/3

PR(A) ermitteln -> (2) und (4) in (3) einsetzen:
2 * PR(A) – 1/3 = 1/6 + 1/4 * PR(A) + 1/2 * (1/6 + 1/4 * PR(A))
2 * PR(A) – 1/3 = 1/6 + 1/4 * PR(A) + 1/12 + 1/8 * PR(A)
2 * PR(A) – 1/3 = 1/4 + 3/8 * PR(A) | - 3/8 * PR(A)
13/8 * PR(A) – 1/3 = 1/4 | + 1/3
13/8 * PR(A) = 7/12 | : 13/8 bzw. *8/13
PR(A) = 14/39 bzw. ca 0,35897436

PR(B) ermitteln -> Wert für PR(A) in (2) einsetzen:
PR(B) = 1/6 + 1/4 * 14/39
PR(B) = 1/6 + 7/78
PR(B) = 10/39 bzw. ca. 0,25641026

PR(C) ermitteln -> Wert für PR(A) in (4) einsetzen:
PR(C) = 2 * 14/39 – 1/3
PR(C) = 28/39 – 1/3
PR(C) = 15/39 bzw. ca. 0,38461538

Das Ergebnis ist so, wie ich es vermutet habe! Die Werte betragen exakt 1/3 von den mit Formel (I) errechneten Werten und ergeben in Summe exakt 1.

Lösungsversuch für (c):
(1) PR(A) = 1/4 + 3/4 * PR(C)
(2) PR(B) = 1/4 + 3/8 * PR(A)
(3) PR(C) = 1/4 + 3/8 * PR(A) + 3/4 * PR(B)

(1) umformen zu PR(C) -> (4):
(4) PR(A) = 1/4 + 3/4 * PR(C) | : 3/4 bzw. * 4/3
(4) 4/3 * PR(A) = 1/3 + PR(C) | – 1/3
(4) PR(C) = 4/3 * PR(A) – 1/3

PR(A) ermitteln -> (2) und (4) in (3) einsetzen:
4/3 * PR(A) – 1/3 = 1/4 + 3/8 * PR(A) + 1/2 * (1/2 + 1/4 · PR(A))
4/3 * PR(A) – 1/3 = 1/4 + 3/8 * PR(A) + 1/4 + 1/8 · PR(A)
4/3 * PR(A) – 1/3 = 1/2 + 1/2 * PR(A) | - 1/2 * PR(A)
5/6 * PR(A) – 1/3 = 1/2 | - 1/3
5/6 * PR(A) = 1/6 | : 5/6 bzw. * 6/5
PR(A) = 1/5

PR(B) ermitteln -> Wert für PR(A) in (2) einsetzen:
PR(B) = 1/4 + 3/8 * 1/5
PR(B) = 1/4 + 3/40
PR(B) = 13/40

PR(C) ermitteln -> Wert für PR(A) in (4) einsetzen:
PR(C) = 4/3 * 1/5 – 1/3
PR(C) = 4/15 – 1/3
PR(C) = -1/15

Hat jemand eine Erklärung für diese Werte? Oder ist dieses Lösungsverfahren aus welchen Gründen auch immer hier ungeeignet? Wie kommen Werte im Minusbereich zustande, wenn der kleinstmögliche PageRank-Wert immer (1-d) beträgt?

Lösungsversuch für (d):
(1) PR(A) = 1/12 + 3/4 * PR(C)
(2) PR(B) = 1/12 + 3/8 * PR(A)
(3) PR(C) = 1/12 + 3/8 * PR(A) + 3/4 * PR(B)

(1) umformen zu PR(C) -> (4):
(4) PR(A) = 1/12 + 3/4 * PR(C) | : 3/4 bzw. * 4/3
(4) 4/3 * PR(A) = 1/3 + PR(C) | – 1/3
(4) PR(C) = 4/3 * PR(A) – 1/3

PR(A) ermitteln -> (2) und (4) in (3) einsetzen:
4/3 * PR(A) – 1/3 = 1/12 + 3/8 * PR(A) + 3/4 * (1/12 + 3/8 * PR(A))
4/3 * PR(A) – 1/3 = 1/12 + 3/8 * PR(A) + 1/16 + 9/32 * PR(A))
4/3 * PR(A) – 1/3 = 7/48 + 21/32 * PR(A) | - 21/32 * PR(A)
65/96 * PR(A) = 7/48 | : 65/96 bzw. * 96/65
PR(A) = 14/65

PR(B) ermitteln -> Wert für PR(A) in (2) einsetzen:
PR(B) = 1/12 + 3/8 * 14/65
PR(B) = 1/4 + 21/260
PR(B) = 21/1040

PR(C) ermitteln -> Wert für PR(A) in (4) einsetzen:
PR(C) = 4/3 * 14/65 – 1/3
PR(C) = 56/195 – 1/3
PR(C) = -3/65

Hier hat sich meine Vermutung, dass die Werte von (c) exakt 1/3 der Werte von (d) betragen, nicht bestätigt.
Hat jemand eine Erklärung für diese Werte? Hier stellen sich mir die gleichen Fragen wie bei der Lösung zu (c).

Wie sind diese Werte zu verstehen?

Lösungsansatz Aufgabe 4 erfolgt im 1. Kommentar.

Comments

Lösungsansatz für Aufgabe 4
Ich verstehe hier nicht ganz, was mit „bis auf 8 Nachkommastellen genau“ gemeint ist. Heißt das, dass mind. 8 Ziffern anders als 0 hinter dem Komma sein sollen oder dass sich die ersten 8 Nachkommastellen im Wert nicht mehr verändern sollen (davon gehe ich aus)?

Iterationsverfahren für (a)
PR(A) = 1/2 + 1/2 * PR(C)
PR(B) = 1/2 + 1/4 * PR(A)
PR(C) = 1/2 + 1/4 * PR(A) + 1/2 * PR(B)

Ich habe im Internet zu dieser Iterationsberechnung Werte gefunden, die nach 12 Iterationen exakt auf die in Aufgabe 2 von mir errechneten Werte konvergieren:

Wieso ist PR(C) bereits nach dem 2. Iterationsschritt bei 1,125 und bei mir noch bei 1,25. Sollte die Summe der Pageranks nicht immer gleich der Anzahl der Seiten sein, also 3, was nur bei meinem Ergebnis der Fall ist. Nach Schritt 12 mit den korrekten Werten stimmt die Summe von 3 auch wieder und die PageRank-Werte sind absolut korrekt.
Kann mir das jemand erklären? Ich komme mit meinen Schritten auch nie exakt auf den errechneten Wert. Meine Werte konvergieren immer weiter, sodass ich nie dauerhaft 8 gleiche Nachkommestellen erhalte, nur für einen kurzen Moment in verschiedenen Iterationsschritten:
PR(A) identisch auf bis zu 8 Nachkommastellen nach Schritt 12 und 13
PR(B) identisch auf bis zu 8 Nachkommastellen nach Schritt 13 und 14
PR(C) identisch auf bis zu 8 Nachkommastellen nach Schritt 11 und 12.

Was mache ich falsch? Liegt es an Rundungs-/Rechenfehlern in Excel?

Answer 1

Deine Gleichungen stimmen soweit.

Lösungsversuch für (c):
...
PR(A) ermitteln -> (2) und (4) in (3) einsetzen:

Dann kommt ein Fehler: Du hast das (2) aus dem Fall d=0.5 verwendet, wir sind aber jetzt bei d=0.75. Das sollte auf \(a=\frac{74}{65},\, b=\frac{44}{65},\, c=\frac{77}{65}\) führen.

Bei d) hast Du dieselbe Gleichung (4) wie bei c). Das kann ja nicht sein.

Doppelnumerierungen von Gleichungen sind selten hilfreich.

Bei d) kommt natürlich jeweils 1/3 von der Lösung von c) raus. "Natürlich", weil ein LGS gelöst wird, dessen rechte Seite 1/3 der rechten Seite von c) ist, also (lineares GS!) ist die Lösung auch 1/3 der Lösung von c).

Überarbeite Deine Lösung entsprechend und schau mal, ob damit alles geklärt ist.

"Konvergenz mit 8 Nachkommastellen": Das ist eine (nicht unübliche) schwammige Ausdrucksweise. Ich würde es so verstehen wie Du: Rechne solange bis die Werte sich in den 8 NKS nicht mehr ändern.

Comments

Vielen Dank, nudger!

Ich habe die Fehler nachvollziehen können und meine sie auch beseitigt zu haben. Dennoch komme ich einfach nicht auf die von dir genannten (und richtigen) Werte. Wo verhäddere ich mich? Die fett markierten Stellen müssten doch die Fehler gewesen sein.

Lösungsversuch für (c):
(1c) PR(A) = 1/4 + 3/4 * PR(C)
(2c) PR(B) = 1/4 + 3/8 * PR(A)
(3c) PR(C) = 1/4 + 3/8 * PR(A) + 3/4 * PR(B)

(1c) umformen zu PR(C) -> (4c):
(4c) PR(A) = 1/4 + 3/4 * PR(C) | : 3/4 bzw. * 4/3
(4c) 4/3 * PR(A) = 1/3 + PR(C) | – 1/3
(4c) PR(C) = 4/3 * PR(A) – 1/3

PR(A) ermitteln -> (2c) und (4c) in (3c) einsetzen:
4/3 * PR(A) – 1/3 = 1/4 + 3/8 * PR(A) + 3/4 * (1/4 + 3/8 * PR(A))
4/3 * PR(A) – 1/3 = 1/4 + 3/8 * PR(A) + 3/16 + 9/32 * PR(A)
4/3 * PR(A) – 1/3 = 7/16 + 21/32 * PR(A) | - 21/32 * PR(A)
3/32 * PR(A) – 1/3 = 7/16 | + 1/3
3/32 * PR(A) = 37/48 | : 3/32 bzw. * 32/3
PR(A) = 83/96 ? Das stimmt doch schon wieder etwas nicht…

PR(B) ermitteln -> Wert für PR(A) in (2c) einsetzen:
…

PR(C) ermitteln -> Wert für PR(A) in (4c) einsetzen:
…

Lösungsversuch für (d):
(1d) PR(A) = 1/12 + 3/4 * PR(C)
(2d) PR(B) = 1/12 + 3/8 * PR(A)
(3d) PR(C) = 1/12 + 3/8 * PR(A) + 3/4 * PR(B)

(1d) umformen zu PR(C) -> (4d):
(4d) PR(A) = 1/12 + 3/4 * PR(C) | : 3/4 bzw. * 4/3
(4d) PR(A) = 1/9 + PR(C) | - 1/9
(4d) PR(C) = PR(A) – 1/9

PR(A) ermitteln -> (2d) und (4d) in (3d) einsetzen:
PR(A) – 1/9 = 1/12 + 3/8 * PR(A) + 3/4 * (1/12 + 3/8 * PR(A))
PR(A) – 1/9 = 1/12 + 3/8 * PR(A) + 1/16 + 9/32 * PR(A)
PR(A) – 1/9 = 7/48 + 21/32 * PR(A) | - 21/32 PR(A)
11/32 * PR(A) – 1/9 = 7/48 | + 1/9
11/32 * PR(A) = 37/144 | : 11/32 bzw. * 32/11
PR(A) = 74/99 ? Auch hier komme ich immer noch auf ein falsches Ergebnis.

PR(B) ermitteln -> Wert für PR(A) in (2d) einsetzen:
…

PR(C) ermitteln -> Wert für PR(A) in (4d) einsetzen:

---

In c)

4/3 * PR(A) – 1/3 = 7/16 + 21/32 * PR(A) | - 21/32 * PR(A)

\(\frac43-\frac{21}{32}\neq \frac3{32}\)

In d)

(4d) PR(A) = 1/12 + 3/4 * PR(C) | : 3/4 bzw. * 4/3

Im nächsten Schritt haben PR(A) und PR(C) den gleichen Faktor, das kann ja nicht sein.

---

Vielen dank! Ich konnte alle Werte ermitteln bis auf PR(C) bei (d).

Wo liegt hier noch mein Fehler?

Lösungsversuch für (d):
(1d) PR(A) = 1/12 + 3/4 * PR(C)
(2d) PR(B) = 1/12 + 3/8 * PR(A)
(3d) PR(C) = 1/12 + 3/8 * PR(A) + 3/4 * PR(B)

(1d) umformen zu PR(C) -> (4d):
(4d) PR(A) = 1/12 + 3/4 * PR(C) | : 3/4 bzw. * 4/3
(4d) 4/3 PR(A) = 1/9 + PR(C) | - 1/9
(4d) PR(C) = 4/3 * PR(A) – 1/9

PR(A) ermitteln -> (2d) und (4d) in (3d) einsetzen:
4/3 PR(A) – 1/9 = 1/12 + 3/8 * PR(A) + 3/4 * (1/12 + 3/8 * PR(A))
4/3 PR(A) – 1/9 = 1/12 + 3/8 * PR(A) + 1/16 + 9/32 * PR(A)
4/3 PR(A) – 1/9 = 7/48 + 21/32 * PR(A) | - 21/32 * PR(A)
65/96 * PR(A) – 1/9 = 7/48 | + 1/9
65/96 * PR(A) = 37/144 | : 65/96 bzw. * 96/65
PR(A) = 74/195

PR(B) ermitteln -> Wert für PR(A) in (2d) einsetzen:
PR(B) = 1/12 + 3/8 * 74/195
PR(B) = 1/12 + 37/260
PR(B) = 44/195

PR(C) ermitteln -> Wert für PR(A) in (4d) einsetzen:
PR(C) = 4/3 * 44/195 – 1/9
PR(C) = 176/585 – 1/9
PR(C) = 37/195 Es müssten doch 77/195 sein.

---

Ah Fehler gefunden: Ich habe PR(B) statt PR(A) verwendet:

PR(C) ermitteln -> Wert für PR(A) in (4d) einsetzen:
PR(C) = 4/3 * 74/195 – 1/9
PR(C) = 296/585 – 1/9
PR(C) = 77/195

Nun ist nur noch die Situation nicht geklärt, warum ich mit dem Jacobi-Iterationsverfahren auf so verschiedene Werte mit den korrekten Formeln komme (Aufgabe 4)...

---

Was heißt denn "so versch. Werte"? Ich hab selbst gerechnet und komme auch auf Deine Werte. Nach einer Weile (bei mir ca. 14) "konvergiert" das aber.

All' das ist beeinflusst von Rechnerarithmetik, Programm (Excel, MATLAB, was auch immer), und auch wie Du das LGS aufgestellt hast (die drei Gleichungen sind ja noch nicht in LGS-Form). Kleine Abweichungen sind immer möglich.

---

Hallo nudger,

was bedeutet denn "die drei Gleichungen sind ja noch nicht in LSG-Form"?
Benötigt man noch andere Gleichungen als die zuvor erstellen Gleichungen für PR(A), PR(B) und PR(C)?

Ich habe jeweils die PageRank-Gleichungen für PR(A), PR(B) und PR(C) in die Zellen geschrieben.

Der Dämpfungsfaktor ist in Zelle B3 angegeben.

Im 0 Iterationsschritt befinden sich die Startwerte "1" in den Zellen B6, C6, D6.

Im 1. Iterationsschritt befinden sich die jeweiligen PageRank-Gleichungen in Bezug zu den anderen Zellen, also

=(1-$B$3)+$B$3*(D6) für PR(A) in Zelle B7

=(1-$B$3)+$B$3*(B6/2) für PR(B) in Zelle C7

=(1-$B$3)+$B$3*(B6/2+C6) für PR(C) in Zelle D7

Die folgenden Iterationsschritte haben dann jeweils die Werte aus den Zellen davor.

Ich komme so ab der 18. Iteration auf stabile 8 Nachkommastellen.

Und bei Dir passiert das bereits nach 14 Iterationen? Sind das "normale" Abweichungen? Mir kommt das ganz schön viel vor...

Anbei meine Werte für Formel (I):

Und hier auch noch mal meine mit Formel (II) errechneten Werte.

Hier fällt auf, dass diese erst viel später auf 8 Nachkommastellen genau konvergieren. Ist das normal? Gibt es dafür einen Grund?

---

Das Jacobi-Verfahren setzt auf ein LGS der Form Ax=b auf. In dieser Form sind Deine Gleichungen erstmal nicht. Wenn man sie aber auf naheliegende Weise in die Form Ax=b bringt (alles mit den Unbekannten auf die linke Seite) und darauf das Jacobi-Verfahren ansetzt, landet man genau bei der Fixpunktiteration, die Du in Excel programmiert hast. Also entfällt der (potenzielle) Grund der unterschiedlichen Formulierung des LGS.

Es bleiben die üblichen numerischen Effekte, zu denen ich oben schon alles gesagt habe. Ja, das ist nicht ungewöhnlich (siehe Abschnitt Rechnerarithmetik in Deiner Numerik-Vorlesung).