Improving Network Robustness by Edge Modification

An important property of networked systems is their robustness to removal of network nodes, through either random node failure or targeted attack. We present empirical results that show how robustness (as measured either by the size of the largest connected component after node removal, or by the average inverse shortest path length between nodes) is affected by several different strategies that alter the network by rewiring a fraction of the edges or by adding new edges. We find that a modest alteration of an initially ‘scale-free’ network can usefully improve robustness against attack, particularly when the fraction of attacked nodes is small, and we identify modification schemes that are most effective for this purpose.

By: Alina Beygelzimer; Geoffrey Grinstein; Ralph Linsker; Irina Rish

Published in: Physica A, volume 357, (no 3-4), pages 593-612 in 2005

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .