PageRank的大O复杂度是什么？

Question

我正在寻找PageRank算法的Big-O复杂度。我很难找到任何有用的信息，只找到了 O(n+m) （n - 节点数，m - 弧/边数），但我目前不相信这个复杂度。

我认为它缺乏收敛标准。我认为这并非恒定值，而是取决于图直径的收敛。可能只需要考虑一次迭代的Big-O，那么收敛就不重要了。

尽管如此，PageRank需要触及每个节点并汇总每个传入的排名，因此我预计运行时间为O(n * m)。

我错过了什么吗？有人知道关于PageRank的复杂度的有价值的来源吗？

提前致谢。

- Matthias Kricke

---

“n+m” 对我来说听起来很合理，可能还需要一些额外的“log”项，因为它需要查找一些东西。你为什么期望是“O(n*m)”呢？也就是说，你期望 PageRank 需要为整个互联网上的每对（网页、链接）执行什么操作？为什么每次发现链接时都要触及其记录中的每个页面？我知道他们说 PageRank 可以任意分散，但我不认为这意味着他们每次创建一个 <a> 标签时都会重新计算整个互联网。 - Steve Jessop

如果我理解正确的话，你是在提到一个现有的PageRank。而我所指的是当你拥有一个图并想要计算PageRank时的情况。我认为这是´O(nm)´，因为必须触及所有节点，在最坏情况下触及所有边（完全图），这将是´O(nm)´。而且你是对的，如果已经有了PageRank，就有一些技巧可以避免计算所有PageRank。但最初所有节点都具有相同的PageRank，即1/n。首先需要算法的收敛或至少一些迭代才能得到更好的值，并对新发现的内容进行一些魔法处理。 - Matthias Kricke

我不明白你的意思。有n个节点和m条边，为什么“触及所有节点并在最坏情况下触及所有边”是O(n*m)？我很确定“技巧”从一开始就开始了，所以算法不必每次启动都要触及每个节点m次。据我所知，Google曾经每天重新计算PageRank，但现在不再这样做了。实际上，它只是更新，尽管我相信他们有手段为测试目的等引导它。 - Steve Jessop

我不知道你为什么如此关心谷歌......谷歌并不是唯一对页面排序感兴趣的公司。这个算法也对许多其他应用程序有用，运行时间复杂度与此无关。O(n*m)的重点在于：您必须计算每个节点的PR。一次操作中，您将当前页面排名推送到所有邻居节点。这意味着对于每个节点（n），我们将值推送到所有相邻节点（在完全图中是m），并在那里聚合值（恒定时间）。在完成所有推送后，就可以得出所有边的新页面排名。 - Matthias Kricke

别误会，我可以想象O(n+m)是可能的，但你的论证并没有说明如何实现这个技巧。 - Matthias Kricke

请注意，PageRank并不是一个算法，而是图的属性。实际上有数十种算法可以在不同的上下文和使用不同的技术来计算它。 - phs

Answer 1

经过一些研究和深思熟虑，我得出结论：O(n+m)才是真正的答案。

因为即使在完全图中，每条边也必须经过两次。不能触及每条边，这是我思考时的错误。因此，至少要触及每个节点，这是n次，每条边要经过两次，即m次，因此大O表示法的正确答案是O(n+m)。

- Matthias Kricke

---

你能否分享一些关于计算页面排名时间复杂度的资源？我不太明白如何在小于二次方时间内完成转移矩阵和分布向量的多次矩阵乘法。谢谢！ - gvas

@gvas 的诀窍是不要那样做。你需要将其简化为更快的方式。 - Chris