Statistical analysis of articulation points in configuration model networks

Abstract

An articulation point (AP) in a network is a node whose deletion would split the network component on which it resides into two or more components. APs are vulnerable spots that play an important role in network collapse processes, which may result from node failures, attacks or epidemics. Therefore, the abundance and properties of APs affect the resilience of the network to these collapse scenarios. We present analytical results for the statistical properties of APs in configuration model networks. In order to quantify their abundance, we calculate the probability $P(i\in \mathrm{AP})$, that a random node, i, in a configuration model network with P(K=k), is an AP. We also obtain the conditional probability $P(i\in \mathrm{AP}|k)$ that a random node of degree k is an AP, and find that high degree nodes are more likely to be APs than low degree nodes. Using Bayes' theorem, we obtain the conditional degree distribution, $P(K=k|\mathrm{AP})$, over the set of APs and compare it to P(K=k). We propose a new centrality measure based on APs: each node can be characterized by its articulation rank, r, which is the number of components that would be added to the network upon deletion of that node. For nodes which are not APs the articulation rank is $r=0$, while for APs $r\ge 1$. We obtain a closed form expression for the distribution of articulation ranks, P(R=r). Configuration model networks often exhibit a coexistence between a giant component and finite components. To examine the distinct properties of APs on the giant and on the finite components, we calculate the probabilities presented above separately for the giant and the finite components. We apply these results to ensembles of configuration model networks with a Poisson, exponential and power-law degree distributions. The implications of these results are discussed in the context of common attack scenarios and network dismantling processes.

arXiv comment53 pages, 16 figures. arXiv admin note: text overlap with arXiv:1804.03336

References in corpus (24)

• Error and attack tolerance of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• Efficient Immunization Strategies for Computer Networks and Populations
• Mitigation of Malicious Attacks on Networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Network dismantling
• Fast and simple decycling and dismantling of networks
• Articulation Points in Complex Networks
• Metric structure of random networks
• Distance distribution in random graphs and application to networks exploration
• On the number of circuits in random graphs
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• Circuits in random graphs: from local trees to global loops
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• An algorithm for counting circuits: application to real-world and random graphs
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• The distribution of shortest path lengths in a class of node duplication network models
• Distribution of shortest cycle lengths in random networks
• Ranking by Loops: a new approach to categorization
• Finding long cycles in graphs

Cited by in corpus (12)

• Percolation on complex networks: Theory and application
• Structure of percolating clusters in random clustered networks
• Statistical analysis of edges and bredges in configuration model networks
• Topological conditions drive stability in meta-ecosystems
• Characterizing cycle structure in complex networks
• The Fate of Articulation Points and Bredges in Percolation
• Generating random networks that consist of a single connected component with a given degree distribution
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments
• 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