Verringert sich der Fehler pro Scheitelpunkt über eine PageRank-Iteration monoton?

8

Es scheint mir, dass die Norm des Fehlervektors über den gesamten Graphen hinweg monoton abnehmen muss, sonst können wir nicht garantieren, dass der PageRank jemals konvergiert.

Gilt das jedoch auch für jeden Scheitelpunkt? Dh, von Iteration t zu Iteration t + 1, nimmt der quadratische Fehler eines Scheitelpunkts garantiert immer ab, wenn er sich seinem PageRank-Wert nähert? Oder ist es möglich, dass der Vertex-Quadrat-Fehler jemals zunimmt?

Dies scheint mir auch eine breitere Beziehung zu Machtiterationen im Allgemeinen zu haben? Eine Erklärung oder ein Beweis mit der Antwort wäre willkommen.

bald
quelle

Antworten:

3

Betrachten Sie den Fall einer isolierten Komponente mit einem zentralen Scheitelpunkt v, auf den die Scheitelpunkte x_1, ...., x_k zeigen. Der Anfangswert bei v ist 1 / n, und der Endwert sollte ungefähr k * die Neustartwahrscheinlichkeit / n sein. Der Wert bei v in der zweiten Runde beträgt jedoch ungefähr k / n. Wenn die Neustartwahrscheinlichkeit deutlich unter 1 / k liegt, ist der Wert weiter vom Endwert entfernt.

Zeigefinger
quelle