PageRank实现研究

Question

阅读了此网站上有关PageRank算法的理论后，我希望能够尝试一下。我正在尝试用Java实现它。我的意思是，我想详细了解PageRank（例如给不同的权重等），但这需要建立超链接矩阵。如果我有100万个节点，那么我的超链接矩阵将是100万x100万大小，这会导致出现以下异常：

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at WebGraph.main(WebGraph.java:6)

如何在Java中实现PageRank算法，有没有存储超链接矩阵的方法？

- torayeff

---

你已经在哪里寻找过了？有没有找到任何非开源实现？你考虑过自己实现吗？你对编程语言有任何偏好吗？ - acattle

@acattle 我已经看过Jung和WebLA了。我想更专注于理论而不是实现。语言偏好：任何一种。 - torayeff

你尝试过增加堆大小来消除那个异常吗？ - Dan W

@DanW 我该怎么做？ - torayeff

你需要一个能够很好地存储稀疏矩阵的库，Matlab有这样的库（我相信是用C++编写的），你可以借用它，并将其链接到你的Java代码中。除非你处理小图/矩阵，否则增加堆大小只是一种临时解决方案。也许在Java中使用这个：http://introcs.cs.princeton.edu/java/44st/SparseMatrix.java.html - Adrian

投票关闭，原因是过于宽泛。 - Ciro Santilli OurBigBook.com

Answer 1

这是一篇了解页面等级的好文章。我从这里实现了一个Perl版本，与Textrank一起使用。然而，如果你只是想学习页面等级以及文章中讨论的各个方面如何影响结果（阻尼因子、直接或非直接图等），我建议在R或Octave中进行实验。如果你想学习如何高效地实现它，那么像你正在做的那样从头开始编程是最好的。

大多数网络图（或网络）非常稀疏，这意味着图的矩阵表示中的大多数条目都是零。用于表示稀疏矩阵的常见数据结构是哈希映射表，其中不存储零值。例如，如果矩阵为

1, 0, 0
0, 0, 2,
0, 3, 0

一个二维哈希映射只会存储hm(0,0)=1，hm(1,2)=2和hm(2,1)=3的值。因此，在一个1000000乘以1000000的web graph矩阵中，我预计只有几百万个非零值。如果每行平均仅有5个非零值，哈希映射将使用约5*(8+8+8)10^6字节～115mb来存储它（左侧int索引为8，右侧int索引为8，double值为8）。该方阵将使用810^6*10^6～7TB。

在Java中实现高效的稀疏矩阵-向量乘法并不容易，如果您不想花时间处理算法的这个方面，已经有一些实现了。稀疏矩阵乘法是PageRank算法中最难实现的部分，所以在此之后会变得更容易（也更有趣）。

- Jeff Kubina

Answer 2

Python的networkx模块有一个很好的PageRank实现。它使用scipy/numpy进行矩阵实现。以下两个stackoverflow上的问题应该足以让您开始。

• 如何在networkx中加权边会影响PageRank？

• Networkx：pagerank、pagerank_numpy和pagerank_scipy之间的区别？

- greeness

Answer 3

一些建议：

• 使用Python而不是Java：Python是一个非常好的原型语言，有可用的稀疏矩阵（在SciPy中），以及许多其他好处。正如其他人所指出的那样，它还有一个PageRank实现。

• 不要将所有数据都存储在内存中：任何类型的轻量级数据库都可以，例如sqlite、hibernate等。

• 按数据块工作：如果有一个大的矩阵NxN，请将其分解为小的矩阵MxM，其中M是N的一小部分，并适合内存。与稀疏矩阵相结合，这使您能够处理真正大的N（根据数据的稀疏程度，达到数十亿到数百亿）。

- Alex I

Answer 4

正如Dan W所建议的那样，尝试增加堆大小。如果您从命令行运行Java应用程序，只需添加开关-Xmx和所需的堆大小即可。假设您将Java代码编译为可运行的JAR文件，名为pagerank.jar，并且您想将堆大小设置为512 MB，则应发出以下命令：

java -jar -Xmx512m pagerank.jar

编辑： 但是这仅适用于您没有太多的“页面”...一个100万 x 100万的数组太大了，无法放入您的RAM中（1万亿次*64位双精度值=7.27595761 TB）。您应该更改算法以从磁盘加载数据块，对其进行操作并将其存储回磁盘。

您可以使用类似Neo4j的图形数据库来实现此目的。

- das_weezul

---

我有WebGraph.class文件，所以我运行了：java -Xmx2048m WebGraph，但仍然出现了OutOfMemoryError。 - torayeff

@torayeff：请查看我编辑过的回答。1百万*1百万个节点=1万亿个单元格。如果使用双数组（double可能是64位），那将会超过7TB，这可能超出了你的RAM处理能力。 - das_weezul

Answer 5

Google使用“Pregel”BSP（实际上只是关键字）框架执行PageRank。

我记得Apache Giraph（另一个Pregel），其中包括其基准套件中的PageRank版本。

这里有一个关于Giraph的视频：它是一个介绍，特别讲述了如何处理PageRank。

如果那不起作用：

在Java中有一个名为GoldenOrb的Pregel实现。

PageRank算法的伪代码在这里（使用不同的Pregel实现）。

您需要阅读有关BSP和PageRank的信息以处理您所拥有的数据量。

- Tom

Answer 6

你不需要存储整个1000000x1000000的矩阵，因为大多数矩阵条目都是零。相反，你可以（例如）为每一行存储一个非零条目列表，并编写矩阵函数直接使用它，而不将其扩展为完整矩阵。

这种压缩表示称为稀疏矩阵格式，大多数矩阵库都有构建和处理稀疏矩阵的选项。

稀疏矩阵的一个缺点是将两个稀疏矩阵相乘会得到一个远比原来稀疏的矩阵。然而，PageRank算法设计成不需要这样做：超链接矩阵是恒定的，只有分数向量被更新。

- comingstorm

Answer 7

由于矩阵是稀疏的，因此您可以实现类似于svd、pca、mds或包括svd的Lsi这样的降维。有一个库来实现这种过程，称为Jama。您可以在这里找到它。

- Lefteris Bab