Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments

Abstract

We investigate the heterogeneity of outcomes of repeated instances of percolation experiments in complex networks using a message passing approach to evaluate heterogeneous, node dependent probabilities of belonging to the giant or percolating cluster, i.e. the set of mutually connected nodes whose size scales linearly with the size of the system. We evaluate these both for large finite single instances, and for synthetic networks in the configuration model class in the thermodynamic limit. For the latter, we consider both Erdos-Renyi and scale free networks as examples of networks with narrow and broad degree distributions respectively. For real-world networks we use an undirected version of a Gnutella peer-to-peer file-sharing network with $N=62,568$ nodes as an example. We derive the theory for multiple instances of both uncorrelated and correlated percolation processes. For the uncorrelated case, we also obtain a closed form approximation for the large mean degree limit of Erdos-Renyi networks.

14 pages, 6 multipart figures

References in corpus (10)

• Efficient Immunization Strategies for Computer Networks and Populations
• A message passing approach for general epidemic models
• Percolation on sparse networks
• Predicting the speed of epidemics spreading on networks
• Stability of a Giant Connected Component in a Complex Network
• Exotic Critical Behavior of Weak Multiplex Percolation
• Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
• Assessing node risk and vulnerability in epidemics on networks
• Phase Transitions in Operational Risk
• Diluted antiferromagnet in a ferromagnetic enviroment

Cited by in corpus (1)

• The Fate of Articulation Points and Bredges in Percolation