second_order_centrality

second_order_centrality(G, weight='weight')

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

给定节点的二阶中心性是在图 G 上进行永久随机游走时，该节点返回时间的标准差。

参数:

G图

一个 NetworkX 连通无向图。

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

边的属性名称，其值用作权重。如果为 None，则每条边的权重为 1。

返回值:

nodes字典

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

抛出:

NetworkXException

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

另请参阅

betweenness_centrality

备注

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

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

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

此实现的复杂度为 O(n^3)，其中 n 是 G 的大小，使其仅适用于小型图。此实现旨在在单台机器上本地运行。

参考文献

[1] (1,2)

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.

示例

>>> G = nx.star_graph(10)
>>> soc = nx.second_order_centrality(G)
>>> print(sorted(soc.items(), key=lambda x: x[1])[0][0])  # pick first id
0