Robustness of onionlike correlated networks against targeted attacks

Recently, it was found by Schneider et al. [Proc. Natl. Acad. Sci. USA 108, 3838 (2011)], using simulations, that scale-free networks with “onion structure” are very robust against targeted high degree attacks. The onion structure is a network where nodes with almost the same degree are connected. Motivated by this work, we propose and analyze, based on analytical considerations, an onionlike candidate for a nearly optimal structure against simultaneous random and targeted high degree node attacks. The nearly optimal structure can be viewed as a set of hierarchically interconnected random regular graphs,the degrees and populations of whose nodes are specified by the degree distribution. This network structure exhibits an extremely assortative degree-degree correlation and has a close relationship to the “onion structure.” After deriving a set of exact expressions that enable us to calculate the critical percolation threshold and the giant component of a correlated network for an arbitrary type of node removal, we apply the theory to the cases of random scale-free networks that are highly vulnerable against targeted high degree node removal. Our results show that this vulnerability can be significantly reduced by implementing this onionlike type of degree-degree correlation without much undermining the almost complete robustness against random node removal. We also investigate in detail the robustness enhancement due to assortative degree-degree correlation by introducing a joint degree-degree probability matrix that interpolates between an uncorrelated network structure and the onionlike structure proposed here by tuning a single control parameter. The optimal values of the control parameter that maximize the robustness against simultaneous random and targeted attacks are also determined. Our analytical calculations are supported by numerical simulations.

Figure 1

An example of a set of separated random regular graphs from $k=2$ to $k=5$. The total node number $N=524$ and the node number for each random regular graph is determined by the power-law degree distribution, $P\left(k\right)\propto k^{-\lambda }$ with $\lambda =2.6$. Notice that the graph for $k=2$ is composed of separated rings, which can be fragmented by removing a tiny amount (zero fraction) of nodes. This means that the giant component of the random regular graph for $k=2$ is always at the edge of criticality, as indeed predicted by Eq. (5).

Figure 2

Plots of the values of the “virtual” giant component $S$ as a function of the remaining fraction of nodes $p$, obtained theoretically for extremely assortative scale-free networks specified by Eq. (4) for various values of the maximum degree $K$. The degree distribution is fixed to the power-law $k^{-\lambda }$ with an exponent $\lambda =2.6$: (a) The giant component $S$ for $m=2$ and (b) $S$ for $m=3$. The values of $S$ for networks with the onion structure obtained by both theory and numerical simulations as well as the giant component fraction of the corresponding uncorrelated random scale-free network for $K=5$ are shown. In (a), the values of $S$ for completely separated RR graphs (with no “bridges”) obtained by simulation are also added for $K=10$ for comparison. Notice that the difference between the results for the onion structure and those of the separated RR graphs are small for $m=2$ and $K=10$. For $m=3$, this difference is indistinguishable.

Figure 3

The fraction of the largest connected component of scale-free networks with the exponent $\lambda =2.6$, minimum degree $m=2$, and maximum degrees $K=10,100$ as a function of the parameter $\sigma$, that controls the assortativity of the degree-degree correlation. Above $\sigma \approx 0.35$, the separated $k=2$ components become connected to the larger degree components and the largest connected component spans the entire network.

Figure 4

Plots of the critical node threshold against a targeted high-degree node attack as a function of the parameter $\sigma$ that controls the assortativity of the degree-degree correlation [see Eq. (14)] for several scale-free networks. (a) Scale-free networks with the exponent $\lambda =2.6$ and minimum degree $m=2$. The (blue) solid curve is for a network with maximum degree $K=10$ and the (red) dotted curve is for $K=100$. (b) Scale-free networks with $m=2$ and $K=100$. The (blue) solid curve is for $\lambda =2.2$ and the (red) dotted curve is for $\lambda =2.6$. (c) Scale-free networks with $\lambda =2.6$ and $m=3$. The (blue) solid curve is for $K=10$ and the (red) dotted curve is for the network with $K=100$. (d) Scale-free networks with $m=3$ and $K=100$. The (blue) solid curve is for $\lambda =2.2$ and the (red) dotted curve is for $\lambda =2.6$. For small values of $\sigma$, where the network structure approaches to be composed of weakly interconnected RR graphs, all critical node thresholds approach to $P\left(2\right)+P\left(3\right)/2$ for $m=2$ and to $P\left(3\right)$ for $m=3$. For all these cases, the giant component spans the entire network at the beginning of the node removal. Note that a smaller value of $p_c$ generally means a more robust network structure.

Figure 5

Plots of the giant component fraction $S$ as a function of the fraction of the remaining nodes $p$ for several values of $\sigma$. The plots for the scale-free networks with $\lambda =2.6$, $m=2$, and $K=10$ are (a) for targeted attack and (b) for random attack. The plots for the scale-free networks with $\lambda =2.6$, $m=3$, and $K=10$ are (c) for targeted attack and (d) for random attack. For comparison, we also plot in (a) and (c) the curves of the giant component for uncorrelated networks and the curves for random regular (RR) networks where all degrees are the same as the average degree $\langle k\rangle$ of the corresponding scale-free networks. The lines $S=p$ in (a) and (c) are guides for eyes and represent an optimal network.

Figure 6

Schematic profiles of the giant component as a function of the remaining node fraction, $p$, for the two typical cases. The case (a) has a larger value of the critical node threshold $p_c$ than (b), but the giant component collapse for (a) occurs much slower than for the case (b). From the viewpoint of the global connectivity, the value of the area below $S\left(p\right)$ represented by $R$ is a better measure of the robustness than the critical threshold $p_c$.

Figure 7

The values of the total robustness measure $R_{\text{tot}}$ as a function of $\sigma$ for two scale-free networks. Plot (a) is for a scale-free network with $\lambda =2.6$, $m=2$, and $K=10$ and plot (b) is for a scale-free network with $\lambda =2.6$, $m=3$, and $K=10$. The numerically obtained optimal values of $\sigma$ that maximize $R_{\text{tot}}$ are $\sigma =1.33$ for $m=2$ and $\sigma =0.646$ for $m=3$.

Figure 8

Plots of the optimal giant component $S$ as a function of $p$ for scale-free networks with $\lambda =2.6$ and $K=10$. For plots (a) targeted attack and (b) random attack, $m=2$ and the optimal value is $\sigma =1.33$. For plots (c) targeted attack and (d) random attack, $m=3$ and the optimal value is $\sigma =0.646$. In all plots, the theoretical values for the giant component are represented by full curves. The critical node thresholds for a targeted attack are $P\left(2\right)+P\left(3\right)/2$ for $m=2$ and $P\left(3\right)/2$ for $m=3$. We also plot, for comparison, the curves for the corresponding uncorrelated scale-free network with the same values of parameters (dashed curves) and for the RR network with the same degree as the average degree of the corresponding scale-free network (dotted curves). The (blue) circles are obtained from simulation of a single realization for each of the optimal networks generated from the joint degree-degree matrix, Eq. (14), for the optimal value of $\sigma =1.33$ with $N=6993$ and $m=2$ and for the optimal value of $\sigma =0.646$ with $N=2795$ and $m=3$.