没有整个数据集,是否可以进行pagerank？

Question

对不起,如果这是愚蠢但我只是想我应该试一试.假设我有一个巨大的图表(例如,1000亿个节点).Neo4J支持32亿,其他支持或多或少相同,所以说我不能同时在数据库中拥有整个数据集,如果它是有向图(无循环)和每组节点连接,我可以在其上运行pagerank到下一组节点(因此不会向后创建新链接,只会为新数据集创建新链接).

有没有办法我可以以某种方式获取以前的pagerank分数并将它们应用于新的数据集(我只关心最新数据集的pagerank但需要先前的set的pagerank来导出最后的数据集)？

那有意义吗？如果是这样,有可能吗？

Answer 1

您需要计算1000亿到1000亿矩阵的主要特征向量.除非它非常稀疏,否则你无法将其放入机器内部.因此,当您只能一次查看矩阵的一小部分时,需要一种计算矩阵的前导特征向量的方法.

计算特征向量的迭代方法只需要在每次迭代时存储一些向量(它们每个都有1000亿个元素).这些可能适合您的机器(4字节浮动,每个矢量需要大约375GB).一旦你有一个候选的排名向量,你可以(非常缓慢地)通过读取块中的矩阵来应用你的巨型矩阵(因为你可以一次看到320亿行,你需要超过3个块).重复这个过程,你将掌握powerrank中使用的power方法的基础知识.cf http://www.ams.org/samplings/feature-column/fcarc-pagerank和http://en.wikipedia.org/wiki/Power_iteration

当然,这里的限制因素是您需要检查矩阵的次数.事实证明,通过存储多个候选向量并使用一些随机算法,您可以获得较高的准确性,同时减少对数据的读取.这是应用数学世界中的当前研究课题.您可以在http://arxiv.org/abs/0909.4061,此处http://arxiv.org/abs/0909.4061以及此处http://arxiv.org/abs/0809.2274找到更多信息.这里有代码:http://code.google.com/p/redsvd/,但您不能只使用现成的数据大小来处理您正在讨论的数据.

你可以采用的另一种方法是研究"增量svd",这可能更适合你的问题,但有点复杂.请考虑以下注释:http://www.cs.usask.ca/~spiteri/CSDA-06T0909e.pdf和此论坛:https://mathoverflow.net/questions/32158/distributed-incremental-svd