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.

arXiv comment18 pages, 10 figures

References in corpus (19)

• Community structure in social and biological networks
• The diameter of the world wide web
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• Stochastic blockmodels and community structure in networks
• Attack vulnerability of complex networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Fuzzy communities and the concept of bridgeness in complex networks
• Core percolation on complex networks
• Articulation Points in Complex Networks
• Bridgeness: A Local Index on Edge Significance in Maintaining Global Connectivity
• Bicomponents and the robustness of networks to failure
• Density-based and transport-based core-periphery structures in networks
• Analytic solution of a static scale-free network model
• Detecting global bridges in networks
• Intrinsic degree-correlations in static model of scale-free networks
• 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