¿El error por vértice sobre una iteración de PageRank está disminuyendo monotónicamente?

8

Me parece que, tomada sobre todo el gráfico, la norma del vector de error debe estar disminuyendo monotónicamente, de lo contrario no podríamos garantizar que el PageRank converja alguna vez.

Sin embargo, ¿es lo mismo cierto para cada vértice? Es decir, de la iteración t a la iteración t + 1, ¿se garantiza que el error al cuadrado de un vértice siempre disminuirá a medida que se acerque a su valor de PageRank? ¿O es posible que el error de vértice al cuadrado aumente alguna vez?

¿Esto también me parece tener una relación más amplia con las iteraciones de potencia en general? Se agradecería alguna explicación o prueba con la respuesta.

pronto
fuente

Respuestas:

3

No. Considere el caso de un componente aislado con un vértice central v al que apuntan los vértices x_1, ...., x_k. El valor inicial en v es 1 / n, y el valor final debe ser aproximadamente k * la probabilidad de reinicio / n. Pero el valor en v en la segunda ronda es aproximadamente k / n. Si la probabilidad de reinicio es significativamente menor que 1 / k, entonces el valor se alejó del valor final.

dedo índice
fuente