Bicomponents and the robustness of networks to failure

Abstract

A common definition of a robust connection between two nodes in a network such as a communication network is that there should be at least two independent paths connecting them, so that the failure of no single node in the network causes them to become disconnected. This definition leads us naturally to consider bicomponents, subnetworks in which every node has a robust connection of this kind to every other. Here we study bicomponents in both real and model networks using a combination of exact analytic techniques and numerical methods. 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 study the size of the giant bicomponent as nodes in the network fail, using a specially developed computer algorithm based on data trees, and find in some cases that our networks are quite robust to failure, with large bicomponents persisting until almost all vertices have been removed.

5 pages, 1 figure, 1 table

References in corpus (9)

• Error and attack tolerance of complex networks
• Finding community structure in networks using the eigenvectors of matrices
• The structure of scientific collaboration networks
• The diameter of the world wide web
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Community detection in complex networks using Extremal Optimization
• Efficient Monte Carlo algorithm and high-precision results for percolation

Cited by in corpus (17)

• Percolation on complex networks: Theory and application
• Network robustness of multiplex networks with interlayer degree correlations
• Towards real-world complexity: an introduction to multiplex networks
• Large-deviation properties of the largest biconnected component for random graphs
• Bridges in Complex Networks
• Color-avoiding percolation
• Optimal redundancy against disjoint vulnerabilities in networks
• Percolation transition in correlated hypergraphs
• Bond and site color-avoiding percolation in scale free networks
• Interdependent transport via percolation backbones in spatial networks
• Critical field-exponents for secure message-passing in modular networks
• Statistical analysis of edges and bredges in configuration model networks
• Emergence of biconnected clusters in explosive percolation
• A sampling-guided unsupervised learning method to capture percolation in complex networks
• Structural Properties of Networks Grown via an Achlioptas Process
• Large deviations of connected components in the stochastic block model
• Collaboration in computer science: a network science approach. Part II