Onion structure and network robustness

In a recent work [Proc. Natl. Acad. Sci. USA 108, 3838 (2011)], Schneider et al. proposed a new measure for network robustness and investigated optimal networks with respect to this quantity. For networks with a power-law degree distribution, the optimized networks have an onion structure—high-degree vertices forming a core with radially decreasing degrees and an over-representation of edges within the same radial layer. In this paper we relate the onion structure to graphs with good expander properties (another characterization of robust network) and argue that networks of skewed degree distributions with large spectral gaps (and thus good expander properties) are typically onion structured. Furthermore, we propose a generative algorithm producing synthetic scale-free networks with onion structure, circumventing the optimization procedure of Schneider et al. We validate the robustness of our generated networks against malicious attacks and random removals.

Figure 1

Visualization of a typical onion network generated by our algorithm with $N=100$ vertices, $\langle k\rangle =5.8$, and a degree distribution $P\left(k\right)\sim k^{-2.5}$. The lowest and highest degrees in this network are, respectively, 3 and 26. The sizes of the vertices are proportional to their degree, vertices with the same layer indices are marked by the same color, and edges between nodes with equal degree are highlighted.

Figure 2

The fraction of vertices belonging to the largest connected cluster $s\left(q\right)$ versus the fraction $q$ of removed vertices. Vertices are removed according to their current degree during the removal to simulate an attack scenario where an adversary hits the fraction $q$ of the system's weakest points. We compare three types of model networks: the configuration model (solid line), the robustness-optimized procedure (dashed line), and our algorithm (dashed-dot line). All networks have the same parameters as shown in Fig. 1.

Figure 3

Scatter plot of the robustness $R$ as a function of (a) the assortativity $r$ and (b) the ratio of the largest eigenvalue of the adjacency matrix to the second largest one of the networks ${\lambda }_1/{\lambda }_2$. The plus and cross symbols are the results for 50 networks generated by the configuration model and our algorithm, respectively. 200 independent degree attacks are carried out on each of them. The corresponding results for an optimized network, generated by the optimization procedure, are also shown for comparison (the solid triangle). All networks have the same parameters as shown in Fig. 1.

Figure 4

The fraction $s\left(q\right)$ of vertices belonging to the largest connected cluster versus the fraction $q$ of removed vertices using the random attack strategy for scale-free networks generated by the configuration model (solid line), and our algorithm (dashed line). The two networks have the same system size $N=2000$, average degree $\langle k\rangle =4.75$, and degree sequences. The lowest and highest degrees in the networks are, respectively, 2 and 73. Each curve is obtained by averaging over 2000 independent trials.

Figure 5

Robustness $R$ (diamonds) and assortativity coefficient $r$ (circles) as a function of $a$ for scale-free networks generated by our algorithm [23]. The error bars indicate the standard errors of the robustness and assortativity calculated for 50 scale-free networks. All networks have the same parameters as shown in Fig. 4.