Optimization of network robustness to waves of targeted and random attacks

We study the robustness of complex networks to multiple waves of simultaneous (i) targeted attacks in which the highest degree nodes are removed and (ii) random attacks (or failures) in which fractions $p_t$ and $p_r$, respectively, of the nodes are removed until the network collapses. We find that the network design which optimizes network robustness has a bimodal degree distribution, with a fraction $r$ of the nodes having degree $k_2=(⟨k⟩-1+r)∕r$ and the remainder of the nodes having degree $k_1=1$, where $⟨k⟩$ is the average degree of all the nodes. We find that the optimal value of $r$ is of the order of $p_t∕p_r$ for $p_t∕p_r⪡1$.

Figure 1

(a) The threshold $f_c$ of three bimodal networks with $⟨k⟩=3$, with (i) $r=2\times {10}^{-3}$ and $k_2=200$, (ii) $r=5\times {10}^{-3}$ and $k_2=90$, and (iii) $r={10}^{-2}$ and $k_2=50$. The results are plotted as a function of the ratio $p_t∕p_r$ for three fixed values of $p_r$. These plots show that the values of the threshold are dependent only on the ratio $p_t∕p_r$ and independent of the value of $p_r$ itself. (b) Scaled plot of the data in (a). The data show that the plots collapse in the region where $r∕(p_t∕p_r)\lesssim 1$.

Figure 2

The threshold $f_c$ versus $k_2$ for a bimodal network with $⟨k⟩=3$ and $r={10}^{-2}$ for three values of $p_t∕p_r$. The value of $p_r$ is fixed at 0.02. For each value of $p_t∕p_r$, the thresholds take their maximum values at the maximum $k_2$ (obtained when $k_1=1$).

Figure 3

The threshold $f_c$ versus the scaled parameter $r∕(p_t∕p_r)$ for a bimodal network with $⟨k⟩=3$ and $k_2$ maximum (i.e., $k_1=1$).

Figure 4

The threshold $f_c$ versus $p_t∕p_r$. The topmost (thickest) curve is for a bimodal network with $⟨k⟩=3$ with $k_1=1$ and with $r$ optimized by Eq. (7) for each value of $p_t∕p_r$. The values of the threshold for the same bimodal network with $k_1=1$ when we fix $r$ independent of $p_t∕p_r$ are plotted in thin curves. The values of $r$ are $r=0.001$, 0.002, 0.005, 0.01, 0.03, 0.05, 0.07, 0.09, 0.11, 0.13, and 0.15, from left to right. The curve marked with crossed circles (⊕) is a plot of the threshold values for a scale-free network with $⟨k⟩=3$, $N={10}^4$, and with exponent values in the range 2.3 to 2.5 chosen for each $p_t∕p_r$ to optimize the threshold. Note that the thresholds for bimodal networks with $0.03\lesssim r\lesssim 0.09$ are always more robust than the optimized scale-free network.

Figure 5

Realization of bimodal network with $N=100$ nodes, $⟨k⟩=2.1$, and $r=0.1$, so there are $rN=10$ “hub” nodes of degree 12, as found from Eq. (1).