Minimal sets to destroy the $k$-core in random networks

We study the problem of finding the smallest set of nodes in a network whose removal results in an empty $k$-core, where the $k$-core is the subnetwork obtained after the iterative removal of all nodes of degree smaller than $k$. This problem is also known in the literature as finding the minimal contagious set. The main contribution of our work is an analysis of the performance of the recently introduced corehd algorithm [Zdeborová, Zhang, and Zhou, Sci. Rep. 6, 37954 (2016)] on random graphs taken from the configuration model via a set of deterministic differential equations. Our analyses provide upper bounds on the size of the minimal contagious set that improve over previously known bounds. Our second contribution is a heuristic called the weak-neighbor algorithm that outperforms all currently known local methods in the regimes considered.

Figure 1

Comparison of the solution of the differential equation Algorithm 2 with direct simulations of the corehd algorithm on several graphs of $2^{14}$ nodes, here with $d=7$ and $k=2$ (left-hand side) and $k=3$ (right-hand side). The time $t$ is directly related to the fraction of removed nodes of degree $\ge k$. For $k=2$ the $k$-core disappears continuously at $t_s=0.5006$ and for $k=3$ discontinuously at $t_s=0.3376$.

Figure 2

Comparison of the three algorithms (here citm with $L=10$) on Erdős-Rényi graphs for different $k$ and varying average degree.

Figure 3

Typical transition of the three algorithms. Here we set $L$ for citm-$L$ to the size of the graph. When $k$ is increased the gap between the citm algorithm and the corehd algorithm closes and they become close in terms of performance. However, it remains a gap to the weak-neighbor algorithm.