Kcore

A k-core of a graph is a maximal subgraph in which every vertex has degree at least k within the subgraph. It is obtained by repeatedly removing vertices whose degree is less than k until all remaining vertices meet the threshold. This process, often called peeling, yields a unique subgraph for a given graph and value of k.

K-cores form a nested sequence of subgraphs: for a fixed graph, if k1 < k2 then the k2-core is contained within the k1-core. Each vertex can be assigned a core number, or coreness, which is the largest k for which the vertex lies in the k-core. The collection of coreness values across vertices provides a core decomposition of the graph, revealing a hierarchical structure of vertex centrality and cohesion.

Computationally, the core can be found efficiently using a peeling algorithm. The standard approach initializes vertex degrees, then repeatedly removes vertices with degree below k and updates the degrees of their neighbors. This procedure runs in linear time with respect to the size of the graph (O(n + m) for a graph with n vertices and m edges) for a fixed k, and there are implementations that compute the entire core decomposition in linear time overall.

Related concepts include the graph degeneracy, defined as the maximum k for which the k-core is non-empty, and various generalizations to directed graphs and hypergraphs. In directed graphs, core definitions often require minimum in-degree and/or out-degree within the subgraph. The k-core is widely used to study network resilience, identify cohesive subgraphs, and reveal core-periphery structure in complex networks.