Articulation Points in Complex Networks

Abstract

An articulation point in a network is a node whose removal disconnects the network. Those nodes play key roles in ensuring connectivity of many real-world networks, from infrastructure networks to protein interaction networks and terrorist communication networks. Despite their fundamental importance, a general framework of studying articulation points in complex networks is lacking. Here we develop analytical tools to study key issues pertinent to articulation points, e.g. the expected number of them and the network vulnerability against their removal, in an arbitrary complex network. We find that a greedy articulation point removal process provides us a novel perspective on the organizational principles of complex networks. Moreover, this process is associated with two fundamentally different types of percolation transitions with a rich phase diagram. Our results shed light on the design of more resilient infrastructure networks and the effective destruction of terrorist communication networks.

51 pages, 16 figures

References in corpus (27)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Catastrophic cascade of failures in interdependent networks
• Random graphs with arbitrary degree distributions and their applications
• Identification of influential spreaders in complex networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• Influence maximization in complex networks through optimal percolation
• Universal Behavior of Load Distribution in Scale-free Networks
• k-core organization of complex networks
• Clique percolation in random networks
• Recent advances in percolation theory and its applications
• Cut-offs and finite size effects in scale-free networks
• Percolation on sparse networks
• "Explosive Percolation" Transition is Actually Continuous
• Explosive Percolation is Continuous, but with Unusual Finite Size Behavior
• Explosive Percolation: Novel critical and supercritical phenomena
• Avoiding a Spanning Cluster in Percolation Models
• Core percolation on complex networks
• Emergence of core-peripheries in networks
• On $k$-Core Percolation in Four Dimensions
• Disruptions in the U.S. Airport Network

Cited by in corpus (21)

• Percolation on complex networks: Theory and application
• Generalized Network Dismantling
• Underestimated cost of targeted attacks on complex networks
• Bridges in Complex Networks
• Identifying vital nodes by Achlioptas process
• Distribution of shortest cycle lengths in random networks
• Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
• Statistical analysis of articulation points in configuration model networks
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• The epidemiology of lateral movement: exposures and countermeasures with network contagion models
• Statistical analysis of edges and bredges in configuration model networks
• Two faces of greedy leaf removal procedure on graphs
• The Fate of Articulation Points and Bredges in Percolation
• Generalized $k$-core pruning process on directed networks
• Emergence of biconnected clusters in explosive percolation
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Induced Percolation on Networked Systems
• Local Articulation Points in Complex Networks
• Identifying super-spreaders in information-epidemic coevolving dynamics on multiplex networks
• Empirical determination of the optimum attack for fragmentation of modular networks
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks