研究的PageRank实现

从this site阅读PageRank算法的理论后，我想玩它。我想在Java中实现这一点。我的意思是我希望能够与PageRank进行比较（比如赋予不同的权重等）。为此，我需要构建超链接矩阵。如果我有1个万个节点，然后我的超级链接矩阵将100万X 1万超大，导致此异常：研究的PageRank实现

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

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

来源

2012-11-04 torayeff

你从哪里看过？你有没有发现任何非开源实现？你有没有考虑过自己实施它？你有对语言的偏好吗？ – acattle

@acattle我曾看过Jung和WebLA。我想关注理论而不是实施。语言偏好：任何。 – torayeff

你是否尝试过增加堆大小以摆脱该异常？ –

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

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

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

一个二维哈希图将仅存储于HM的值（0,0）= 1，HM（1,2）= 2，和HM（2,1 ）= 3。因此，在web graph的1,000,000乘以1,000,000的矩阵中，我预计只有几百万个值不为零。如果每行平均只有5个非零值，哈希映射将使用大约5 *（8 + 8 + 8）* 10^6个字节〜115mb来存储它（左边的int索引为8，右边的int为8索引，8为双值）。方阵将使用8 * 10^6 * 10^6〜7太字节。在Java中实现一个高效的稀疏矩阵向量乘法并不是微不足道的，如果不想为该算法的这个方面投入时间，那么已经有一些已经存在的implemented。稀疏矩阵乘法是实现pagerank算法最困难的方面，因此在这之后它变得更容易（也更有趣）。

来源

2012-11-17 00:48:14

Python networkx模块有很好的pagerank实现。它使用scipy/numpy来实现矩阵。下面两个关于stackoverflow的问题应该足以让你开始。

来源

2012-11-12 06:04:13 greeness

由于丹W¯¯建议，尝试增加堆大小。如果您从命令行运行Java应用程序，只需将交换机-Xmx添加到所需的堆大小。让我们假设你编译Java代码到名为pagerank.jar运行的JAR文件，并要将堆大小设置为512 MB，您会发出以下命令：

java -jar -Xmx512m pagerank.jar

编辑： 但是，只有作品如果你没有那么多的“页面”......一百万×一百万个阵列太大而无法放入你的RAM（1万亿次* 64位双值= 7.27595761兆兆字节）。你应该改变你的算法，从磁盘加载数据块，操作它，并将其存回磁盘。

您可以使用图形数据库，如Neo4j。

来源

2012-11-12 17:21:21

我有WebGraph.class，所以我跑：java -Xmx2048m WebGraph，但它仍然给OutOfMemoryError – torayeff

@torayeff：请参阅我编辑的答案。 1百万* 1百万个节点= 1万亿个单元。如果你使用一个双数组（double可能是64位），这个数组可能超过7TB，这可能比你的RAM可以处理的多。 –

PageRank由Google使用'Pregel'BSP（真正的关键字）框架执行。

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

Here's a video about Giraph：这是一个介绍，它具体谈到处理PageRank。

如果不工作：

在Java中有预凝胶的实现称为GoldenOrb。

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

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

来源

2012-11-12 17:31:27 Tom

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

这种压缩表示形式被称为sparse matrix格式，大多数矩阵库可以选择构建和使用稀疏矩阵。

稀疏矩阵的一个缺点是将它们中的两个相乘会导致矩阵不够稀疏。但是，PageRank算法的设计使您无需这样做：超链接矩阵是恒定的，只有得分向量被更新。

来源

2012-11-12 18:09:29 comingstorm

几点建议：

使用Python，而不是Java：蟒蛇是一个优秀的原型语言，并具有可稀疏矩阵（在SciPy的）以及许多其他的东西。正如其他人所指出的那样，它也有一个pagerank实现。
存储你的数据不是所有的内存：任何类型的轻量级数据库的就可以了，比如sqlite的，休眠，...
上的数据的瓦片工作：如果有一个大的N×N的矩阵，将其分解成小块瓷砖MxM，其中M是N的一小部分，适合记忆。结合稀疏矩阵，您可以使用非常大的N（从数亿到数十亿，取决于数据的稀疏程度）。

来源

2012-11-16 11:10:16

因为矩阵很稀疏，所以可以实现像svd，pca，mds或Lsi这样的包含svd的降维。有一个图书馆来实施这种称为贾马的过程。你可以找到它here

来源

2012-11-16 13:00:27

研究的PageRank实现

回答

相关问题