algorithm - 如何检查 Page Rank 收敛？

Question

我正在编写一个小代码(顺序)来计算适度数据集的网页排名(尽管并非完全微不足道)。

算法是这样的:

while ( not converged ) {
   // Do a bunch of things to calculate PR
}

除了“收敛”标准外，我对算法很清楚。检查算法是否收敛的最佳方法是什么？我应该:

检查我是否保留了迭代中所有单个节点的 PR 的副本，并检查下一次迭代中所有节点的 PR 是否具有相同的值？

这对我来说似乎非常低效。这是正确的做法吗？

Answer 1

对于每个节点，取当前迭代与上一次迭代之间的得分差异，如果该误差低于某个阈值，则图形已经收敛。

论文 TextRank描述得很好:

Starting from arbitrary values assigned to each node in the graph, the computation iterates until convergence below a given threshold is achieved.

Convergence is achieved when the error rate for any vertex in the graph falls below a given threshold. The error rate of a vertex is defined as the difference between the “real” score of the vertex S(Vi) and the score computed at iteration k, S^K(Vi) . Since the real score is not known apriori, this error rate is approximated with the difference between the scores computed at two successive iterations: S^(k+1)(Vi)+S^(k)(Vi).