kk-core architecture and kk-core percolation on complex networks

We analytically describe the architecture of uncorrelated complex networks with arbitrary degree distributions as a set of successively enclosed substructures—kk-cores. We find the structure of kk-cores, their sizes, and their birth points—the bootstrap percolation thresholds. We show that in networks with a finite mean number z2z2 of the second-nearest neighbours, the emergence of a kk-core is a unique hybrid phase transition with a jump emergence of the kk-core as at a first order phase transition but also with a critical singularity as at a continuous phase transition. In contrast, if z2z2 diverges, the networks contain an infinite sequence of kk-cores which are ultra-robust against random damage. We explain the meaning of the order parameter for kk-core percolation, and reveal the origin of the specific critical phenomena. We demonstrate that a so-called “corona” of the kk-core plays a crucial role. It turns out that the kk-core percolation threshold is at the same time the percolation threshold of finite corona clusters. The mean separation of vertices in corona clusters plays the role of the correlation length and diverges at the critical point. We demonstrate that a random removal of even one vertex from the kk-core may result in the collapse of a vast region of the kk-core around the removed vertex. The mean size of this region diverges at the critical point. We find an exact mapping of kk-core percolation to a model of cooperative relaxation. This model undergoes critical relaxation with a divergent rate at some critical moment.