Fate of articulation points and bredges in percolation

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

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
33 Downloads (Pure)


We investigate the statistics of articulation points and bredges (bridge edges) in complex networks in which bonds are randomly removed in a percolation process. Because of the heterogeneous structure of a complex 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. Our methods allow us to obtain these distributions both for large single instances of networks and for ensembles of networks in the configuration model class in the thermodynamic limit, through a single unified approach. We also evaluate deconvolutions of these distributions according to degrees of the node or the degrees of both adjacent nodes in the case of bredges. We obtain closed form expressions for the large mean degree limit of Erdos-Rényi networks. Moreover, we reveal and are able to rationalize a significant amount of structure in the evolution of articulation point and bredge probabilities in response to random bond removal. We find that full distributions of articulation point and bredge probabilities in real networks and in their randomized counterparts may exhibit significant differences even where average articulation point and bredge probabilities do not. We argue that our results could be exploited in a variety of applications, including approaches to network dismantling or to vaccination and islanding strategies to prevent the spread of epidemics or of blackouts in process networks.

Original languageEnglish
Article number042302
JournalPhysical Review E
Issue number4
Early online date2 Apr 2021
Publication statusPublished - Apr 2021


Dive into the research topics of 'Fate of articulation points and bredges in percolation'. Together they form a unique fingerprint.

Cite this