k-core organization of complex networks -: art. no. 040601

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.