python - 特征向量中心性的快速计算在 networkx 中花费的时间太长

Question

我正在使用 networkx 计算特征向量中心性。问题是它花费的时间太长(已经运行了大约 6 个小时)。有没有更快的方法得到结果？

图中有大约 200,000 个节点和 60,000,000 条边。

Answer 1

通过查看源代码，networkx.algorithms.centrality.eigenvector 使用幂法求主特征向量。

如果您坚持使用 networkx，请像 Joel 注意到的那样使用它:

eigenvector_centrality_numpy

centrality = nx.eigenvector_centrality_numpy(G)

或者:

您可以使用使用 ARPACK 的 scipy.sparse.linalg.eigs 并请求仅返回 1 个特征向量。

玩具示例:

import scipy.sparse as sparse

X = np.array() # dimensions 200000 by 200000 as the adjacency
# Note: k=1 and you request the Largest real.
vals, vecs = sparse.linalg.eigs(X, k=1, which='LR')

在任何情况下，2000000 x 200000 都很大，根据矩阵的稀疏性和性质，算法可能需要很长时间。您还需要大量的 CPU 和 RAM。

networkx.algorithms.centrality.eigenvector 的额外提示:

如果您坚持使用 networkx，请尝试放宽公差:

eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight=None)

尝试设置 tol=1e-04 甚至 tol=1e-03