King's College London

Research portal

Statistical analysis of edges and bredges in configuration model networks

Research output: Contribution to journalArticlepeer-review

Haggai Bonneau, Ofer Biham, Reimer Kühn, Eytan Katzav

Original languageEnglish
Article number012314
Number of pages1
JournalPhysical review. E
Issue number1
Accepted/In press6 Jul 2020
Published23 Jul 2020


King's Authors


A bredge (bridge-edge) in a network is an edge whose deletion would split the network component on which it resides into two separate 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 to these collapse scenarios. 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 P(e∼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 P(k,k′|B) of the end-nodes i and i′ 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 P(e∼B|GC) that a random edge on the giant component is a bredge. We also calculate the joint degree distribution P(k,k′|B,GC) of the end-nodes of bredges and the joint degree distribution P(k,k′|NB,GC) of the end-nodes of nonbredge 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 nonbredge 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 Γ(B,GC) of the joint degree distribution of end-nodes of bredges and show it is negative, namely bredges tend to connect high degree nodes to low degree nodes. We apply this analysis to ensembles of configuration model networks with degree distributions that follow a Poisson distribution (Erdos-Rényi networks), an exponential distribution and a power-law distribution (scale-free networks). The implications of these results are discussed in the context of common attack scenarios and network dismantling processes.

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454