kcores

A k-core of a graph G is a maximal subgraph in which every vertex has degree at least k, where degree is the number of edges incident to the vertex within the subgraph. The k-core is obtained by repeatedly removing vertices whose degree is less than k, along with their incident edges, until all remaining vertices have degree at least k. The resulting subgraph is unique for a given k.

More generally, as k increases, the graph's k-cores form a nested sequence of subgraphs, each contained in the previous one. The core number or coreness of a vertex is the largest k for which the vertex lies in the k-core. The coreness values provide a core decomposition of the graph and give a measure of how deeply embedded a vertex is within dense regions.

Computing the k-core decomposition can be done in linear time with respect to the size of the graph, O(n + m), using a peeling process that maintains the current degree of each vertex and enqueues vertices whose degree falls below the threshold, updating neighbors as vertices are removed. For all k values, a single pass yields the core numbers for all vertices.

K-cores are used in network analysis to identify structurally important dense regions, to study resilience and connectivity, and as a preprocessing step for visualization or other algorithms. They are simple to compute and interpretable, though they do not capture all aspects of centrality or community structure and can be sensitive to graph sparsity.