如何检查网页排名收敛？

Question

我正在编写一小段代码（顺序）来计算适度数据集的页面排名（尽管并非完全无关紧要）。

该算法是这样的：

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

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

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

对我来说这似乎效率很低。这是正确的方法吗？

Answer 1

对于每个节点，取当前迭代与最后一个迭代之间的分数差，如果此误差降至某个阈值以下，则表示该图已收敛。

TextRank的论文描述得很好：

从分配给图中每个节点的任意值开始，计算将反复进行，直到达到低于给定阈值的收敛。

当图中任何顶点的错误率降到给定阈值以下时，就会实现收敛。一个顶点的误差率被定义为顶点的“真正的”得分之间的差S（六）和在迭代计算的得分ķ，小号^ K（六）。由于实际分数是先验未知的，因此该错误率近似为两个连续迭代计算的分数之间的差：S ^（k + 1）（Vi）+ S ^（k）（Vi）。