Network robustness and fragility: Percolation on random graphs

Recent work on the Internet, social networks, and the power grid has addres sed the resilience of these networks to either random or targeted deletion of network nodes or links. Such deletions include, for example, the failure of Internet routers or power transmission Lines. Percolation models on ran dom graphs provide a simple representation of this process but have typical ly been limited to graphs with Poisson degree distribution at their vertice s. Such graphs are quite unlike real-world networks, which often possess po wer-law or other highly skewed degree distributions. In this paper we study percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolation, bond pe rcolation, and models in which occupation probabilities depend on vertex de gree. We discuss the application of our theory to the understanding of netw ork resilience.