kemeny_constant

kemeny_constant(G, *, weight=None)

返回给定图的Kemeny常数。

*Kemeny常数*（或Kemeny常数）是指将图 G 视为马尔可夫链时计算得到的常数。Kemeny常数是从起始状态i到从马尔可夫链的平稳分布中随机抽取的目标状态的预期时间步数。Kemeny常数与所选择的初始状态无关[1]。

Kemeny常数衡量了在图上传播所需的时间。低值表示图紧密连接，而高值表示图分散。

如果没有提供权重，则所有边的权重为1。

由于 G 表示一个马尔可夫链，权重必须为正。

Parameters:

GNetworkX图

weight字符串或None, 可选 (默认=None)

用于计算Kemeny常数的边数据键。如果为None，则每条边的权重为1。

Returns:

float

图 G 的Kemeny常数。

Raises:

NetworkXNotImplemented

如果图 G 是有向的。

NetworkXError

如果图 G 不连通，或不包含节点，或有边权重为负。

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

Examples

>>> G = nx.complete_graph(5)
>>> round(nx.kemeny_constant(G), 10)
3.2