core_number#

core_number(G)[source]#

Returns the core number for each node.

A k-core is a maximal subgraph that contains nodes of degree k or more.

The core number of a node is the largest value k of a k-core containing that node.

Parameters:
GNetworkX graph

An undirected or directed graph

Returns:
core_numberdictionary

A dictionary keyed by node to the core number.

Raises:
NetworkXNotImplemented

If G is a multigraph or contains self loops.

Notes

For directed graphs the node degree is defined to be the in-degree + out-degree.

References

[1]

An O(m) Algorithm for Cores Decomposition of Networks Vladimir Batagelj and 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}

Additional backends implement this function

cugraphGPU-accelerated backend.

Directed graphs are not yet supported.