Fast Fragmentation of Networks using Module-Based Attacks

In the multidisciplinary field of Network Science, optimization of
procedures for efficiently breaking complex networks is attracting
much attention from two practical points of view: attacking and
preventing attacks or failures. In this contribution we present a
novel procedure to break complex networks guided by the identification
of modular structures. Our module-based method first identifies
communities in which the network can be represented, then it deletes
the nodes or edges that connect different modules by decreasing order
in the betweenness centrality ranking list. We illustrate the method
by applying it to various well known examples of social (Facebook,
Google+, and Twitter), infrastructure (US power grid, Euro road, Open
flights, and US airports), and biological (Yeast protein, C elegans,
and H pylori) networks. We show that the proposed method always
outperforms vertex attacks which are based on the ranking of node
degree or centrality, with a huge gain in efficiency for some
examples. Remarkably, for the US power grid, the present method breaks
the original network of 4941 nodes to many fragments smaller than 210
nodes ($\approx 4\%$ of the original size) by removing mere 142 nodes
(less than 3\%) identified by the procedure. By comparison, any
degree or centrality based procedure, deleting the same amount of
nodes, removes only 18\% of the original network, i.e. more than 4000
nodes continue to be connected after that.