The Fate of Articulation Points and Bredges in Percolation
arXiv:2101.09977 · doi:10.1103/PhysRevE.103.042302
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.
arXiv comment15 pages, 10 multipart figures
References in corpus (21)
- Error and attack tolerance of complex networks
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Breakdown of the Internet under intentional attack
- Mitigation of Malicious Attacks on Networks
- The Bethe lattice spin glass revisited
- Percolation on sparse networks
- Network dismantling
- Fast and simple decycling and dismantling of networks
- Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
- Articulation Points in Complex Networks
- Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
- Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
- Bridges in Complex Networks
- Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
- Heterogeneous micro-structure of percolation in sparse networks
- Spectra of Random Stochastic Matrices and Relaxation in Complex Systems
- Statistical analysis of articulation points in configuration model networks
- Disentangling Giant Component and Finite Cluster Contributions in Sparse Matrix Spectra
- Statistical analysis of edges and bredges in configuration model networks
- Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments