Bicomponents and the robustness of networks to failure.
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.
Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA.
M E J
ME
Newman
Gourab
G
Ghoshal
D000465:Algorithms; D001704:Biopolymers / Q000737:chemistry; D003195:Computer Communication Networks; D007255:Information Services; D008962:Models, Theoretical; D008968:Molecular Conformation
D001704:Biopolymers