Optimization of Network Robustness to Random Breakdowns

Abstract

We study network configurations that provide optimal robustness to random breakdowns for networks with a given number of nodes $N$ and a given cost--which we take as the average number of connections per node $\kav$. We find that the network design that maximizes $f_c$, the fraction of nodes that are randomly removed before global connectivity is lost, consists of $q=[(\kav-1)/\sqrt\kav]\sqrt N$ high degree nodes (``hubs'') of degree $\sqrt{\kav N}$ and $N-q$ nodes of degree 1. Also, we show that $1-f_c$ approaches 0 as $1/\sqrt{N}$--faster than any other network configuration including scale-free networks. We offer a simple heuristic argument to explain our results.

References in corpus (12)

• Error and attack tolerance of complex networks
• Assortative mixing in networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• Generation of uncorrelated random scale-free networks
• Cut-offs and finite size effects in scale-free networks
• Optimization of Robustness of Complex Networks
• Optimization of Network Robustness to Waves of Targeted and Random Attack
• Two-Peak and Three-Peak Optimal Complex Networks
• Uncorrelated Random Networks
• Resilience of Complex Networks to Random Breakdown

Cited by in corpus (5)

• Impact of the topology of global macroeconomic network on the spreading of economic crises
• Robustness of onion-like correlated networks against targeted attacks
• A limited resource model of fault-tolerant capability against cascading failure of complex network
• Characterizing the Robustness of Complex Networks
• Robustness analysis of bimodal networks in the whole range of degree correlation