JUNG图表性能 - 致密图表上的PageRank

Question

我想知道如果我使用JUNG2和PageRank时遇到的相对较慢的性能是否合理，考虑到我正在使用的数据。

给定一个包含200个顶点和40000个边的图，计算该图的PageRank大约需要15秒。给定一个具有〜900个顶点和〜800000个边的图，计算该图的PageRank需要将近5分钟的时间。

我意识到这些图很密集，也许这自然会需要一段时间来计算。但是，这些图形并不是特别大，按照这个速度，一次只能计算一小部分图形是不可能的。 （10,000个顶点和100,000,000个边缘大约需要8个小时）。

我正在使用一个DirectedSparseGraph与基元整数作为顶点和边缘，并没有边权重。这些显然不是稀疏图，所以也许有一个更合适的图结构可用于密集图更优化？

我在服务器模式下运行带有大量堆空间的jvm，并确认整个图形适合内存，并且不使用交换。

排名结果是正确的，总和为1，并匹配荣格源和其他地方的测试示例。

也许有一个更高性能的方法和库？但是，即使速度提高了10倍，是否它的时间复杂度与边数成正比这一事实并不意味着我很快就会超出的限制，无论我使用的是什么方法？

例如，我认为只是完全跳过图表方法，并使用矩阵来表示转换概率，这可能会提供显着提升。但是 - PageRank并不是我感兴趣的唯一算法。如果我开始滚动我自己的方法来解决一个问题并引入其他几个方法。另外，我在一个慢盒子，双核1Ghz，所以，你的数字可能会好很多（比如我的第一个例子说4-5秒），但这一点成立。我主要关心的是，如果代码预计会以更快的速度运行，或者预期以对数形式进行扩展。

无论如何，谢谢你的见解。

Answer 1

tl; dr：这是PageRank算法的一个固有限制，渐近地说。

任何想要考虑所有边缘的算法将具有Omega（| E |）的时间复杂性。任何试图测量全局拓扑性质的算法（例如PageRank等特征向量度量）都必须至少查看一次边缘。

您可以通过改变Graph实现来改进性能，但最终在密集图上执行操作往往很昂贵。

框架问题：你的图的语义是什么，你希望通过 计算PageRank学到什么？你想解决什么问题？