Optimization of network robustness to random breakdowns

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 〈k〉. We find that the network design that maximizes fc, the fraction of nodes that are randomly removed before global connectivity is lost, consists of q=[(〈k〉-1)/〈k〉]N high degree nodes (“hubs”) of degree 〈k〉N and N-q nodes of degree 1. Also, we show that 1-fc 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.