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

Question

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

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

Answer 1

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

如果你坚持 networkx 使用这个，正如乔尔注意到的那样：

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

Answer 2

尝试使用 eigenvector_centrality_numpy。来自文档：

This algorithm uses the SciPy sparse eigenvalue solver (ARPACK) to find the largest eigenvalue/eigenvector pair.

所以这将进行 serafeim 的计算，并进行一些额外的处理。

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

Fast calculation of eigenvector centrality takes too long in networkx

python

networkx

igraph

eigenvector