Bridges in Complex Networks

Abstract

A bridge in a graph is an edge whose removal disconnects the graph and increases the number of connected components. We calculate the fraction of bridges in a wide range of real-world networks and their randomized counterparts. We find that real networks typically have more bridges than their completely randomized counterparts, but very similar fraction of bridges as their degree-preserving randomizations. We define a new edge centrality measure, called bridgeness, to quantify the importance of a bridge in damaging a network. We find that certain real networks have very large average and variance of bridgeness compared to their degree-preserving randomizations and other real networks. Finally, we offer an analytical framework to calculate the bridge fraction , the average and variance of bridgeness for uncorrelated random networks with arbitrary degree distributions.

18 pages, 10 figures

References in corpus (6)

• Critical phenomena in complex networks
• Stochastic blockmodels and community structure in networks
• Core percolation on complex networks
• Articulation Points in Complex Networks
• Bicomponents and the robustness of networks to failure
• Variability of Contact Process in Complex Networks

Cited by in corpus (10)

• Percolation on complex networks: Theory and application
• Centrally Administered State-Owned Enterprises' Engagement in China's Public-Private Partnerships: A Social Network Analysis
• The characteristics of cycle-nodes-ratio and its application to network classification
• Relational flexibility of network elements based on inconsistent community detection
• Stratified communities in complex business networks
• Convex skeletons of complex networks
• Statistical analysis of edges and bredges in configuration model networks
• A perturbation-based approach to identifying potentially superfluous network constituents
• The Fate of Articulation Points and Bredges in Percolation
• Local Articulation Points in Complex Networks