Optimization of Network Robustness to Random Breakdowns

Gerald Paul; Sameet Sreenivasan; Shlomo Havlin; H. Eugene Stanley

doi:10.1016/j.physa.2006.02.044

paper

Optimization of Network Robustness to Random Breakdowns

arXiv:cond-mat/0507249 · doi:10.1016/j.physa.2006.02.044

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/ N$ --faster than any other network configuration including scale-free networks. We offer a simple heuristic argument to explain our results.