Bridges in complex networks

Ang-Kun Wu, Liang Tian, and Yang-Yu Liu
Phys. Rev. E 97, 012307 – Published 17 January 2018

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 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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
3 More
  • Received 12 December 2016
  • Revised 22 April 2017

DOI:https://doi.org/10.1103/PhysRevE.97.012307

©2018 American Physical Society

Physics Subject Headings (PhySH)

Interdisciplinary PhysicsNetworksStatistical Physics & Thermodynamics

Authors & Affiliations

Ang-Kun Wu1,2,3, Liang Tian1,4, and Yang-Yu Liu1,5,*

  • 1Channing Division of Network Medicine, Brigham and Women's Hospital, Harvard Medical School, Boston, Massachusetts 02115, USA
  • 2Department of Physics, Chu Kochen Honors College, Zhejiang University, Hangzhou, Zhejiang 310027, China
  • 3Department of Physics and Astronomy, Rutgers University, Piscataway, New Jersey 08854, USA
  • 4College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
  • 5Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Boston, Massachusetts 02115, USA

  • *Author to whom all correspondence should be addressed: yyl@channing.harvard.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 97, Iss. 1 — January 2018

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×