Fast Approximation Algorithms for Finding Node-Independent Paths in Networks

Douglas R. White and M. E. J. Newman

01-07-035

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.