K-Core Decomposition

k-core decomposition is an algorithmic method for identifying the maximal subgraph in which every vertex has degree at least k, by iteratively pruning vertices with degree below threshold. It reveals the nested hierarchical structure of networks: the 1-core contains all non-isolated nodes, the 2-core contains nodes in cycles, and higher k-cores identify increasingly resilient substructures that survive targeted attack. The decomposition is computationally efficient — O(m) for a graph with m edges — and it connects to bootstrap percolation, where the k-core is precisely the final active set under threshold-r activation. In social networks, the k-core number of a node is often a better predictor of influence than raw degree or betweenness centrality, because it captures not just how many connections a node has, but how deeply embedded those connections are in a mutually reinforcing substructure.