$k$-Core Organization of Complex Networks

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.

Figure 1

The structure of a network with a $k$-core. The $k$-core is the internal circle. Vertices of degrees smaller than $k$ form the light- gray area. The dark- gray regions are numerous finite clusters with those vertices of degrees $q\ge k$, which do not belong to the $k$-core . These clusters are either connected to the $k$-core by less than $k$-edges or isolated from it.

Figure 2

The size of the $k$-core, $M(k)$, in the Erdős-Rényi random graph with the mean degree $z_1=10$ versus the concentration $Q$ of vertices removed at random. The highest core disappears at a very low concentration $Q\approx 1.2\%$ in contrast to the ordinary percolation threshold $Q\approx 90\%$. The inset shows the mean degree $z_1(k)$ of vertices in the $k$-core.

Figure 3

The relative sizes of the $k$-cores, $M(k)$, panel (a), and $k$-shells, $S(k)$, panel (b), in the Erdős-Rényi graphs with $z_1=10$ and 20; scale-free networks with $\gamma =2.5$, 4, and 7, and an uncorrelated network with the degree distribution of the router-level IR. The minimum degree in the scale-free networks is $q_0=1$. In the case $\gamma =2.5$, the maximum degree in the network is $q_{\mathrm{cut}}=2000$, and $c=2$; for $\gamma =4$ and 7, $c=30$ and 50, respectively.