graph - 是否可以在没有整个数据集的情况下进行 pagerank？

Question

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

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

那有意义吗？如果是这样，可以这样做吗？

Answer 1

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

计算特征向量的迭代方法只需要您在每次迭代时存储几个向量(它们每个都有 1000 亿个元素)。这些可能适合您的机器(对于 4 字节浮点数，每个向量需要大约 375GB)。一旦你有了一个候选的排名向量，你就可以(非常缓慢地)通过分块读取矩阵来应用你的巨型矩阵(因为你一次可以查看 320 亿行，你只需要超过 3 个块)。重复此过程，您将掌握在 pagerank 中使用的幂方法的基础知识。参见 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