3

在阅读了这个网站的 PageRank 算法理论之后，我想玩一下它。我正在尝试在 Java 中实现这一点。我的意思是我想详细使用 PageRank（比如给出不同的权重等等）。为此，我需要构建超链接矩阵。如果我有 100 万个节点，那么我的超链接矩阵将是 100 万 x 100 万大小，这会导致此异常：

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

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

4

7 回答 7

8

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

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

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

二维哈希映射将仅存储 hm(0,0)=1、hm(1,2)=2 和 hm(2,1)=3 的值。因此，在一个 1,000,000 x 1,000,000 的网络图矩阵中，我预计只有几百万个值是非零的。如果每行平均只有 5 个非零值，则哈希映射将使用大约 5*(8+8+8)*10^6 字节 ~ 115mb 来存储它（8 用于左侧 int 索引，8 用于右侧 int索引，8 表示双精度值）。方阵将使用 8*10^6*10^6 ~ 7 TB。

在 Java 中实现有效的稀疏矩阵向量乘法并非易事，如果您不想花时间在算法的这方面，已经实现了一些。稀疏矩阵乘法是 pagerank 算法最难实现的方面，因此之后它变得更容易（也更有趣）。

于 2012-11-17T00:48:14.553 回答
4

Pythonnetworkx模块有一个很好的 pagerank 实现。它使用 scipy/numpy 来实现矩阵。以下关于 stackoverflow 的两个问题应该足以让您入门。

于 2012-11-12T06:04:13.910 回答
2

几点建议：

  • 使用 python，而不是 Java：python 是一种出色的原型设计语言，并且具有可用的稀疏矩阵（在 scipy 中）以及许多其他好东西。正如其他人所指出的，它也有一个 pagerank 实现。

  • 并非将数据全部存储在内存中：任何类型的轻量级数据库都可以，例如 sqlite、hibernate、...

  • 处理数据块：如果有一个大矩阵 NxN，将其分解为小块 MxM，其中 M 是 N 的一小部分，适合内存。结合稀疏矩阵，这使您可以处理非常大的 N（数亿到数十亿，具体取决于数据的稀疏程度）。

于 2012-11-16T11:10:16.660 回答
0

正如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 之类的图形数据库。

于 2012-11-12T17:21:21.753 回答
0

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

我记得Apache Giraph（另一个 Pregel），它在其基准包中包含一个 PageRank 版本。

这是一个关于 Giraph 的视频：这是一个介绍，它专门讨论了处理 PageRank。

如果这不起作用：

在 Java 中有一个 Pregel 的实现叫做GoldenOrb。

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

您必须阅读 BSP 和 PageRank 来处理您拥有的数据大小。

于 2012-11-12T17:31:27.287 回答
0

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

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

稀疏矩阵的一个缺点是，将它们中的两个相乘会得到一个稀疏得多的矩阵。但是，PageRank 算法的设计目的是让您不需要这样做：超链接矩阵是恒定的，并且只更新分数向量。

于 2012-11-12T18:09:29.397 回答
0

因为矩阵是稀疏的，所以您可以实现像 svd、pca、mds 或包含 svd 的 Lsi 这样的降维。有一个库可以实现这种称为 Jama 的过程。你可以在这里找到

于 2012-11-16T13:00:27.987 回答