King's College London

Research portal

Fate of articulation points and bredges in percolation

Research output: Contribution to journalArticlepeer-review

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

Original languageEnglish
Article number042302
JournalPhysical Review E
Volume103
Issue number4
Early online date2 Apr 2021
DOIs
Accepted/In press5 Mar 2021
E-pub ahead of print2 Apr 2021
PublishedApr 2021

Bibliographical note

Funding Information: This work was partly supported by the Israel Science Foundation Grant No. 1682/18. Publisher Copyright: © 2021 American Physical Society. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

Documents

King's Authors

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. 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.

View graph of relations

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