Statistical analysis of edges and bredges in configuration model networks

Abstract

A bredge (bridge-edge) is an edge whose deletion would split the network component on which it resides into two components. Bredges are vulnerable links that play an important role in network collapse processes, which may result from node or link failures, attacks or epidemics. Therefore, the abundance and properties of bredges affect the resilience of the network. We present analytical results for the statistical properties of bredges in configuration model networks. Using a generating function approach based on the cavity method, we calculate the probability $\hat{P}(e\in \mathrm{B})$ that a random edge e in a configuration model network with degree distribution P(k) is a bredge (B). We also calculate the joint degree distribution $\hat{P}(k,k^{\prime }|\mathrm{B})$ of the end-nodes of a random bredge. We examine the distinct properties of bredges on the giant component (GC) and on the finite tree components (FC) of the network. On the finite components all the edges are bredges and there are no degree-degree correlations. We calculate the probability $\hat{P}(e\in \mathrm{B}|\mathrm{GC})$ that a random edge on the giant component is a bredge. We also calculate the joint degree distribution $\hat{P}(k,k^{\prime }|\mathrm{B},\mathrm{GC})$ of the end-nodes of bredges and the joint degree distribution $\hat{P}(k,k^{\prime }|\mathrm{NB},\mathrm{GC})$ of the end-nodes of non-bredge (NB) edges on the giant component. Surprisingly, it is found that the degrees k and k' of the end-nodes of bredges are correlated, while the degrees of the end-nodes of NB edges are uncorrelated. We thus conclude that all the degree-degree correlations on the giant component are concentrated on the bredges. We calculate the covariance of end-nodes of bredges and show it is negative, namely bredges tend to connect high degree nodes to low degree nodes. The implications of the results are discussed in the context of common attack scenarios and dismantling processes.

arXiv comment27 pages, 14 figures. arXiv admin note: text overlap with arXiv:1806.04591

References in corpus (41)

• Error and attack tolerance of complex networks
• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Mixing patterns in networks
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• Why social networks are different from other types of networks
• Mitigation of Malicious Attacks on Networks
• k-core organization of complex networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Betweenness centrality correlation in social networks
• Network dismantling
• Generalized Network Dismantling
• Fast and simple decycling and dismantling of networks
• The entropic origin of disassortativity in complex networks
• Structure of shells in complex networks
• Articulation Points in Complex Networks
• Component sizes in networks with arbitrary degree distributions
• Metric structure of random networks
• Bicomponents and the robustness of networks to failure
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Distance distribution in random graphs and application to networks exploration
• Fractal Boundaries of Complex Networks
• The cavity method at zero temperature
• Distribution of diameters for Erdös-Rényi random graphs
• Disassortativity of percolating clusters in random networks
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• Bridges in Complex Networks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• The distribution of shortest path lengths in a class of node duplication network models
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• General expression for the component size distribution in infinite configuration networks
• Percolation on random networks with arbitrary k-core structure
• Distribution of shortest cycle lengths in random networks
• Statistical analysis of articulation points in configuration model networks
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication
• Generating random networks that consist of a single connected component with a given degree distribution
• Distance Distribution in Extreme Modular Networks

Cited by in corpus (6)

• The Fate of Articulation Points and Bredges in Percolation
• Influence of cumulative damage on synchronization of Kuramoto oscillators on networks
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Emergent networks in fractional percolation
• Larger holes as narrower degree distributions in complex networks
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks