Onion structure and network robustness

Abstract

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.

6 pages, 5 figures

References in corpus (18)

• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Assortative mixing in networks
• Catastrophic cascade of failures in interdependent networks
• Statistical physics of social dynamics
• Random graphs with arbitrary degree distributions and their applications
• Mixing patterns in networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• Attack vulnerability of complex networks
• Breakdown of the Internet under intentional attack
• Mitigation of Malicious Attacks on Networks
• Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition
• The critical effect of dependency groups on the function of networks
• Interdependent networks with correlated degrees of mutually dependent nodes
• Efficient local strategies for vaccination and network attack
• Scale-free networks with a large- to hypersmall-world transition

Cited by in corpus (26)

• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Structure and dynamics of core-periphery networks
• Enhancing network robustness for malicious attacks
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• A Learning Convolutional Neural Network Approach for Network Robustness Prediction
• Knowledge-Based Prediction of Network Controllability Robustness
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• Towards Optimal Robustness of Network Controllability: An Empirical Necessary Condition
• A loop enhancement strategy for network robustness
• Generating Robust and Efficient Networks Under Targeted Attacks
• A simple model clarifies the complicated relationships of complex networks
• Effect of degree correlations above the first shell on the percolation transition
• A new design principle of robust onion-like networks self-organized in growth
• A growth model for water distribution networks with loops
• Critical Cooperation Range to Improve Spatial Network Robustness
• A quantitative method for determining the robustness of complex networks
• Emergence of Robust and Efficient Networks in a Family of Attachment Models
• Growing Self-organized Design of Efficient and Robust Complex Networks
• Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
• Degree heterogeneity in spatial networks with total cost constraint
• Asymptotic behavior of the node degrees in the ensemble average of adjacency matrix
• More Tolerant Reconstructed Networks by Self-Healing against Attacks in Saving Resource
• Effective Self-Healing Networks against Attacks or Disasters in Resource Allocation Control
• Global decomposition of networks into multiple cores formed by local hubs
• Emergence of an Onion-like Network in Surface Growth and Its Strong Robustness
• Mandala Networks: ultra-robust, ultra-small-world and highly sparse graphs