<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>k</mml:mi></mml:math>-Core Organization of Complex Networks

TLDR

The k‑core is the largest subgraph in which every vertex has at least k interconnections. We analytically describe the architecture of randomly damaged uncorrelated networks as a set of successively enclosed substructures—k‑cores. We find that k‑cores have specific structures, sizes, and bootstrap percolation thresholds; their emergence is a hybrid phase transition when the mean number of second‑nearest neighbors z₂ is finite, and when z₂ diverges the networks contain an infinite sequence of ultra‑robust k‑cores.

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 birth points -- 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 ultra-robust against random damage.