graph_tool.topology.kcore_decomposition(g, vprop=None)[source]#

Perform a k-core decomposition of the given graph.


Graph to be used.

vpropVertexPropertyMap (optional, default: None)

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


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


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.



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


>>> g =["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.#