如何计算百万节点上的个性化PageRank？

Question

我有一个稀疏图，包含大约一百万个节点和一千万个边。我想计算每个节点的个性化PageRank，其中node n的personalized PageRank是指：

# x_0 is a column vector of all zeros, except a 1 in the position corresponding to node n
# adjacency_matrix is a matrix with a 1 in position (i, j) if there is an edge from node i to node j

x_1 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_0
x_2 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_1
x_3 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_2

# x_3 now holds the personalized PageRank scores

# i'm basically approximating the personalized PageRank by running this for only 3 iterations

我试着用NumPy编写代码，但是运行起来太长了。（大约1秒计算每个节点的个性化PageRank）

我还尝试将x_0更改为矩阵（通过组合几个不同节点的列向量），但这也没有太大帮助，而且实际上使计算花费了更长的时间。（可能是因为矩阵密度相当快，所以不再适合RAM？我不确定）

有没有其他建议的方法来计算这个值，最好是在Python中？我还考虑过使用非矩阵的方法来计算PageRank，通过三次迭代进行一种模拟随机行走（即，我以1的分数开始每个节点，然后将该分数传播给它的邻居，等等），但我不确定这是否会更快。是吗？如果是，为什么？在

Answer 1

我本以为“PageRank”算法最好被看作是有向图http://en.wikipedia.org/wiki/Directed_graph（可能有适当的权重）。在

我喜欢位于http://networkx.lanl.org的networkx库

你会发现它还有一个“PageRank”的例子，在算法下你可以适应。在

Answer 2

在您的例子中，如果数据存储方式正确，使用模拟随机行走迭代方法应该可以很好地工作。当与节点数相比只有很少的边时（就像你的例子），我不认为矩阵方法是一个好的选择，因为它是一个非常稀疏的矩阵，但实际上这种方法意味着你要检查从I到j的任何I和j节点的存在性（顺便说一下，我不确定这些乘法运算的运行时间零分，真的需要。）

如果您的数据存储方式是，对于每个节点对象，您都有其传出链接的目的地列表，则随机漫游模拟方法将相当快速。忽略阻尼因子，这就是您在随机行走模拟的每次迭代中实际要做的事情：

for node in nodes:
    for destination in node.destinations:
        destination.pageRank += node.pageRank/len(destinations)

每次迭代的时间复杂度为O（n*k），其中n=1m，k=10。这听起来不错，如果我没有遗漏什么。在