"""计算特征向量中心性的函数。"""
import math
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = ["eigenvector_centrality", "eigenvector_centrality_numpy"]
[docs]
@not_implemented_for("multigraph")
@nx._dispatchable(edge_attrs="weight")
def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None, weight=None):
r"""计算图 G 的特征向量中心性。
特征向量中心性通过将其前驱节点的中心性相加来计算节点的中心性。节点 $i$ 的中心性是与最大模数的特征值 $\lambda$ 相关联的左特征向量的第 $i$ 个元素，且该特征向量 $x$ 是正的。这样的特征向量 $x$ 由以下方程定义，直到一个乘法常数：
.. math::
\lambda x^T = x^T A,
其中 $A$ 是图 G 的邻接矩阵。根据行-列乘积的定义，上述方程等价于
.. math::
\lambda x_i = \sum_{j\to i}x_j.
也就是说，将节点 $i$ 的前驱节点的特征向量中心性相加，得到乘以 $\lambda$ 的节点 $i$ 的特征向量中心性。在无向图的情况下，$x$ 也解决了熟悉的右特征向量方程 $Ax = \lambda x$。
由于 Perron-Frobenius 定理 [1]_，如果 G 是强连通的，则存在唯一的特征向量 $x$，并且其所有条目都是严格正的。
如果 G 不是强连通的，可能会有多个与 $\lambda$ 相关联的左特征向量，并且其中一些元素可能为零。
Parameters
----------
G : 图
一个 networkx 图。
max_iter : 整数，可选 (默认=100)
最大幂迭代次数。
tol : 浮点数，可选 (默认=1.0e-6)
用于检查幂迭代中收敛性的误差容限（欧几里得范数）。
nstart : 字典，可选 (默认=None)
每个节点的幂迭代的初始值。必须对所需的特征向量有一个非零投影，以使幂方法收敛。如果为 None，此实现使用全一的向量，这是一个安全的选择。
weight : None 或字符串，可选 (默认=None)
如果为 None，所有边的权重都被视为相等。否则，持有用作权重的边属性的名称。在此度量中，权重被解释为连接强度。
Returns
-------
nodes : 字典
具有特征向量中心性作为值的节点字典。相关联的向量具有单位欧几里得范数，且值是非负的。
Examples
--------
>>> G = nx.path_graph(4)
>>> centrality = nx.eigenvector_centrality(G)
>>> sorted((v, f"{c:0.2f}") for v, c in centrality.items())
[(0, '0.37'), (1, '0.60'), (2, '0.60'), (3, '0.37')]
Raises
------
NetworkXPointlessConcept
如果图 G 是空图。
NetworkXError
如果 `nstart` 中的每个值都是零。
PowerIterationFailedConvergence
如果算法在指定的幂迭代方法迭代次数内未能收敛到指定的容差。
See Also
--------
eigenvector_centrality_numpy
:func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank`
:func:`~networkx.algorithms.link_analysis.hits_alg.hits`
Notes
-----
特征向量中心性由 Landau [2]_ 为国际象棋比赛引入。后来由 Wei [3]_ 重新发现，并在体育排名的背景下由 Kendall [4]_ 推广。Berge 基于社交连接为图引入了一般定义 [5]_。Bonacich [6]_ 再次引入了特征向量中心性，并在链接分析中使其流行。
此函数计算左主导特征向量，对应于将其前驱节点的中心性相加：这是通常的方法。要首先将其后继节点的中心性相加，请使用 ``G.reverse()`` 反转图。
该实现使用幂迭代 [7]_ 从提供的向量 `nstart` 计算主导特征向量。只要 `nstart` 在主导特征向量上有一个非零投影，收敛性就得到保证，这在使用默认值时肯定发生。
当计算向量在两次迭代之间的变化小于 ``G.number_of_nodes() * tol`` 的误差容限或在 ``max_iter`` 次迭代后停止，但在第二种情况下会引发异常。
此实现使用 $(A + I)$ 而不是邻接矩阵 $A$，因为这种变化保留了特征向量，但移动了谱，从而保证了即使对于具有最大模数的负特征值的网络也能收敛。
References
----------
.. [1] Abraham Berman 和 Robert J. Plemmons。
"Nonnegative Matrices in the Mathematical Sciences."
Classics in Applied Mathematics. SIAM, 1994.
.. [2] Edmund Landau。
"Zur relativen Wertbemessung der Turnierresultate."
Deutsches Wochenschach, 11:366–369, 1895.
.. [3] Teh-Hsing Wei。
"The Algebraic Foundations of Ranking Theory."
PhD thesis, University of Cambridge, 1952.
.. [4] Maurice G. Kendall。
"Further contributions to the theory of paired comparisons."
Biometrics, 11(1):43–62, 1955.
https://www.jstor.org/stable/3001479
.. [5] Claude Berge
"Théorie des graphes et ses applications."
Dunod, Paris, France, 1958.
.. [6] Phillip Bonacich。
"Technique for analyzing overlapping memberships."
Sociological Methodology, 4:176–185, 1972.
https://www.jstor.org/stable/270732
.. [7] 幂迭代:: https://en.wikipedia.org/wiki/Power_iteration
"""
if len(G) == 0:
raise nx.NetworkXPointlessConcept(
"cannot compute centrality for the null graph"
)
# If no initial vector is provided, start with the all-ones vector.
if nstart is None:
nstart = {v: 1 for v in G}
if all(v == 0 for v in nstart.values()):
raise nx.NetworkXError("initial vector cannot have all zero values")
# Normalize the initial vector so that each entry is in [0, 1]. This is
# guaranteed to never have a divide-by-zero error by the previous line.
nstart_sum = sum(nstart.values())
x = {k: v / nstart_sum for k, v in nstart.items()}
nnodes = G.number_of_nodes()
# make up to max_iter iterations
for _ in range(max_iter):
xlast = x
x = xlast.copy() # Start with xlast times I to iterate with (A+I)
# do the multiplication y^T = x^T A (left eigenvector)
for n in x:
for nbr in G[n]:
w = G[n][nbr].get(weight, 1) if weight else 1
x[nbr] += xlast[n] * w
# Normalize the vector. The normalization denominator `norm`
# should never be zero by the Perron--Frobenius
# theorem. However, in case it is due to numerical error, we
# assume the norm to be one instead.
norm = math.hypot(*x.values()) or 1
x = {k: v / norm for k, v in x.items()}
# Check for convergence (in the L_1 norm).
if sum(abs(x[n] - xlast[n]) for n in x) < nnodes * tol:
return x
raise nx.PowerIterationFailedConvergence(max_iter)
[docs]
@nx._dispatchable(edge_attrs="weight")
def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0):
r"""计算图 G 的特征向量中心性。
特征向量中心性通过将其前驱节点的中心性相加来计算节点的中心性。节点 $i$ 的中心性是与最大模数的特征值 $\lambda$ 相关联的左特征向量的第 $i$ 个元素，且该特征向量为正。这样的特征向量 $x$ 由以下方程定义，直至一个乘法常数：
.. math::
\lambda x^T = x^T A,
其中 $A$ 是图 G 的邻接矩阵。根据行-列乘积的定义，上述方程等价于
.. math::
\lambda x_i = \sum_{j\to i}x_j.
即，将节点 $i$ 的前驱节点的特征向量中心性相加，得到乘以 $\lambda$ 的节点 $i$ 的特征向量中心性。对于无向图，$x$ 也满足熟悉的右特征向量方程 $Ax = \lambda x$。
根据 Perron-Frobenius 定理 [1]_，如果 G 是强连通的，则存在唯一的特征向量 $x$，并且其所有元素严格为正。
如果 G 不是强连通的，可能会有多个与 $\lambda$ 相关联的左特征向量，并且其中一些元素可能为零。
Parameters
----------
G : 图
一个 networkx 图。
max_iter : 整数，可选 (默认=50)
允许的最大 Arnoldi 更新迭代次数。
tol : 浮点数，可选 (默认=0)
特征值的相对精度（停止准则）。默认值 0 表示机器精度。
weight : None 或字符串，可选 (默认=None)
如果为 None，则所有边权重视为相等。否则，保留用作权重的边属性的名称。在此度量中，权重被解释为连接强度。
Returns
-------
nodes : 字典
包含节点及其特征向量中心性值的字典。相关向量具有单位欧几里得范数，且值为非负。
Examples
--------
>>> G = nx.path_graph(4)
>>> centrality = nx.eigenvector_centrality_numpy(G)
>>> print([f"{node} {centrality[node]:0.2f}" for node in centrality])
['0 0.37', '1 0.60', '2 0.60', '3 0.37']
Raises
------
NetworkXPointlessConcept
如果图 G 为空图。
ArpackNoConvergence
当未达到请求的收敛时。当前收敛的特征值和特征向量可以在异常对象的特征值和特征向量属性中找到。
See Also
--------
:func:`scipy.sparse.linalg.eigs`
eigenvector_centrality
:func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank`
:func:`~networkx.algorithms.link_analysis.hits_alg.hits`
Notes
-----
特征向量中心性由 Landau [2]_ 为国际象棋比赛引入。后来由 Wei [3]_ 重新发现，并在体育排名的背景下由 Kendall [4]_ 推广。Berge 基于社交连接为图引入了通用定义 [5]_。Bonacich [6]_ 再次引入了特征向量中心性，并在链接分析中使其流行。
此函数计算左主导特征向量，对应于前驱节点的中心性相加：这是通常的方法。要首先添加后继节点的中心性，请使用 ``G.reverse()`` 反转图。
此实现使用 :func:`SciPy 稀疏特征值求解器<scipy.sparse.linalg.eigs>` (ARPACK) 通过 Arnoldi 迭代 [7]_ 找到最大特征值/特征向量对。
References
----------
.. [1] Abraham Berman 和 Robert J. Plemmons。
"Nonnegative Matrices in the Mathematical Sciences."
Classics in Applied Mathematics. SIAM, 1994.
.. [2] Edmund Landau。
"Zur relativen Wertbemessung der Turnierresultate."
Deutsches Wochenschach, 11:366–369, 1895.
.. [3] Teh-Hsing Wei。
"The Algebraic Foundations of Ranking Theory."
PhD thesis, University of Cambridge, 1952.
.. [4] Maurice G. Kendall。
"Further contributions to the theory of paired comparisons."
Biometrics, 11(1):43–62, 1955.
https://www.jstor.org/stable/3001479
.. [5] Claude Berge
"Théorie des graphes et ses applications."
Dunod, Paris, France, 1958.
.. [6] Phillip Bonacich。
"Technique for analyzing overlapping memberships."
Sociological Methodology, 4:176–185, 1972.
https://www.jstor.org/stable/270732
.. [7] Arnoldi 迭代:: https://en.wikipedia.org/wiki/Arnoldi_iteration
"""
import numpy as np
import scipy as sp
if len(G) == 0:
raise nx.NetworkXPointlessConcept(
"cannot compute centrality for the null graph"
)
M = nx.to_scipy_sparse_array(G, nodelist=list(G), weight=weight, dtype=float)
_, eigenvector = sp.sparse.linalg.eigs(
M.T, k=1, which="LR", maxiter=max_iter, tol=tol
)
largest = eigenvector.flatten().real
norm = np.sign(largest.sum()) * sp.linalg.norm(largest)
return dict(zip(G, (largest / norm).tolist()))
