Module k_core 

k-core decomposition via the Batagelj-Zaversnik linear-time bucket method.

The k-core of a graph is the maximal subgraph in which every vertex has degree at least k. The core number of a vertex v is the largest k such that v belongs to the k-core. The degeneracy of the graph is the maximum core number over all vertices (equivalently, the smallest value d such that every subgraph has a vertex of degree <= d).

Directed vs undirected

Core numbers are an undirected notion. The crate’s AdjacencyList is directed by default, so this module first materialises the symmetric adjacency (an edge u -> v contributes the undirected relation {u, v}), deduplicating parallel edges and ignoring self-loops. As a consequence a graph built with AdjacencyList::add_undirected_edge and a graph built with a single directed edge per pair yield identical core numbers.

Algorithm (Batagelj & Zaversnik, 2003), O(V + E)

Vertices are bucket-sorted by current degree into the vert array. The arrays bin (start offset of each degree bucket), pos (position of each vertex inside vert), and vert (vertices ordered by current degree) are maintained so that the minimum-degree vertex can be extracted in O(1) and a neighbour’s degree decremented (with its bucket boundary advanced) in O(1). Processing vertices left-to-right, the degree a vertex has at the moment it is processed is exactly its core number, and the processing order is a degeneracy ordering.

Structs

KCoreResult

Result of a full k-core decomposition.

Functions

core_numbers

Return only the per-vertex core numbers (core_number[v]).

degeneracy

Return the graph degeneracy (maximum core number; 0 for an empty graph).

degeneracy_ordering

Return a degeneracy ordering: the vertices in the order they are removed by the Batagelj-Zaversnik peeling (repeatedly extracting a minimum-degree vertex). The vector is a permutation of 0..graph.n.

k_core_decomposition

Compute a full k-core decomposition: per-vertex core numbers and degeneracy.

k_core_subgraph

Return the vertices of the k-core: all vertices whose core number is >= k.