Network dismantling techniques have gained increasing interest during the last years caused by the need for protecting and strengthening critical infrastructure systems in our society. We show that communities play a critical role in dismantling, given their inherent property of separating a network into strongly and weakly connected parts. The process of community-based dismantling depends on several design factors, including the choice of community detection method, community cut strategy, and inter-community node selection. We formalize the problem of community attacks to networks, identify critical design decisions for such methods, and perform a comprehensive empirical evaluation with respect to effectiveness and efficiency criteria on a set of more than 40 community-based network dismantling methods. We compare our results to state-of-the-art network dismantling, including collective influence, articulation points, as well as network decycling. We show that community-based network dismantling significantly outperforms existing techniques in terms of solution quality and computation time in the vast majority of real-world networks, while existing techniques mainly excel on model networks (ER, BA) mostly. We additionally show that the scalability of community-based dismantling opens new doors towards the efficient analysis of large real-world networks.

We acknowledge financial support from FEDER/Ministerio de Ciencia, Innovación y Universidades Agencia Estatal de Investigación/ SuMaEco Project (RTI2018-095441-B-C22) and the María de Maeztu Program for Units of Excellence in R&D (No. MDM-2017-0711). D.R.-R. also acknowledges the Fellowship No. BES-2016-076264 under the FPI program of MINECO, Spain.

Peer reviewed