core_number

core_number(G)

返回每个节点的核心数。

一个 k-核心是指包含度数为 k 或更多的节点的最大子图。

一个节点的核心数是包含该节点的 k-核心中 k 的最大值。

Parameters:

GNetworkX 图

一个无向或有向图

Returns:

core_number字典

一个以节点为键，核心数为值的字典。

Raises:

NetworkXNotImplemented

如果 G 是多重图或包含自环。

Notes

对于有向图，节点的度数定义为入度 + 出度。

References

[1]

一种 O(m) 时间复杂度的网络核心分解算法 Vladimir Batagelj 和 Matjaz Zaversnik, 2003. https://arxiv.org/abs/cs.DS/0310049

Examples

>>> degrees = [0, 1, 2, 2, 2, 2, 3]
>>> H = nx.havel_hakimi_graph(degrees)
>>> nx.core_number(H)
{0: 1, 1: 2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 0}
>>> G = nx.DiGraph()
>>> G.add_edges_from([(1, 2), (2, 1), (2, 3), (2, 4), (3, 4), (4, 3)])
>>> nx.core_number(G)
{1: 2, 2: 2, 3: 2, 4: 2}