Spin-glass model for the $C$-dismantling problem

The $C$-dismantling (CD) problem aims at finding the minimum vertex set $\mathcal{D}$ of a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ after removing which the remaining graph will break into connected components with the size not larger than $C$. In this paper, we introduce a spin-glass model with $C+1$ integer-value states into the CD problem and then study the properties of this spin-glass model with the belief-propagation (BP) equations under the replica-symmetry ansatz. We give the lower bound ${\rho }_c$ of the relative size of $\mathcal{D}$ with finite $C$ on regular random graphs and Erdős-Rényi random graphs. We find ${\rho }_c$ will decrease gradually with growing $C$, and it converges to ${\rho }_{\infty }$ as $C\to \infty$. The CD problem is called the dismantling problem when $C$ is a small finite fraction of $\left|\mathcal{V}\right|$. Therefore, ${\rho }_{\infty }$ is also the lower bound of the dismantling problem when $\left|\mathcal{V}\right|\to \infty$. To reduce the computation complexity of the BP equations, taking the knowledge of the probability of a random selected vertex belonging to a remaining connected component with the size $A$, the original BP equations can be simplified to one with only three states when $C\to \infty$. The simplified BP equations are very similar to the BP equations of the feedback vertex set spin-glass model [H.-J. Zhou, Eur. Phys. J. B 86, 455 (2013)]. Finally, we develop two practical belief-propagation-guide decimation algorithms based on the original BP equations (CD-BPD) and the simplified BP equations (SCD-BPD) to solve the CD problem on a certain graph. Our BPD algorithms and two other state-of-art heuristic algorithms are applied on various random graphs and some real-world networks. Computation results show that the CD-BPD is the best of all tested algorithms in the case of small $C$. But considering the performance and computation consumption, we recommend using SCD-BPD for the network with a small clustering coefficient when $C$ is large.

Figure 1

(a) Fraction of vertices removed as a function of $C$ on RR graph with degree $K=6$ given by the RS mean-field method (pluses), the CD-BPD (circles), the SCD-BPD (squares) algorithms, the CI (triangles), and the NEP (crosses). (b) The same as panel (a) but on ER graphs with average degree $c=6$. (c) Scaling plot of the $({\rho }_c-{\rho }_{\infty })$ versus $C$ for RR graphs with $K=3$ (squares) where ${\rho }_{\infty }=0.24236$, $K=6$ (circles) where ${\rho }_{\infty }=0.42278$, and $K=9$ (triangles) where ${\rho }_{\infty }=0.519633$. (d) The same as (c) but on ER graphs with degree $c=5$ (squares) where ${\rho }_{\infty }=0.2785$ and $c=10$ (circles) where ${\rho }_{\infty }=0.4835$.

Figure 2

The relative size $\rho$ of set $\mathcal{D}$ for (a) the RR graph on degree $K$, (b) the ER graph on mean degree $c,$ and (c) the SF graph on mean degree $c$ with power-law exponent $\gamma =3.0$ given with the collective influence algorithm with ball radius $\ell =2$ (CI) (squares) [7], node explosive percolation algorithm with the second score definition in Ref. [8] (NEP) (empty circles), CD-BPD (triangles), and SCD-BPD (crosses) algorithms. ${\rho }_{\infty }$ is the value of ${\rho }_c$ at $C\to \infty$ predicted by the RS mean-field method (solid circles). The dashed lines are the lower bounds of the minimum FVS predicted with the RS mean-field method [5].

Figure 3

The mean value of the probability $q_i^A$ over all vertices in (a) RR graphs with degree $K=5$ and $C=2^7$ (thick solid line), $C=2^8$ (thick dashed line), and $C=2^9$ (thick dotted line) and with degree $K=10$ and $C=2^7$ (thin solid line), $C=2^8$ (thin dashed line), and $C=2^9$ (thin dotted line); (b) ER graphs with average degree $c=5$ and $C=2^7$ (thick solid line), $C=2^8$ (thick dashed line), and $C=2^9$ (thick dotted line) and with degree $c=10$ and $C=2^7$ (thin solid line), $C=2^8$ (thin dashed line), and $C=2^9$ (thin dotted line). To compare the probability distributions with different $C$ easily, these distributions are multiplied by $C$ respectively. ${\overline{q}}^0$ is not presented in these figures because it is far beyond the others.

Figure 4

The real computation time of updating all messages on a random graph. All messages are updated synchronously and in parallel on a desktop computer (AMD-2700X, dual channel memory at 2666 MHz). When $N=2^{14}$ and $K=10$ in RR graphs (pluses) or $c=10$ in ER graphs (crosses), we run $C=2^5,2^6,2^7,2^8$. When $N=2^{14}$ and $C=2^4$, we run $K=20,40,80,160,320$ in RR graphs (stars) and $c=20,40,80,160,320$ in ER graphs (squares). When $K=10$ in RR graphs (circles) or $c=10$ in ER graphs (triangles) and $C=2^4$, we run $N=2^{15},2^{16},2^{17},2^{18},2^{19}$.

Figure 5

The relative size $\rho$ of set $\mathcal{D}$ for some real-world networks as a function of $C$ given by CI (pluses), NEP (crosses), CD-BPD (triangles), and SCD-BPD (squares) algorithms. The numbers in the brackets are the clustering coefficients of the corresponding graph. (a) RoadEU (0.0671) [40], (b) PPI (0.1301) [41], (c) Grid (0.0801) [28], (d) IntNet1 (0.2522) [42], (e) Authors (0.6334) [43], (f) Citation (0.2848) [42], (g) P2P (0.0055) [42], (h) Friend(0.2367) [42], (i) Email (0.0671) [43].