k-Core Organization of Complex Networks

Abstract

We analytically describe the architecture of randomly damaged uncorrelated networks as a set of successively enclosed substructures—$k$-cores. The $k$-core is the largest subgraph where vertices have at least $k$ interconnections. We find the structure of $k$-cores, their sizes, and their birthpoints—the bootstrap percolation thresholds. We show that in networks with a finite mean number $z_2$ of the second-nearest neighbors, the emergence of a $k$-core is a hybrid phase transition. In contrast, if $z_2$ diverges, the networks contain an infinite sequence of $k$-cores which are ultrarobust against random damage.