second_order_centrality

second_order_centrality(G, weight='weight')

计算图 G 中节点的二阶中心性。

给定节点的二阶中心性是永久随机游走返回该节点时间的标准差：

Parameters:

G图

一个 NetworkX 连通且无向的图。

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

边属性的名称，该属性持有作为权重使用的数值。如果为 None，则每条边的权重为 1。

Returns:

nodes字典

以节点为键，二阶中心性为值的字典。

Raises:

NetworkXException

如果图 G 为空、不连通或具有负权重。

See also

betweenness_centrality

Notes

二阶中心性值越低表示中心性越高。

该算法来自 Kermarrec, Le Merrer, Sericola 和 Trédan [1]。

此代码实现了算法的分析版本，即不涉及随机游走过程的模拟。这里的随机游走是无偏的（对应于论文 [1] 中的等式 6），因此中心性值是随机游走返回时间在变换后的输入图 G（通过添加自环使每个节点的入度相等）上的标准差。

此实现的复杂度为 O(n^3)，其中 n 是图 G 的大小，这使其仅适用于小型图。

References

[1]

Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan “Second order centrality: Distributed assessment of nodes criticity in complex networks”, Elsevier Computer Communications 34(5):619-628, 2011.

Examples

>>> G = nx.star_graph(10)
>>> soc = nx.second_order_centrality(G)
>>> print(sorted(soc.items(), key=lambda x: x[1])[0][0])  # 选择第一个 id
0