Network robustness and fragility: Percolation on random graphs

Network robustness and fragility: Percolation on random graphs

19 Oct 2000 | Duncan S. Callaway1, M. E. J. Newman2,3, Steven H. Strogatz1,2, and Duncan J. Watts4
This paper explores the robustness and fragility of networks, particularly focusing on percolation models on random graphs. The authors study the resilience of networks to random or targeted node deletions, which can simulate failures such as router crashes or power line outages. Unlike previous models that often use Poisson degree distributions, this study generalizes to graphs with arbitrary degree distributions, including power-law distributions commonly found in real-world networks. The paper introduces a generating function formalism to solve exact solutions for various percolation models, including site percolation, bond percolation, and models where occupation probabilities depend on vertex degree. These solutions provide insights into network robustness, such as mean cluster size, percolation threshold, and the size of the giant component. Key findings include: - Networks with power-law degree distributions are highly robust to random node deletions, but relatively fragile to the removal of highly connected nodes. - The percolation threshold, which marks the point at which a giant component forms, can be calculated explicitly. - The behavior of networks under selective node removal, such as removing high-degree nodes, is analyzed, showing that while the network may appear fragile when viewed in terms of the fraction of nodes removed, it can remain robust when viewed in terms of the highest remaining degree. The study uses both theoretical analysis and simulations to validate the results, demonstrating good agreement between the theoretical predictions and empirical observations. The findings have implications for understanding the resilience of communication and distribution networks, as well as the spread of diseases through communities.This paper explores the robustness and fragility of networks, particularly focusing on percolation models on random graphs. The authors study the resilience of networks to random or targeted node deletions, which can simulate failures such as router crashes or power line outages. Unlike previous models that often use Poisson degree distributions, this study generalizes to graphs with arbitrary degree distributions, including power-law distributions commonly found in real-world networks. The paper introduces a generating function formalism to solve exact solutions for various percolation models, including site percolation, bond percolation, and models where occupation probabilities depend on vertex degree. These solutions provide insights into network robustness, such as mean cluster size, percolation threshold, and the size of the giant component. Key findings include: - Networks with power-law degree distributions are highly robust to random node deletions, but relatively fragile to the removal of highly connected nodes. - The percolation threshold, which marks the point at which a giant component forms, can be calculated explicitly. - The behavior of networks under selective node removal, such as removing high-degree nodes, is analyzed, showing that while the network may appear fragile when viewed in terms of the fraction of nodes removed, it can remain robust when viewed in terms of the highest remaining degree. The study uses both theoretical analysis and simulations to validate the results, demonstrating good agreement between the theoretical predictions and empirical observations. The findings have implications for understanding the resilience of communication and distribution networks, as well as the spread of diseases through communities.
Reach us at info@study.space