"""图的直径、半径、偏心率及其他属性。"""
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = [
"eccentricity",
"diameter",
"radius",
"periphery",
"center",
"barycenter",
"resistance_distance",
"kemeny_constant",
"effective_graph_resistance",
]
def _extrema_bounding(G, compute="diameter", weight=None):
"""计算无向图 G 的请求极值距离度量
计算基于智能的下界和上界，并且在实践中是线性的节点数量，而不是二次的（除了一些边界情况，如完全图或环形图）。
Parameters
----------
G : NetworkX 图
一个无向图
compute : 表示请求度量的字符串
"diameter" 表示最大偏心距值，
"radius" 表示最小偏心距值，
"periphery" 表示偏心距等于直径的节点集合，
"center" 表示偏心距等于半径的节点集合，
"eccentricities" 表示从每个节点到 G 中所有其他节点的最大距离
weight : 字符串、函数或 None
如果这是一个字符串，则将通过具有此键的边属性访问边权重（即，连接 `u` 到 `v` 的边的权重将是 ``G.edges[u, v][weight]`` ）。如果没有这样的边属性存在，则假设边的权重为 1。
如果这是一个函数，边的权重是该函数返回的值。该函数必须接受三个位置参数：一条边的两个端点和该边的边属性字典。该函数必须返回一个数字。
如果这是 None，则每条边的权重/距离/成本为 1。
存储为浮点值的权重可能导致小的舍入误差。使用整数权重以避免这种情况。
权重应该是正的，因为它们是距离。
Returns
-------
value : 请求度量的值
"diameter" 和 "radius" 为整数，
"center" 和 "periphery" 为节点列表，
"eccentricities" 为以节点为键的偏心距值字典
Raises
------
NetworkXError
如果图由多个组件组成
ValueError
如果 `compute` 不是 "diameter"、"radius"、"periphery"、"center" 或 "eccentricities" 之一。
Notes
-----
此算法在 [1]_ 中提出，并在 [2]_ 和 [3]_ 中进一步讨论。
References
----------
.. [1] F. W. Takes, W. A. Kosters,
"Determining the diameter of small world networks."
Proceedings of the 20th ACM international conference on Information and knowledge management, 2011
https://dl.acm.org/doi/abs/10.1145/2063576.2063748
.. [2] F. W. Takes, W. A. Kosters,
"Computing the Eccentricity Distribution of Large Graphs."
Algorithms, 2013
https://www.mdpi.com/1999-4893/6/1/100
.. [3] M. Borassi, P. Crescenzi, M. Habib, W. A. Kosters, A. Marino, F. W. Takes,
"Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games. "
Theoretical Computer Science, 2015
https://www.sciencedirect.com/science/article/pii/S0304397515001644
"""
# init variables
degrees = dict(G.degree()) # start with the highest degree node
minlowernode = max(degrees, key=degrees.get)
N = len(degrees) # number of nodes
# alternate between smallest lower and largest upper bound
high = False
# status variables
ecc_lower = dict.fromkeys(G, 0)
ecc_upper = dict.fromkeys(G, N)
candidates = set(G)
# (re)set bound extremes
minlower = N
maxlower = 0
minupper = N
maxupper = 0
# repeat the following until there are no more candidates
while candidates:
if high:
current = maxuppernode # select node with largest upper bound
else:
current = minlowernode # select node with smallest lower bound
high = not high
# get distances from/to current node and derive eccentricity
dist = nx.shortest_path_length(G, source=current, weight=weight)
if len(dist) != N:
msg = "Cannot compute metric because graph is not connected."
raise nx.NetworkXError(msg)
current_ecc = max(dist.values())
# print status update
# print ("ecc of " + str(current) + " (" + str(ecc_lower[current]) + "/"
# + str(ecc_upper[current]) + ", deg: " + str(dist[current]) + ") is "
# + str(current_ecc))
# print(ecc_upper)
# (re)set bound extremes
maxuppernode = None
minlowernode = None
# update node bounds
for i in candidates:
# update eccentricity bounds
d = dist[i]
ecc_lower[i] = low = max(ecc_lower[i], max(d, (current_ecc - d)))
ecc_upper[i] = upp = min(ecc_upper[i], current_ecc + d)
# update min/max values of lower and upper bounds
minlower = min(ecc_lower[i], minlower)
maxlower = max(ecc_lower[i], maxlower)
minupper = min(ecc_upper[i], minupper)
maxupper = max(ecc_upper[i], maxupper)
# update candidate set
if compute == "diameter":
ruled_out = {
i
for i in candidates
if ecc_upper[i] <= maxlower and 2 * ecc_lower[i] >= maxupper
}
elif compute == "radius":
ruled_out = {
i
for i in candidates
if ecc_lower[i] >= minupper and ecc_upper[i] + 1 <= 2 * minlower
}
elif compute == "periphery":
ruled_out = {
i
for i in candidates
if ecc_upper[i] < maxlower
and (maxlower == maxupper or ecc_lower[i] > maxupper)
}
elif compute == "center":
ruled_out = {
i
for i in candidates
if ecc_lower[i] > minupper
and (minlower == minupper or ecc_upper[i] + 1 < 2 * minlower)
}
elif compute == "eccentricities":
ruled_out = set()
else:
msg = "compute must be one of 'diameter', 'radius', 'periphery', 'center', 'eccentricities'"
raise ValueError(msg)
ruled_out.update(i for i in candidates if ecc_lower[i] == ecc_upper[i])
candidates -= ruled_out
# for i in ruled_out:
# print("removing %g: ecc_u: %g maxl: %g ecc_l: %g maxu: %g"%
# (i,ecc_upper[i],maxlower,ecc_lower[i],maxupper))
# print("node %g: ecc_u: %g maxl: %g ecc_l: %g maxu: %g"%
# (4,ecc_upper[4],maxlower,ecc_lower[4],maxupper))
# print("NODE 4: %g"%(ecc_upper[4] <= maxlower))
# print("NODE 4: %g"%(2 * ecc_lower[4] >= maxupper))
# print("NODE 4: %g"%(ecc_upper[4] <= maxlower
# and 2 * ecc_lower[4] >= maxupper))
# updating maxuppernode and minlowernode for selection in next round
for i in candidates:
if (
minlowernode is None
or (
ecc_lower[i] == ecc_lower[minlowernode]
and degrees[i] > degrees[minlowernode]
)
or (ecc_lower[i] < ecc_lower[minlowernode])
):
minlowernode = i
if (
maxuppernode is None
or (
ecc_upper[i] == ecc_upper[maxuppernode]
and degrees[i] > degrees[maxuppernode]
)
or (ecc_upper[i] > ecc_upper[maxuppernode])
):
maxuppernode = i
# print status update
# print (" min=" + str(minlower) + "/" + str(minupper) +
# " max=" + str(maxlower) + "/" + str(maxupper) +
# " candidates: " + str(len(candidates)))
# print("cand:",candidates)
# print("ecc_l",ecc_lower)
# print("ecc_u",ecc_upper)
# wait = input("press Enter to continue")
# return the correct value of the requested metric
if compute == "diameter":
return maxlower
if compute == "radius":
return minupper
if compute == "periphery":
p = [v for v in G if ecc_lower[v] == maxlower]
return p
if compute == "center":
c = [v for v in G if ecc_upper[v] == minupper]
return c
if compute == "eccentricities":
return ecc_lower
return None
[docs]
@nx._dispatchable(edge_attrs="weight")
def eccentricity(G, v=None, sp=None, weight=None):
"""返回图 G 中节点的偏心率。
节点 v 的偏心率是从 v 到 G 中所有其他节点的最大距离。
Parameters
----------
G : NetworkX 图
一个图
v : 节点, 可选
指定节点的返回值
sp : 字典的字典, 可选
所有节点对的最短路径长度，作为一个字典的字典
weight : 字符串, 函数, 或 None (默认=None)
如果这是一个字符串，则将通过具有此键的边属性访问边权重（即，连接 `u` 到 `v` 的边的权重将是 ``G.edges[u, v][weight]`` ）。如果不存在这样的边属性，则假定边的权重为 1。
如果这是一个函数，边的权重是该函数返回的值。该函数必须接受三个位置参数：一条边的两个端点和该边的边属性字典。该函数必须返回一个数字。
如果这是 None，则每条边的权重/距离/成本为 1。
存储为浮点值的权重可能导致小的舍入误差。使用整数权重可以避免这种情况。
权重应该是正数，因为它们是距离。
Returns
-------
ecc : 字典
一个以节点为键的偏心率值字典。
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> dict(nx.eccentricity(G))
{1: 2, 2: 3, 3: 2, 4: 2, 5: 3}
>>> dict(
... nx.eccentricity(G, v=[1, 5])
... ) # 这返回节点 1 和 5 的偏心率
{1: 2, 5: 3}
"""
# if v is None: # none, use entire graph
# nodes=G.nodes()
# elif v in G: # is v a single node
# nodes=[v]
# else: # assume v is a container of nodes
# nodes=v
order = G.order()
e = {}
for n in G.nbunch_iter(v):
if sp is None:
length = nx.shortest_path_length(G, source=n, weight=weight)
L = len(length)
else:
try:
length = sp[n]
L = len(length)
except TypeError as err:
raise nx.NetworkXError('Format of "sp" is invalid.') from err
if L != order:
if G.is_directed():
msg = (
"Found infinite path length because the digraph is not"
" strongly connected"
)
else:
msg = "Found infinite path length because the graph is not" " connected"
raise nx.NetworkXError(msg)
e[n] = max(length.values())
if v in G:
return e[v] # return single value
return e
[docs]
@nx._dispatchable(edge_attrs="weight")
def diameter(G, e=None, usebounds=False, weight=None):
"""返回图 G 的直径。
直径是最大偏心率。
Parameters
----------
G : NetworkX 图
一个图
e : 偏心率字典, 可选
预先计算的偏心率字典。
weight : 字符串, 函数, 或 None
如果这是一个字符串, 则将通过具有此键的边属性访问边权重（即，连接 `u` 到 `v` 的边的权重将是 ``G.edges[u, v][weight]`` ）。如果不存在这样的边属性，则假定边的权重为 1。
如果这是一个函数，边的权重是该函数返回的值。该函数必须接受三个位置参数：一条边的两个端点和该边的边属性字典。该函数必须返回一个数字。
如果这是 None，则每条边的权重/距离/成本为 1。
存储为浮点值的权重可能导致距离上的小舍入误差。使用整数权重以避免这种情况。
权重应为正数，因为它们是距离。
Returns
-------
d : 整数
图的直径
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> nx.diameter(G)
3
See Also
--------
eccentricity
"""
if usebounds is True and e is None and not G.is_directed():
return _extrema_bounding(G, compute="diameter", weight=weight)
if e is None:
e = eccentricity(G, weight=weight)
return max(e.values())
[docs]
@nx._dispatchable(edge_attrs="weight")
def periphery(G, e=None, usebounds=False, weight=None):
"""返回图 G 的外围节点集合。
外围节点是指偏心距等于直径的节点集合。
Parameters
----------
G : NetworkX 图
一个图
e : 偏心距字典, 可选
预先计算的偏心距字典。
weight : 字符串, 函数, 或 None
如果这是一个字符串，则将通过该键访问边属性来获取边权重（即，连接 `u` 到 `v` 的边的权重将是 ``G.edges[u, v][weight]`` ）。如果不存在这样的边属性，则假定边的权重为 1。
如果这是一个函数，边的权重是该函数返回的值。该函数必须接受三个位置参数：一条边的两个端点和该边的属性字典。该函数必须返回一个数字。
如果这是 None，则每条边的权重/距离/成本为 1。
存储为浮点值的权重可能导致小的舍入误差。使用整数权重可以避免这种情况。
权重应该是正数，因为它们代表距离。
Returns
-------
p : 列表
外围节点的列表
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> nx.periphery(G)
[2, 5]
See Also
--------
barycenter
center
"""
if usebounds is True and e is None and not G.is_directed():
return _extrema_bounding(G, compute="periphery", weight=weight)
if e is None:
e = eccentricity(G, weight=weight)
diameter = max(e.values())
p = [v for v in e if e[v] == diameter]
return p
[docs]
@nx._dispatchable(edge_attrs="weight")
def radius(G, e=None, usebounds=False, weight=None):
"""返回图 G 的半径。
半径是离心率的最小值。
Parameters
----------
G : NetworkX 图
一个图
e : 离心率字典, 可选
预先计算的离心率字典。
weight : 字符串, 函数, 或 None
如果这是一个字符串, 则将通过具有此键的边属性访问边权重（即，连接 `u` 到 `v` 的边的权重将是 ``G.edges[u, v][weight]`` ）。如果不存在这样的边属性，则假定边的权重为 1。
如果这是一个函数，边的权重是该函数返回的值。该函数必须接受三个位置参数：一条边的两个端点和该边的边属性字典。该函数必须返回一个数字。
如果这是 None，则每条边的权重/距离/成本为 1。
存储为浮点值的权重可能导致距离上的小舍入误差。使用整数权重可以避免这种情况。
权重应该是正数，因为它们是距离。
Returns
-------
r : 整数
图的半径
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> nx.radius(G)
2
"""
if usebounds is True and e is None and not G.is_directed():
return _extrema_bounding(G, compute="radius", weight=weight)
if e is None:
e = eccentricity(G, weight=weight)
return min(e.values())
[docs]
@nx._dispatchable(edge_attrs="weight")
def center(G, e=None, usebounds=False, weight=None):
"""返回图 G 的中心。
中心是离心率等于半径的节点集合。
Parameters
----------
G : NetworkX 图
一个图
e : 离心率字典, 可选
预先计算的离心率字典。
weight : 字符串, 函数, 或 None
如果这是一个字符串, 则将通过该键访问边属性来获取边权重（即，连接 `u` 到 `v` 的边的权重将是 ``G.edges[u, v][weight]`` ）。如果不存在这样的边属性，则假定边的权重为 1。
如果这是一个函数，边的权重是该函数返回的值。该函数必须接受三个位置参数：一条边的两个端点和该边的边属性字典。该函数必须返回一个数字。
如果这是 None，则每条边的权重/距离/成本为 1。
存储为浮点值的权重可能导致小的舍入误差。使用整数权重可以避免这种情况。
权重应该是正数，因为它们代表距离。
Returns
-------
c : 列表
中心节点的列表
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> list(nx.center(G))
[1, 3, 4]
See Also
--------
barycenter
periphery
"""
if usebounds is True and e is None and not G.is_directed():
return _extrema_bounding(G, compute="center", weight=weight)
if e is None:
e = eccentricity(G, weight=weight)
radius = min(e.values())
p = [v for v in e if e[v] == radius]
return p
[docs]
@nx._dispatchable(edge_attrs="weight", mutates_input={"attr": 2})
def barycenter(G, weight=None, attr=None, sp=None):
r"""计算连通图的重心，可选地考虑边权重。
:dfn:`重心` 是一个
:func:`连通 <networkx.algorithms.components.is_connected>` 图
:math:`G` 的子图，由其节点 :math:`v` 组成的集合诱导，最小化目标函数
.. math::
\sum_{u \in V(G)} d_G(u, v),
其中 :math:`d_G` 是（可能加权的）:func:`路径长度
<networkx.algorithms.shortest_paths.generic.shortest_path_length>` 。
重心也称为 :dfn:`中位数` 。参见 [West01]_，第 78 页。
Parameters
----------
G : :class:`networkx.Graph`
连通图 :math:`G` 。
weight : :class:`str` , 可选
传递给
:func:`~networkx.algorithms.shortest_paths.generic.shortest_path_length` 。
attr : :class:`str` , 可选
如果给定，将目标函数的值写入每个节点的 `attr` 属性。否则不存储该值。
sp : dict of dicts, 可选
所有对最短路径长度作为字典的字典
Returns
-------
list
`G` 的节点，诱导 `G` 的重心。
Raises
------
NetworkXNoPath
如果 `G` 是不连通的。 `G` 可能对
:func:`barycenter` 显示为不连通，如果 `sp` 给定但缺少任何对的最短路径长度。
ValueError
如果 `sp` 和 `weight` 同时给定。
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> nx.barycenter(G)
[1, 3, 4]
See Also
--------
center
periphery
"""
if sp is None:
sp = nx.shortest_path_length(G, weight=weight)
else:
sp = sp.items()
if weight is not None:
raise ValueError("Cannot use both sp, weight arguments together")
smallest, barycenter_vertices, n = float("inf"), [], len(G)
for v, dists in sp:
if len(dists) < n:
raise nx.NetworkXNoPath(
f"Input graph {G} is disconnected, so every induced subgraph "
"has infinite barycentricity."
)
barycentricity = sum(dists.values())
if attr is not None:
G.nodes[v][attr] = barycentricity
if barycentricity < smallest:
smallest = barycentricity
barycenter_vertices = [v]
elif barycentricity == smallest:
barycenter_vertices.append(v)
if attr is not None:
nx._clear_cache(G)
return barycenter_vertices
[docs]
@not_implemented_for("directed")
@nx._dispatchable(edge_attrs="weight")
def resistance_distance(G, nodeA=None, nodeB=None, weight=None, invert_weight=True):
"""返回图 G 中节点对之间的电阻距离。
图的两个节点之间的电阻距离类似于将图视为一个电阻器网格，其电阻等于提供的权重 [1]_, [2]_。
如果没有提供权重，则所有边的权重为 1。
如果两个节点相同，则电阻距离为零。
Parameters
----------
G : NetworkX 图
一个图
nodeA : 节点或 None, 可选 (默认=None)
图 G 中的一个节点。
如果为 None，则使用所有节点作为源节点计算电阻距离。
nodeB : 节点或 None, 可选 (默认=None)
图 G 中的一个节点。
如果为 None，则使用所有节点作为目标节点计算电阻距离。
weight : 字符串或 None, 可选 (默认=None)
用于计算电阻距离的边数据键。
如果为 None，则每条边的权重为 1。
invert_weight : 布尔值 (默认=True)
正确计算电阻距离需要使用权重的倒数构建拉普拉斯矩阵。如果权重已经倒数，则不需要。权重不能为零。
Returns
-------
rd : 字典或浮点数
如果指定了 `nodeA` 和 `nodeB` ，则返回 `nodeA` 和 `nodeB` 之间的电阻距离。如果 `nodeA` 或 `nodeB` 未指定（默认），则返回一个字典，节点为键，电阻距离为值。
Raises
------
NetworkXNotImplemented
如果 `G` 是有向图。
NetworkXError
如果 `G` 不连通，或不包含节点，
或 `nodeA` 不在 `G` 中，或 `nodeB` 不在 `G` 中。
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> round(nx.resistance_distance(G, 1, 3), 10)
0.625
Notes
-----
实现基于 [2]_ 中的定理 A。忽略自环。多重边合并为一条边，权重等于权重的调和和。
References
----------
.. [1] 维基百科
"电阻距离"
https://en.wikipedia.org/wiki/Resistance_distance
.. [2] D. J. Klein 和 M. Randic。
"电阻距离"
J. Math. Chem. 12:81-95, 1993.
"""
import numpy as np
if len(G) == 0:
raise nx.NetworkXError("Graph G must contain at least one node.")
if not nx.is_connected(G):
raise nx.NetworkXError("Graph G must be strongly connected.")
if nodeA is not None and nodeA not in G:
raise nx.NetworkXError("Node A is not in graph G.")
if nodeB is not None and nodeB not in G:
raise nx.NetworkXError("Node B is not in graph G.")
G = G.copy()
node_list = list(G)
# Invert weights
if invert_weight and weight is not None:
if G.is_multigraph():
for u, v, k, d in G.edges(keys=True, data=True):
d[weight] = 1 / d[weight]
else:
for u, v, d in G.edges(data=True):
d[weight] = 1 / d[weight]
# Compute resistance distance using the Pseudo-inverse of the Laplacian
# Self-loops are ignored
L = nx.laplacian_matrix(G, weight=weight).todense()
Linv = np.linalg.pinv(L, hermitian=True)
# Return relevant distances
if nodeA is not None and nodeB is not None:
i = node_list.index(nodeA)
j = node_list.index(nodeB)
return Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
elif nodeA is not None:
i = node_list.index(nodeA)
d = {}
for n in G:
j = node_list.index(n)
d[n] = Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
return d
elif nodeB is not None:
j = node_list.index(nodeB)
d = {}
for n in G:
i = node_list.index(n)
d[n] = Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
return d
else:
d = {}
for n in G:
i = node_list.index(n)
d[n] = {}
for n2 in G:
j = node_list.index(n2)
d[n][n2] = (
Linv.item(i, i)
+ Linv.item(j, j)
- Linv.item(i, j)
- Linv.item(j, i)
)
return d
[docs]
@not_implemented_for("directed")
@nx._dispatchable(edge_attrs="weight")
def effective_graph_resistance(G, weight=None, invert_weight=True):
"""返回图 G 的有效图电阻。
也称为基尔霍夫指数。
有效图电阻定义为 G 中每对节点的电阻距离之和 [1]。
如果未提供权重，则所有边的权重为 1。
不连通图的有效图电阻为无穷大。
Parameters
----------
G : NetworkX 图
一个图
weight : 字符串或 None, 可选 (默认=None)
用于计算有效图电阻的边数据键。
如果为 None，则每条边的权重为 1。
invert_weight : 布尔值 (默认=True)
电阻距离的正确计算需要使用权重的倒数构建拉普拉斯矩阵。
如果权重已经倒数，则不需要。权重不能为零。
Returns
-------
RG : float
`G` 的有效图电阻。
Raises
------
NetworkXNotImplemented
如果 `G` 是有向图。
NetworkXError
如果 `G` 不包含任何节点。
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> round(nx.effective_graph_resistance(G), 10)
10.25
Notes
-----
该实现基于 [2] 中的定理 2.2。忽略自环。
多重边被合并为一条边，权重等于权重的调和和。
References
----------
.. [1] Wolfram
"Kirchhoff Index."
https://mathworld.wolfram.com/KirchhoffIndex.html
.. [2] W. Ellens, F. M. Spieksma, P. Van Mieghem, A. Jamakovic, R. E. Kooij.
Effective graph resistance.
Lin. Alg. Appl. 435:2491-2506, 2011.
"""
import numpy as np
if len(G) == 0:
raise nx.NetworkXError("Graph G must contain at least one node.")
# Disconnected graphs have infinite Effective graph resistance
if not nx.is_connected(G):
return float("inf")
# Invert weights
G = G.copy()
if invert_weight and weight is not None:
if G.is_multigraph():
for u, v, k, d in G.edges(keys=True, data=True):
d[weight] = 1 / d[weight]
else:
for u, v, d in G.edges(data=True):
d[weight] = 1 / d[weight]
# Get Laplacian eigenvalues
mu = np.sort(nx.laplacian_spectrum(G, weight=weight))
# Compute Effective graph resistance based on spectrum of the Laplacian
# Self-loops are ignored
return float(np.sum(1 / mu[1:]) * G.number_of_nodes())
[docs]
@nx.utils.not_implemented_for("directed")
@nx._dispatchable(edge_attrs="weight")
def kemeny_constant(G, *, weight=None):
"""返回给定图的Kemeny常数。
*Kemeny常数*（或Kemeny常数）是指将图 `G` 视为马尔可夫链时计算得到的常数。Kemeny常数是从起始状态i到从马尔可夫链的平稳分布中随机抽取的目标状态的预期时间步数。Kemeny常数与所选择的初始状态无关[1]。
Kemeny常数衡量了在图上传播所需的时间。低值表示图紧密连接，而高值表示图分散。
如果没有提供权重，则所有边的权重为1。
由于 `G` 表示一个马尔可夫链，权重必须为正。
Parameters
----------
G : NetworkX图
weight : 字符串或None, 可选 (默认=None)
用于计算Kemeny常数的边数据键。如果为None，则每条边的权重为1。
Returns
-------
float
图 `G` 的Kemeny常数。
Raises
------
NetworkXNotImplemented
如果图 `G` 是有向的。
NetworkXError
如果图 `G` 不连通，或不包含节点，或有边权重为负。
Examples
--------
>>> G = nx.complete_graph(5)
>>> round(nx.kemeny_constant(G), 10)
3.2
Notes
-----
该实现基于[2]中的公式(3.3)。自环是允许的，表示状态可以保持不变的马尔可夫链。多重边被合并为一条边，权重等于各权重之和。
References
----------
.. [1] Wikipedia
"Kemeny's constant."
https://en.wikipedia.org/wiki/Kemeny%27s_constant
.. [2] Lovász L.
Random walks on graphs: A survey.
Paul Erdös is Eighty, vol. 2, Bolyai Society,
Mathematical Studies, Keszthely, Hungary (1993), pp. 1-46
"""
import numpy as np
import scipy as sp
if len(G) == 0:
raise nx.NetworkXError("Graph G must contain at least one node.")
if not nx.is_connected(G):
raise nx.NetworkXError("Graph G must be connected.")
if nx.is_negatively_weighted(G, weight=weight):
raise nx.NetworkXError("The weights of graph G must be nonnegative.")
# Compute matrix H = D^-1/2 A D^-1/2
A = nx.adjacency_matrix(G, weight=weight)
n, m = A.shape
diags = A.sum(axis=1)
with np.errstate(divide="ignore"):
diags_sqrt = 1.0 / np.sqrt(diags)
diags_sqrt[np.isinf(diags_sqrt)] = 0
DH = sp.sparse.csr_array(sp.sparse.spdiags(diags_sqrt, 0, m, n, format="csr"))
H = DH @ (A @ DH)
# Compute eigenvalues of H
eig = np.sort(sp.linalg.eigvalsh(H.todense()))
# Compute the Kemeny constant
return float(np.sum(1 / (1 - eig[:-1])))
