debugMinor
Is the per-vertex error over a PageRank iteration monotonically decreasing?
Viewed 0 times
errorthepagerankpervertexdecreasingiterationmonotonicallyover
Problem
It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge.
However, is the same true on a per-vertex basis? I.e., from iteration t to iteration t+1, is the squared error of a vertex guaranteed to always decrease as it moves closer to its PageRank value? Or is it possible that the vertex squared error would ever increase?
This also seems to me to have some broader relationship with power iterations in general? Some explanation or proof with the answer would be appreciated.
However, is the same true on a per-vertex basis? I.e., from iteration t to iteration t+1, is the squared error of a vertex guaranteed to always decrease as it moves closer to its PageRank value? Or is it possible that the vertex squared error would ever increase?
This also seems to me to have some broader relationship with power iterations in general? Some explanation or proof with the answer would be appreciated.
Solution
No. Consider the case of an isolated component with a central vertex v that is pointed to by vertices x_1, ...., x_k. The initial value at v is 1/n, and the final value should be roughly k * the restart probability/n. But the value at v in the second round is roughly k/n. If the restart probability is significantly less than 1/k, then the value got further from the ultimate value.
Context
StackExchange Computer Science Q#15024, answer score: 3
Revisions (0)
No revisions yet.