Robustness of onion-like correlated networks against targeted attacks

Abstract

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 onion-like candidate for a nearly optimal structure against simultaneous random and targeted high degree node attacks. The nearly optimal structure can be viewed as a hierarchically interconnected random regular graphs, the degrees and populations of which 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 onion-like 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 onion-like 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.

12 pages, 8 figures

References in corpus (7)

• Mitigation of Malicious Attacks on Networks
• Robustness of interdependent networks under targeted attack
• Percolation on correlated networks
• Correlations in weighted networks
• Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
• Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
• Critical behavior and correlations on scale-free small-world networks. Application to network design

Cited by in corpus (32)

• Structure and dynamics of core-periphery networks
• Percolation on complex networks: Theory and application
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• A Learning Convolutional Neural Network Approach for Network Robustness Prediction
• Cascading Failures in Interdependent Networks with Multiple Supply-Demand Links and Functionality Thresholds
• Knowledge-Based Prediction of Network Controllability Robustness
• Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations
• Dynamics on Modular Networks with Heterogeneous Correlations
• Towards Optimal Robustness of Network Controllability: An Empirical Necessary Condition
• A loop enhancement strategy for network robustness
• Robustness of cooperation on scale-free networks under continuous topological change
• Analysis and perturbation of degree correlation in complex networks
• A general formulation of long-range degree correlations in complex networks
• Hierarchical scale-free network is fragile against random failure
• Observability transitions in correlated networks
• A new design principle of robust onion-like networks self-organized in growth
• A growth model for water distribution networks with loops
• Fragmentation properties of two-dimensional Proximity Graphs considering random failures and targeted attacks
• Emergence of Robust and Efficient Networks in a Family of Attachment Models
• Robustness analysis of bimodal networks in the whole range of degree correlation
• Growing Self-organized Design of Efficient and Robust Complex Networks
• Robustness of correlated networks against propagating attacks
• Spatially self-organized resilient networks by a distributed cooperative mechanism
• Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
• Robustness of Random Networks with Selective Reinforcement against Attacks
• Asymptotic behavior of the node degrees in the ensemble average of adjacency matrix
• Quantitative modeling of degree-degree correlation in complex networks
• Structural instability of large-scale functional networks
• Effective Self-Healing Networks against Attacks or Disasters in Resource Allocation Control
• More Tolerant Reconstructed Networks by Self-Healing against Attacks in Saving Resource
• Mandala Networks: ultra-robust, ultra-small-world and highly sparse graphs
• Emergence of an Onion-like Network in Surface Growth and Its Strong Robustness