kemeny_constant

kemeny_constant(G, *, weight=None)

返回给定图的 Kemeny 常数。

图 G 的 Kemeny 常数（或 Kemeny’s 常数）可以通过将图视为马尔可夫链来计算。Kemeny 常数是马尔可夫链中从起始状态 i 过渡到从其平稳分布中采样的随机目标状态的预期时间步数。Kemeny 常数与所选的初始状态无关 [1]。

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

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

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

参数:

GNetworkX 图

weight字符串或 None，可选（默认为 None）

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

返回值:

浮点数

图 G 的 Kemeny 常数。

抛出异常:

NetworkXNotImplemented

如果图 G 是有向图。

NetworkXError

如果图 G 不连通，或不包含任何节点，或包含带有负权重的边。

注意事项

实现基于 [2] 中的公式 (3.3)。允许自环，这表示马尔可夫链中状态可以保持不变。多条边会合并为一条边，其权重等于所有边的权重之和。

参考文献

[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

示例

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