  The function or performance of a network is strongly dependent on its
robustness, quantifying the ability of the network to continue functioning
under perturbations. While a wide variety of robustness metrics have been
proposed, they have their respective limitations. In this paper, we propose to
use the forest index as a measure of network robustness, which overcomes the
deficiencies of existing metrics. Using such a measure as an optimization
criterion, we propose and study the problem of breaking down a network by
attacking some key edges. We show that the objective function of the problem is
monotonic but not submodular, which impose more challenging on the problem. We
thus resort to greedy algorithms extended for non-submodular functions by
iteratively deleting the most promising edges. We first propose a simple greedy
algorithm with a proved bound for the approximation ratio and cubic-time
complexity. To confront the computation challenge for large networks, we
further propose an improved nearly-linear time greedy algorithm, which
significantly speeds up the process for edge selection but sacrifices little
accuracy. Extensive experimental results for a large set of real-world networks
verify the effectiveness and efficiency of our algorithms, demonstrating that
our algorithms outperform several baseline schemes.
