Optimization of Robustness of Complex Networks

Abstract

Networks with a given degree distribution may be very resilient to one type of failure or attack but not to another. The goal of this work is to determine network design guidelines which maximize the robustness of networks to both random failure and intentional attack while keeping the cost of the network (which we take to be the average number of links per node) constant. We find optimal parameters for: (i) scale free networks having degree distributions with a single power-law regime, (ii) networks having degree distributions with two power-law regimes, and (iii) networks described by degree distributions containing two peaks. Of these various kinds of distributions we find that the optimal network design is one in which all but one of the nodes have the same degree, $k_1$ (close to the average number of links per node), and one node is of very large degree, $k_2\sim N^{2/3}$, where $N$ is the number of nodes in the network.

Accepted for publication in European Physical Journal B

References in corpus (11)

• Emergence of scaling in random networks
• Error and attack tolerance of complex networks
• The large-scale organization of metabolic networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Breakdown of the Internet under intentional attack
• Generation of uncorrelated random scale-free networks
• Optimal Paths in Disordered Complex Networks
• Two-Peak and Three-Peak Optimal Complex Networks
• Uncorrelated Random Networks

Cited by in corpus (40)

• Robustness and resilience of complex networks
• The topological relationship between the large-scale attributes and local interaction patterns of complex networks
• Entropy Optimization of Scale-Free Networks Robustness to Random Failures
• Optimization of Network Robustness to Waves of Targeted and Random Attack
• Graph Vulnerability and Robustness: A Survey
• Robustness of onion-like correlated networks against targeted attacks
• Multiple, weak hits confuse complex systems: A transcriptional regulatory network as an example
• Smart Rewiring for Network Robustness
• Evolution of robust network topologies: Emergence of central backbones
• Optimization of robustness of scale-free network to random and targeted attacks
• Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations
• Optimization of Network Robustness to Random Breakdowns
• Optimization of network structure to random failures
• Percolation theory applied to measures of fragmentation in social networks
• Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
• Enhancing the robustness of scale-free networks
• Building Damage-Resilient Dominating Sets in Complex Networks against Random and Targeted Attacks
• Optimization of scale-free network for random failures
• Complex Network Properties of Chinese Natural Science Basic Research
• Robustness of football passing networks against continuous node and link removals
• Discontinuous transition to loop formation in optimal supply networks
• Growing distributed networks with arbitrary degree distributions
• Multistage Random Growing Small-World Networks with Power-law degree Distribution
• Network resilience against intelligent attacks constrained by degree dependent node removal cost
• A note on measurement of network vulnerability under random and intentional attacks
• Scale-free networks resistant to intentional attacks
• Characterizing the Robustness of Complex Networks
• Fragmentation properties of two-dimensional Proximity Graphs considering random failures and targeted attacks
• Enhancing the robustness of a multiplex network leads to multiple discontinuous percolation transitions
• The Robustness of Graph k-shell Structure under Adversarial Attacks
• Robustness analysis of bimodal networks in the whole range of degree correlation
• Preservation of network Degree Distributions from non-uniform failures
• Bounding robustness in complex networks under topological changes through majorization techniques
• Design of endurable networks in the presence of aging
• Network Extreme Eigenvalue - from Multimodal to Scale-free Network
• Null models for multi-optimized large-scale network structures
• Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
• Resilience of Social Networks Under Different Attack Strategies
• A new metric for robustness with respect to virus spread
• Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks