kcore_decomposition

graph_tool.topology.kcore_decomposition(g, vprop=None)

Perform a k-core decomposition of the given graph.

Parameters:

gGraph

Graph to be used.

vpropVertexPropertyMap (optional, default: None)

Vertex property to store the decomposition. If None is supplied, one is created.

Returns:

kvalVertexPropertyMap

Vertex property map with the k-core decomposition, i.e. a given vertex v belongs to the kval[v]-core.

Notes

The k-core is a maximal set of vertices such that its induced subgraph only contains vertices with degree larger than or equal to k.

For directed graphs, the degree is assumed to be the total (in + out) degree.

The algorithm accepts graphs with parallel edges and self loops, in which case these edges contribute to the degree in the usual fashion.

This algorithm is described in [batagelj-algorithm] and runs in \(O(V + E)\) time.

References

[k-core]

http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29

[batagelj-algorithm]

Vladimir Batagelj, Matjaž Zaveršnik, “Fast algorithms for determining (generalized) core groups in social networks”, Advances in Data Analysis and Classification Volume 5, Issue 2, pp 129-145 (2011), DOI: 10.1007/s11634-010-0079-y [sci-hub, @tor], arXiv: cs/0310049

Examples

>>> g = gt.collection.data["netscience"]
>>> g = gt.GraphView(g, vfilt=gt.label_largest_component(g))
>>> kcore = gt.kcore_decomposition(g)
>>> gt.graph_draw(g, pos=g.vp["pos"], vertex_fill_color=kcore, vertex_text=kcore, output="netsci-kcore.svg")
<...>

K-core decomposition of a network of network scientists.