我正在编写一个小代码(顺序)来计算适度数据集的网页排名(尽管并非完全微不足道)。
算法是这样的:
while ( not converged ) {
// Do a bunch of things to calculate PR
}
除了“收敛”标准外,我对算法很清楚。检查算法是否收敛的最佳方法是什么?我应该:
检查我是否保留了迭代中所有单个节点的 PR 的副本,并检查下一次迭代中所有节点的 PR 是否具有相同的值?
这对我来说似乎非常低效。这是正确的做法吗?
最佳答案
对于每个节点,取当前迭代与上一次迭代之间的得分差异,如果该误差低于某个阈值,则图形已经收敛。
论文 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).
关于algorithm - 如何检查 Page Rank 收敛?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28224793/