2007/08/20 by M. E. J. Newman, Gourab Ghoshal · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Artificial intelligence #Combinatorics #Complex Network Analysis Techniques #Complex network #Computer science #Connected component #Giant component #Graph #Graph theory and applications #Interdependent networks #Mathematics #Node (physics) #Physics #Random graph #Robustness (evolution) #Set (abstract data type) #Theoretical computer science #Topology (electrical circuits) #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physrevlett.100.138701
published as Phys. Rev. Lett. 100, 138701 (2008) · 5 pages, 1 figure, 1 table
arxiv created 2007/08/20 · openalex publication_date 2008/03/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study bicomponents in networks, sets of nodes such that each pair in the set is connected by at least two independent paths, so that the failure of no single node in the network can cause them to become disconnected. We show that standard network models predict there to be essentially no small bicomponents in most networks, but there may be a giant bicomponent, whose presence coincides with the presence of the ordinary giant component, and we find that real networks seem by and large to follow this pattern, although there are some interesting exceptions. We also study the size of the giant bicomponent as nodes in the network fail and find in some cases that our networks are quite robust to failure, with large bicomponents persisting until almost all vertices have been removed.