Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks

The study of network robustness focuses on the way the overall functionality of a network is affected as some of its constituent parts fail. Failures can occur at random or be part of an intentional attack and, in general, networks behave differently against different removal strategies. Although much effort has been put on this topic, there is no unified framework to study the problem. While random failures have been mostly studied under percolation theory, targeted attacks have been recently restated in terms of network dismantling. In this work, we link these two approaches by performing a finite-size scaling analysis to four dismantling strategies over Erdös-Rényi networks: initial and recalculated high degree removal and initial and recalculated high betweenness removal. We find that the critical exponents associated with the initial attacks are consistent with the ones corresponding to random percolation. For recalculated high degree, the exponents seem to deviate from mean field, but the evidence is not conclusive. Finally, recalculated betweenness produces a very abrupt transition with a hump in the cluster size distribution near the critical point, resembling some explosive percolation processes.

Figure 1

Relative size of the giant component as a function of the fraction of removed nodes, averaged over ${10}^3$ realizations, for two ER networks with $\langle k\rangle =5$ and size $N$. As a reference, the dot-dashed line corresponds to node removal of a fully connected graph. The inset zooms the behavior right before the collapse produced by RB. (a) $N=250$; (b) $N=16000$.

Figure 2

Determination of the critical point $f_c$ through the crossing-point method for the four attack strategies considered. Each curve represents an average over $N_s$ independent realizations. The vertical line corresponds to the mean of the intersections and the shadowed region to the standard deviation. The values obtained are shown in Table 1. (a) ID, $N_s=2\times {10}^4$; (b) RD, $N_s=2\times {10}^4$; (c) IB, $N_s=2\times {10}^4$; (d) RB, $N_s=5\times {10}^3$.

Figure 3

Order parameter $S_1$ as a function of the fraction of nodes removed $f$ in the neighborhood of the critical point. Each panel corresponds to one of the four attack strategies studied. Data is averaged over $N_s$ independent realizations. The dashed vertical lines correspond to the value of the percolation threshold computed using the crossing method (see main text). The insets show the collapse of the curves using the scaling ansatz given by Eq. (9). The values for the percolation thresholds and critical exponents used to perform the scaling are the ones summarized in Table 1. (a) ID, $N_s=2\times {10}^4$; (b) RD, $N_s=2\times {10}^4$; (c) IB, $N_s=2\times {10}^4$; (d) RB, $N_s=5\times {10}^3$.

Figure 4

Size of the second cluster $S_{2}N$ as a function of the fraction of nodes removed $f$ for the four attack strategies studied. As it can be seen, this quantity peaks in the neighborhood of the percolation threshold (dashed vertical line). The color code and number of realizations are the same as in Fig. 3. The insets show the collapse of the curves using the scaling ansatz given by Eq. (9), with the parameters given in Table 1. (a) ID; (b) RD; (c) IB; (d) RB.

Figure 5

Susceptibility $\langle s\rangle$ as a function of the fraction of nodes removed $f$ for the four attack strategies studied. As it happens with the size of the second cluster, this quantity also peaks near the percolation threshold. The insets show the collapse of the curves using the scaling ansatz given by Eq. (10), with the parameters given in Table 1. The color code and number of realizations are the same as in Fig. 3. (a) ID; (b) RD; (c) IB; (d) RB.

Figure 6

Scaling of the peaks of $S_{2}N$ and $\langle s\rangle$ for the four attack strategies. The markers represent the value at the peak, after averaging over $N_s$ realizations. Dashed lines correspond to a linear fit of the points using least squares on a log-log scale. (a) ID, $N_s=2\times {10}^4$; (b) RD, $N_s=2\times {10}^4$; (c) IB, $N_s=2\times {10}^4$; (d) RB, $N_s=5\times {10}^3$.

Figure 7

(a)–(d) Derivative of the logarithm of the order parameter as a function of the fraction of nodes removed. The gray curves correspond to a five-point numerical derivative and the colored curves to the derivatives computed using the regularization method described in [39]. Both methods were applied over averages using $2\times {10}^4$ simulations (ID, RD, and IB) and $5\times {10}^3$ simulations (RB). (e)–(h) Scaling of the peaks of the curves in the left. Dashed lines correspond to linear fits using least squares. The values obtained for the critical exponent of the correlation length $\overline{\nu }$ are summarized in Table 1.

Figure 8

Cluster size distribution $p\left(s\right)=n\left(s\right)/{\sum }_s^{\prime }n\left(s\right)$ for each attack strategy. Dotted dashed red curves correspond to the subcritical region $f<f_c$, dashed gray curves to the supercritical region $f>f_c$, and solid blue lines to the critical value $f=f_c$. For ID, RD, and IB, the plots are consistent with Eq. (4), showing a power-law distribution at the critical point (with a gentle decay at the tail due to finite-size effects) and an exponential decay for other values of $f$. RB deviates from the standard behavior, showing a hump for middle values of $s$. The dotted black curves are power laws fitted from the binned data, and their slopes are summarized in Table 1. The distributions were computed averaging ${10}^3$ networks. (a) ID, $N=64000$; (b) RD, $N=64000$; (c) IB, $N=64000$; (d) RB, $N=16000$.