The Fate of Articulation Points and Bredges in Percolation

Abstract

We investigate the statistics of articulation points and bredges (bridge-edges) in complex networks in which bonds are randomly removed in a percolation process. Articulation points are nodes in a network which, if removed, would split the network component on which they are located into two or more separate components, while bredges are edges whose removal would split the network component on which they are located into two separate components. Both articulation points and bredges play an important role in processes of network dismantling and it is therefore useful to know the evolution of the probability of nodes or edges to be articulation points and bredges, respectively, when a fraction of edges is randomly removed from the network in a percolation process. Due to the heterogeneity of the network, the probability of a node to be an articulation point, or the probability of an edge to be a bredge will not be homogeneous across the network. We therefore analyze full distributions of articulation point probabilities as well as bredge probabilities, using a message-passing or cavity approach to the problem, as well as a deconvolution of these distributions according to degrees of the node or the degrees of both adjacent nodes in the case of bredges. Our methods allow us to obtain these distributions both for large single instances of networks as well as for ensembles of networks in the configuration model class in the thermodynamic limit of infinite system size. We also derive closed form expressions for the large mean degree limit of Erdős-Rényi networks.

15 pages, 10 multipart figures

References in corpus (8)

• Mitigation of Malicious Attacks on Networks
• Percolation on sparse networks
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Articulation Points in Complex Networks
• Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
• Spectra of Random Stochastic Matrices and Relaxation in Complex Systems
• Statistical analysis of edges and bredges in configuration model networks
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments