使用 networkx 计算特征向量中心性

Question

我正在尝试使用 networkx 来计算我的图形的特征向量中心性：

import networkx as nx
import pandas as pd
import numpy as np

a = nx.eigenvector_centrality(my_graph)

但是我得到错误：

NetworkXError: eigenvector_centrality():
power iteration failed to converge in %d iterations."%(i+1))

我的图表有什么问题？

Answer 1

TL/DR：试试nx.eigenvector_centrality_numpy.

这是怎么回事：nx.eigenvector_centrality 依赖于幂迭代。它采取的行动相当于将一个向量重复乘以同一个矩阵（然后对结果进行归一化）。这通常会收敛到最大的特征向量。但是，当存在多个具有相同（最大）幅度的特征值时，它 会失败 。

您的图表是星形图。星图有多个“最大”特征值。对于只有两个“外围节点”的恒星，您可以轻松检查 sqrt(2) 和 -sqrt(2) 是否都是特征值。更一般地，sqrt(N)和-sqrt(N)都是特征值，其他特征值的量级较小。我相信对于任何二分网络，这都会发生并且标准算法会失败。

数学原因是经过n轮迭代后，解看起来像c_i lambda_i^n v_i/K_n的总和，其中c_i是一个常数取决于初始猜测，lambda_i 是第 i 个特征值，v_i 是它的特征向量，K 是归一化因子（应用于求和中的所有项）。当存在主导特征值时，lambda_i^n/K_n 对主导特征值变为非零常数，对其他特征值变为 0。

但是在您的情况下，您有两个同样大的特征值，一个是正值 (lambda_1)，另一个是负值 (lambda_2=-lambda_1)。较小特征值的贡献仍然为零。但是你还剩下 (c_1 lambda_1^n v_1 + c_2 lambda_2^n v_2)/K_n。使用 lambda_2=-lambda_1 你剩下 lambda_1^n(c_1 v_1+(-1)^n c_2v_2)/K_n。然后 K_n-> lambda_1^n 并且这个“收敛”为 c_1 v_1 + (-1)^n c_2 v_2。但是，每次迭代时，您都会从添加 v_2 的某个倍数到减去该倍数，因此它并没有真正收敛。

因此 networkx 使用的简单 eigenvalue_centrality 将不起作用。您可以改用 nx.eigenvector_centrality_numpy 以便使用 numpy。那会让你 v_1.

注意：快速浏览一下文档，我并不是 100% 肯定 numpy 算法保证是最大（正）特征值。它使用 numpy 算法来查找特征向量，但我在文档中看不到它是主要特征向量的保证。大多数寻找单个特征向量的算法都会产生主导特征向量，所以你可能没问题。

我们可以给它加一张支票：

只要nx.eigenvector_centrality_numpyreturns都是正值，Perron-Frobenius定理保证这对应最大的特征值
如果有些为零，则确定起来会有点棘手，
如果有些是负数，则不是主要特征向量。

使用 networkx 计算特征向量中心性

Using networkx to calculate eigenvector centrality

python

networkx

eigenvector