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.