Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations

Abstract

We developed a scheme for evaluating the size of the largest connected subnetwork (giant component) in random networks and the percolation threshold when sites (nodes) and/or bonds (edges) are removed from the networks based on the cavity method of statistical mechanics of disordered systems. An advantage of our scheme is the capability of handling targeted attacks on sites/bonds in the presence of degree correlations beyond naive analyses on random failures (crashes) in networks of no degree correlations. We apply our scheme particularly to random networks of bimodal degree distribution (two-peak networks), which have been proposed in earlier studies as robust networks against random failures of site and/or targeted attacks on sites, and show that the correlations among degrees affect a network's robustness against targeted attacks on sites or bonds non-trivially depending on details of network configurations.

11 pages, 6 figures

References in corpus (26)

• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Specificity and stability in topology of protein networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• Breakdown of the Internet under intentional attack
• The Bethe lattice spin glass revisited
• Mean-field solution of the small-world network model
• Cut-offs and finite size effects in scale-free networks
• Robustness of the European power grids under intentional attack
• Resilience to damage of graphs with degree correlations
• Second look at the spread of epidemics on networks
• Construction and properties of assortative random networks
• Optimization of Robustness of Complex Networks
• Optimization of Network Robustness to Waves of Targeted and Random Attack
• Percolation on correlated networks
• How to make a fragile network robust and vice versa
• Two-Peak and Three-Peak Optimal Complex Networks
• Error and Attack Tolerance of Layered Complex Networks
• The high temperature region of the Viana-Bray diluted spin glass model
• Organization of modular networks
• Computational complexity arising from degree correlations in networks
• Trading interactions for topology in scale-free networks
• Spin models on random graphs with controlled topologies beyond degree constraints
• Generating functional analysis of complex formation and dissociation in large protein interaction networks

Cited by in corpus (19)

• Robustness and resilience of complex networks
• Robustness of onion-like correlated networks against targeted attacks
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations
• First eigenvalue/eigenvector in sparse random symmetric matrices: influences of degree fluctuation
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Robustness of cooperation on scale-free networks under continuous topological change
• Observability transitions in correlated networks
• Robustness analysis of bimodal networks in the whole range of degree correlation
• Robustness of correlated networks against propagating attacks
• Belief propagation on networks with cliques and chordless cycles
• The Fate of Articulation Points and Bredges in Percolation
• Synergistic epidemic spreading in correlated networks
• Robustness of Random Networks with Selective Reinforcement against Attacks
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments
• Structural instability of large-scale functional networks
• Vaccination with partial transmission and social distancing on contact networks
• Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
• Nonreciprocal random networks and their percolation properties