研究的PageRank实施

Question

从这个网站阅读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,有没有办法存储超链接矩阵？

Answer 1

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

大多数Web图(或网络)非常稀疏,这意味着图的矩阵表示中的大多数条目都为零.用于表示稀疏矩阵的公共数据结构是散列映射,其中不存储零值.例如,如果矩阵是

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

二维哈希映射将仅存储hm(0,0)= 1,hm(1,2)= 2和hm(2,1)= 3的值.因此,在一个1,000,000到1,000,000的网络图表矩阵中,我预计只有几百万个值不为零.如果每行平均只有5个非零值,则哈希映射将使用大约5*(8 + 8 + 8)*10 ^ 6字节~115mb来存储它(8表示左int索引,8表示右int index,和double值为8).方阵将使用8*10 ^ 6*10 ^ 6~7太字节.

在Java中实现有效的稀疏矩阵向量乘法并非易事,如果您不想将时间用于算法的这一方面,则已经实现了一些.稀疏矩阵乘法是实现pagerank算法最困难的方面,因此之后它变得更容易(也更有趣).