$k$-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects

We develop the theory of the $k$-core (bootstrap) percolation on uncorrelated random networks with arbitrary degree distributions. We show that the $k$-core percolation is an unusual, hybrid phase transition with a jump emergence of the $k$-core as at a first order phase transition but also with a critical singularity as at a continuous transition. We describe the properties of the $k$-core, explain the meaning of the order parameter for the $k$-core percolation, and reveal the origin of the specific critical phenomena. We demonstrate that a so-called “corona” of the $k$-core plays a crucial role (corona is a subset of vertices in the $k$-core which have exactly $k$ neighbors in the $k$-core). It turns out that the $k$-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 show that a random removal of even one vertex from the $k$-core may result in the collapse of a vast region of the $k$-core around the removed vertex. The mean size of this region diverges at the critical point. We find an exact mapping of the $k$-core percolation to a model of cooperative relaxation. This model undergoes critical relaxation with a divergent rate at some critical moment.

Figure 1

(Color online) (a) A part of the $k=3$-core with a finite corona cluster which consists of vertices with exactly three edges. This cluster is shown as a grey region. Corona vertices are represented by open dots. In a treelike network only one corona cluster may connect two vertices, for example, vertices $i$ and $j$ on this figure. Removal of vertex $i$ results in pruning all vertices which belong to the corona cluster. As a result, vertex $j$ loses one neighbor (this is the neighboring corona vertex). The degree of vertex $j$ decreases by 1. (b) In a network with loops, two or more corona clusters may connect together a pair of vertices in the $k$-core. (c) In networks with nonzero clustering, a vertex in the $k$-core may be attached to a corona cluster by two or more edges. In the cases (b) and (c) a removal of the vertex $i$ results in pruning the corona vertices and, in turn, the degree of the vertex $j$ is decreased by 2.

Figure 2

(a) Schematic representation of the order parameter. $1-R$ is the probability that a given end of a randomly chosen edge in an undamaged network is a root of an infinite $(k-1)$-ary subtree. $R$ is the probability that a given end of an edge is not a root of an infinite $(k-1)$-ary subtree. (b) Schematic view of vertex configurations contributing to $M_k$ which is the probability that a vertex is in the $k$-core [see Eqs. (5, 6)]. A vertex in a treelike network belongs to the $k$-core if at least $k$ its nearest neighbors are the roots of infinite $(k-1)$-ary subtrees. The symbol $\forall$ shows that the number of nearest neighbors which are not roots of infinite $(k-1)$-ary subtrees is arbitrary.

Figure 3

(a) and (b) are graphic representations of Eqs. (7, 8), respectively. In (a) the open circle with a dashed boundary represents an unoccupied vertex. Other notations are explained in the caption to Fig. 2.

Figure 4

Dependence of the sizes of the $k$-core and the corona, $M_k$ and $M_k\left(k\right)$, respectively, on the occupation probability $p$ in the Erdős-Rényi graphs with the mean degree $z_1=10$. Solid lines show $M_k$ versus $p$, and dashed lines show $M_k\left(k\right)$ versus $p$ at $k=3$, 5, and 6. Notice that both $M_k$ and $M_k\left(k\right)$ have a square root singularity at the $k$-core percolation thresholds, but in the curves $M_{k=5,6}\left(k\right)$ this singular addition is practically unnoticeable. Notice the nonmonotonous dependence $M_k\left(k\right)$. The inset shows the fraction $P_k\left(k\right)$ of the corona vertices in the $k$-core versus $p$.

Figure 5

(Color online) Schematic representation of the three types of edges in a network (large circle) with the $k$-core (grey central region): (i) edges between vertices in the $k$-core (links between two black dots), (ii) edges between vertices which do not belong to the $k$-core (links between two open dots), and (iii) edges between vertices in the $k$-core and vertices which do not belong to the $k$-core (links between black and open dots).

Figure 6

Schematic representations of the probabilities that an edge connects together vertices of the $k$-core or that it connects vertices outside the $k$-core, (a) and (b), respectively.

Figure 7

Diagrammatic representation of the mean number ${\mathcal{P}}_l(n_0,n_1,\dots ,n_l)$ of ways to reach a vertex which is at distance $l$ from a vertex $i=0$ in the $k$-core. The path goes through vertices $m=1,2,\dots ,l-1$ with degrees $n_m$ in the $k$-core.

Figure 8

(Color online) Schematic picture of a relaxation process described by Eq. (60). An initial distribution $M_k(n,t=0)$ over states with $n=q_{\mathrm{cut}},q_{\mathrm{cut}}-1,\dots ,k$ relaxes into the final state $\left\{M_k\right(n)=0\}$ due to transitions of vertices from a state with degree $n+1$ to a state with degree $n$. Here $q_{\mathrm{cut}}$ is the maximum degree.