"""
拉普拉斯中心性度量。
"""
import networkx as nx
__all__ = ["laplacian_centrality"]
[docs]
@nx._dispatchable(edge_attrs="weight")
def laplacian_centrality(
G, normalized=True, nodelist=None, weight="weight", walk_type=None, alpha=0.95
):
r"""计算图 `G` 中节点的拉普拉斯中心性。
节点 ``i`` 的拉普拉斯中心性是通过从图中删除节点 ``i`` 后拉普拉斯能量的下降来衡量的。拉普拉斯能量是图的拉普拉斯矩阵特征值平方和。
.. math::
C_L(u_i,G) = \frac{(\Delta E)_i}{E_L (G)} = \frac{E_L (G)-E_L (G_i)}{E_L (G)}
E_L (G) = \sum_{i=0}^n \lambda_i^2
其中 $E_L (G)$ 是图 `G` 的拉普拉斯能量，E_L (G_i) 是删除节点 ``i`` 后图 `G` 的拉普拉斯能量，$\lambda_i$ 是 `G` 的拉普拉斯矩阵的特征值。该公式显示了归一化值。如果不进行归一化，则返回右侧分子的值。
Parameters
----------
G : 图
一个 networkx 图
normalized : bool (默认 = True)
如果为 True，中心性得分会缩放，使得所有节点的总和为 1。
如果为 False，每个节点的中心性得分是该节点移除后拉普拉斯能量的下降。
nodelist : 列表, 可选 (默认 = None)
行和列的顺序根据 nodelist 中的节点确定。
如果 nodelist 为 None，则顺序由 G.nodes() 生成。
weight: 字符串或 None, 可选 (默认= `weight` )
计算拉普拉斯矩阵的可选参数 `weight` 。
用于计算矩阵中每个值的边数据键。
如果为 None，则每条边的权重为 1。
walk_type : 字符串或 None, 可选 (默认=None)
调用 :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>` 时使用的可选参数 `walk_type` 。
可以是 ``"random"`` , ``"lazy"`` , 或 ``"pagerank"`` 。如果 ``walk_type=None`` （默认），则根据 `G` 的属性选择值：
- ``walk_type="random"`` 如果 `G` 是强连通且非周期的
- ``walk_type="lazy"`` 如果 `G` 是强连通但非周期的
- ``walk_type="pagerank"`` 适用于所有其他情况。
alpha : 实数 (默认 = 0.95)
调用 :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>` 时使用的可选参数 `alpha` 。
(1 - alpha) 是与 pagerank 一起使用的传送概率。
Returns
-------
nodes : 字典
包含节点及其拉普拉斯中心性值的字典。
Examples
--------
>>> G = nx.Graph()
>>> edges = [(0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 2), (1, 4, 2), (4, 5, 1)]
>>> G.add_weighted_edges_from(edges)
>>> sorted((v, f"{c:0.2f}") for v, c in laplacian_centrality(G).items())
[(0, '0.70'), (1, '0.90'), (2, '0.28'), (3, '0.22'), (4, '0.26'), (5, '0.04')]
Notes
-----
该算法基于 [1]_ 实现，并扩展到使用 ``directed_laplacian_matrix`` 函数的定向图。
Raises
------
NetworkXPointlessConcept
如果图 `G` 是空图。
ZeroDivisionError
如果图 `G` 没有边（为空）且请求归一化。
References
----------
.. [1] Qi, X., Fuller, E., Wu, Q., Wu, Y., and Zhang, C.-Q. (2012).
拉普拉斯中心性：加权网络的一种新中心性度量。
信息科学，194:240-253。
https://math.wvu.edu/~cqzhang/Publication-files/my-paper/INS-2012-Laplacian-W.pdf
See Also
--------
:func:`~networkx.linalg.laplacianmatrix.directed_laplacian_matrix`
:func:`~networkx.linalg.laplacianmatrix.laplacian_matrix`
"""
import numpy as np
import scipy as sp
if len(G) == 0:
raise nx.NetworkXPointlessConcept("null graph has no centrality defined")
if G.size(weight=weight) == 0:
if normalized:
raise ZeroDivisionError("graph with no edges has zero full energy")
return {n: 0 for n in G}
if nodelist is not None:
nodeset = set(G.nbunch_iter(nodelist))
if len(nodeset) != len(nodelist):
raise nx.NetworkXError("nodelist has duplicate nodes or nodes not in G")
nodes = nodelist + [n for n in G if n not in nodeset]
else:
nodelist = nodes = list(G)
if G.is_directed():
lap_matrix = nx.directed_laplacian_matrix(G, nodes, weight, walk_type, alpha)
else:
lap_matrix = nx.laplacian_matrix(G, nodes, weight).toarray()
full_energy = np.power(sp.linalg.eigh(lap_matrix, eigvals_only=True), 2).sum()
# calculate laplacian centrality
laplace_centralities_dict = {}
for i, node in enumerate(nodelist):
# remove row and col i from lap_matrix
all_but_i = list(np.arange(lap_matrix.shape[0]))
all_but_i.remove(i)
A_2 = lap_matrix[all_but_i, :][:, all_but_i]
# Adjust diagonal for removed row
new_diag = lap_matrix.diagonal() - abs(lap_matrix[:, i])
np.fill_diagonal(A_2, new_diag[all_but_i])
if len(all_but_i) > 0: # catches degenerate case of single node
new_energy = np.power(sp.linalg.eigh(A_2, eigvals_only=True), 2).sum()
else:
new_energy = 0.0
lapl_cent = full_energy - new_energy
if normalized:
lapl_cent = lapl_cent / full_energy
laplace_centralities_dict[node] = float(lapl_cent)
return laplace_centralities_dict
