Bridges in Complex Networks

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 they have a fraction of bridges that is very similar to their degree-preserving randomizations. We define an edge centrality measure, called bridgeness, to quantify the importance of a bridge in damaging a network. We find that certain real networks have a 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 and the average and variance of bridgeness for uncorrelated random networks with arbitrary degree distributions.

• Publication year

  2016

• Venue

  Physical Review E

• Publication date

  2016-11-30

• Fields of study

  Mathematics, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1103/PhysRevE.97.012307arXiv 1611.10159PMID 29448361
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Sociometry

  2020cited by this paper
• PhD thesis

  2020cited by this paper
• Eutrophication

  2019cited by this paper
• Articulation points in complex networks

  2016cited by this paper
• Graph Theory

  2016cited by this paper
• Growth And Development Ecosystems Phenomenology

  2016cited by this paper
• Nucleic Acids Research

  2015cited by this paper
• Detecting global bridges in networks

  2015cited by this paper
• Journal of Complex Networks

  2013cited by this paper
• Modern Graph Theory

  2013cited by this paper
• Density-Based and Transport-Based Core-Periphery Structures in Networks

  2013cited by this paper
• Core percolation on complex networks

  2012cited by this paper
• Variability of contact process in complex networks

  2011cited by this paper
• Bridgeness: a local index on edge significance in maintaining global connectivity

  2010cited by this paper
• Stochastic blockmodels and community structure in networks

  2010cited by this paper
• Ecological Modelling

  2009cited by this paper
• Empirically controlled mapping of the Caenorhabditis elegans protein-protein interactome network

  2009cited by this paper
• Critical phenomena in complex networks

  2007cited by this paper
• Bicomponents and the robustness of networks to failure.

  2007cited by this paper
• Fuzzy communities and the concept of bridgeness in complex networks.

  2007cited by this paper
• Influence of cultivation temperature on the ligninolytic activity of selected fungal strains

  2006cited by this paper
• Intrinsic degree-correlations in the static model of scale-free networks

  2005cited by this paper
• The Hidden Power of Social Networks: Understanding How Work Really Gets Done in Organizations

  2004cited by this paper
• Analytic solution of a static scale-free network model

  2004cited by this paper
• The Semantic Web - ISWC 2003, Second International Semantic Web Conference, Sanibel Island, FL, USA, October 20-23, 2003, Proceedings

  2003cited by this paper
• Attack vulnerability of complex networks.

  2002cited by this paper
• Food-web structure and network theory: The role of connectance and size

  2002cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• Information

  2001cited by this paper
• Universal behavior of load distribution in scale-free networks.

  2001cited by this paper
• Resilience of the internet to random breakdowns

  2000cited by this paper
• Random graphs with arbitrary degree distributions and their applications.

  2000cited by this paper
• Network robustness and fragility: percolation on random graphs.

  2000cited by this paper
• Models of core/periphery structures

  2000cited by this paper
• Internet: Diameter of the World-Wide Web

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Information, physics, and computation

  1996cited by this paper
• A Critical Point for Random Graphs with a Given Degree Sequence

  1995cited by this paper
• Random Graphs

  1985cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper
• Order propagation near the percolation threshold

  1981cited by this paper
• Proc. Nat. Acad. Sei

  1978cited by this paper
• Depth-First Search and Linear Graph Algorithms

  1972cited by this paper
• Introduction to the theory of graphs

  1971cited by this paper
• Ecology

  1964cited by this paper
• Journal of Molecular Biology

  1959cited by this paper
• The Journal of Animal Ecology

  1943cited by this paper
• Ecological Monographs

  1930cited by this paper
• Chaos

  1876cited by this paper
• Estuarine , Coastal and Shelf Science

  year unknowncited by this paper

• Topological analysis and prediction of pedestrian crash location distribution in an urban district

  2025cites this paper
• Identification and Assessment of Critical Waterways in Water Network Areas from a Community Detection Perspective

  2025cites this paper
• Enhancing the robustness of planar spatial networks

  2025cites this paper
• Network Higher-Order Structure Dismantling

  2024cites this paper
• A Distributed Method for Detecting Critical Edges and Increasing Edge Connectivity in Undirected Networks

  2024cites this paper
• A perturbation-based approach to identifying potentially superfluous network constituents.

  2023cites this paper
• Rewiring or adding links: A real-world case study of network vulnerability

  2023cites this paper
• Two-Hop Biconnected Components in the Global Liner Shipping Network Reveal International Trade Statuses

  2023cites this paper
• Non-Coding RNAs Are Brokers in Breast Cancer Interactome Networks and Add Discrimination Power between Subtypes

  2022cites this paper
• Joint Detection of Community and Structural Hole Spanner of Networks in Hyperbolic Space

  2022cites this paper
• A straightforward edge centrality concept derived from generalizing degree and strength

  2022cites this paper
• Percolation on complex networks: Theory and application

  2021cites this paper
• Fate of articulation points and bredges in percolation.

  2021cites this paper
• The characteristics of cycle-nodes-ratio and its application to network classification

  2021cites this paper
• Adaptive Cluster Synchronization of Complex Networks with Identical and Nonidentical Lur’e Systems

  2020cites this paper
• Centrally administered state-owned enterprises’ engagement in China’s public–private partnerships: a social network analysis

  2020cites this paper
• Controllability and Optimization of Complex Networks Based on Bridges

  2020cites this paper
• Statistical analysis of edges and bredges in configuration model networks.

  2020cites this paper
• Exploring significant edges of public transport network under targeted attacks

  2019cites this paper
• Structural vulnerability of quantum networks

  2019cites this paper
• Beyond bond links in complex networks:Local bridges, global bridges and silk links

  2019cites this paper
• Relational flexibility of network elements based on inconsistent community detection

  2019cites this paper
• Local Articulation Points in Complex Networks

  2018cites this paper
• A method of key links identification in command and control network based on bridging coefficient

  2018cites this paper
• Quantifying edge significance on maintaining global connectivity

  2017cites this paper
• Convex skeletons of complex networks

  2017cites this paper