1

我有一个包含大约一百万个节点和一千万条边的稀疏图。我想计算每个节点的个性化 PageRank，其中节点 n 的个性化 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 计算，通过模拟随机游走进行 3 次迭代（即，我以 1 的分数开始每个节点，然后将该分数传播给它的邻居，等等），但我不确定这是否会更快。会是吗？如果是，为什么？

4

2 回答 2

1

我会认为“PageRank”算法最好被视为有向图http://en.wikipedia.org/wiki/Directed_graph（可能具有适当的权重）。

我喜欢http://networkx.lanl.orgnetworkx上的图书馆

您会发现它在您可以适应的算法下也有一个“PageRank”示例。

于 2012-07-16T06:28:40.107 回答
1

在您的情况下，如果您的数据以正确的方式存储，使用模拟随机游走迭代方法应该可以正常工作。当与节点数量（如您的情况）相比，边缘很少时，我认为矩阵方法不是一个好的选择，因为它是一个非常稀疏的矩阵，但实际上这种方法意味着您正在检查对于任何 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。这听起来不错，如果我在这里没有遗漏任何东西的话。

于 2012-08-21T21:05:35.093 回答