A network is robust to the extent that it is not vulnerable to disconnection by removal of nodes. The minimum number of nodes that need be removed to disconnect a pair of other nodes is called the connectivity of the pair. It can be proved that the connectivity is also equal to the number of node-independent paths between nodes, and hence we can quantify network robustness by calculating numbers of node-independent paths. Unfortunately, computing such numbers is known to be an NP-hard problem, taking exponentially long to run to completion. In this paper, we present an approximation algorithm which gives good lower bounds on numbers of node-independent paths between any pair of nodes on a directed or undirected graph in worst-case time which is linear in the graph size. A variant of the same algorithm can also calculate all the k-components of a graph in the same approximation. Our algorithm is found empirically to work with better than 99% accuracy on random graphs and for several real-world networks is 100% accurate. As a demonstration of the algorithm, we apply it to two large graphs for which the traditional NP-hard algorithm is entirely intractable--a network of collaborations between scientists and a network of business ties between biotechnology firms.
Download Info
To our knowledge, this item is not available for
download. To find whether it is available, there are three
options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page
whether it is in fact available.
3. Perform a search for a similarly titled item that would be
available.
Publisher Info
Paper provided by Santa Fe Institute in its series Working Papers with number
01-07-035.