Identifying optimal targets of network attack by belief propagation

For a network formed by nodes and undirected links between pairs of nodes, the network optimal attack problem aims at deleting a minimum number of target nodes to break the network down into many small components. This problem is intrinsically related to the feedback vertex set problem that was successfully tackled by spin-glass theory and an associated belief propagation-guided decimation (BPD) algorithm [Zhou, Eur. Phys. J. B 86, 455 (2013)]. In the present work we apply the BPD algorithm (which has approximately linear time complexity) to the network optimal attack problem and demonstrate that it has much better performance than a recently proposed collective information algorithm [Morone and Makse, Nature 524, 65 (2015)] for different types of random networks and real-world network instances. The BPD-guided attack scheme often induces an abrupt collapse of the whole network, which may make it very difficult to defend.

Figure 1

The relative size $g\left(t\right)$ of the largest connected component as a function of algorithmic time $t$ for an ER network with $N={10}^5$ nodes and mean node degree $c=3$. At each time interval $\delta t=1/N$ of the targeted attack process, a node chosen by the CI algorithm or by the BPD algorithm is deleted along with all the attached links. The three sets of simulation data obtained by the CI algorithm correspond to ball radius $\ell =2$ (dotted line), $\ell =3$ (dashed line), and $\ell =4$ (long-dashed line), respectively. The BPD results (solid line) are obtained at fixed reweighting parameter $x=12$.

Figure 2

The relative size $g\left(t\right)$ of the largest connected component at algorithmic time $t$ of the BPD-guided attack process, for six real-world networks of different sizes $N$ (see Table 1): Citation (pluses), P2P (crosses), Friend (squares), Authors (circles), WebPage (triangles), Grid (diamonds). At each time interval $\delta t=1/N$ of the targeted attack process, a node chosen by the BPD algorithm (with $x=12$) is deleted along with all the attached links.

Figure 3

Performance of the BPD algorithm on ER networks of mean degree $c=3$ and different sizes $N$. The fraction $f$ of deleted nodes in each BPD step is $f=0.01$ (pluses) or $f=0.001$ (crosses). (a) The relationship between the total BPD running time $T_{\mathrm{BPD}}$ and $N$. The simulation results (pluses) are obtained on a relatively old desktop computer (Intel-6300, $1.86$ GHz, 2 GB memory). The dashed line is the fitting curve $T_{\mathrm{BPD}}=aNln\left(N\right)$ with fitting parameter $a=2.93\times {10}^{-5}$ s. (b) The relationship between the relative size $\rho$ of the attack node set and $N$. The dashed horizontal line denotes the predicted minimum value of $\rho =0.13493$ (for $N=\infty$) by the replica-symmetric mean-field theory [18].

Figure 4

Fraction $\rho$ of removed nodes for Erdös-Rényi random networks of mean degree $c$ (a) and regular random networks of degree $K$ (b). Each CI (diamond) or BPD (circle) data point is the averaged result over 48 network instances (size $N={10}^5$); the standard deviation is of order ${10}^{-4}$ and is therefore not shown. The cross symbols are the predictions of the replica-symmetric (RS) mean-field theory on the minimum relative size of the target node sets [18]. The plus symbols of (b) are the mathematical lower bound (LB) on the minimum relative size of the target node sets [19]. The reweighting parameter of the BPD algorithm is fixed to $x=12$ for ER networks and $x=7$ for RR networks; the ball radius parameter of the CI algorithm is fixed to $\ell =4$.

Figure 5

Fraction $\rho$ of removed nodes for scale-free random networks of mean degree $c$ and degree decay exponent $\gamma =3.0$ (a) and $\gamma =3.5$ (b). Each CI (diamond) or BPD (circle) data point is the averaged result over 48 network instances (size $N={10}^5$) generated through the static method [26]; the standard deviation (not shown) of each data point is of order ${10}^{-4}$. The reweighting parameter of the BPD algorithm is fixed to $x=12$; the ball radius parameter of the CI algorithm is fixed to $\ell =4$.