Bonneau Haggai, Tishby Ido, Biham Ofer, Katzav Eytan, Kühn Reimer
Racah Institute of Physics, The Hebrew University, Jerusalem 9190401, Israel.
Mathematics Department, King's College London, Strand, London WC2R 2LS, United Kingdom.
Phys Rev E. 2021 Apr;103(4-1):042302. doi: 10.1103/PhysRevE.103.042302.
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 Erdős-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.
我们研究了复杂网络中关节点和桥（桥边）的统计特性，其中键在渗流过程中被随机移除。由于复杂网络的异质结构，节点成为关节点的概率或边成为桥的概率在整个网络中并非均匀分布。因此，我们使用消息传递或腔方法来分析关节点概率和桥概率的完整分布。我们的方法使我们能够通过单一统一方法，在热力学极限下，针对大型网络的单个实例以及配置模型类中的网络集合获得这些分布。我们还根据节点的度数或桥的情况下相邻两个节点的度数来评估这些分布的去卷积。我们得到了厄多斯 - 雷尼网络大平均度数极限的封闭形式表达式。此外，我们揭示并能够合理解释在随机键移除时关节点和桥概率演变中的大量结构。我们发现，即使平均关节点和桥概率没有差异，真实网络及其随机化对应网络中关节点和桥概率的完整分布也可能存在显著差异。我们认为我们的结果可用于各种应用，包括网络拆解方法、疫苗接种以及预防过程网络中流行病传播或停电的孤岛策略。
