Cost-effective Vital Nodes Identification for Network Dismantling Based on Coarse-grained Belief Propagation

This paper studies the network dismantling (ND) problem and aims to develop more effective models and approaches to cope with it, such that a given network can be dismantled by a set of vital nodes of minimum size. To achieve that, we propose a three-phase framework—the Percolation coarsening, Belief propagation dismantling, and Fragmentation optimization fine-tuning (PBF) framework—consisting of PBF-I, PBF-II, and PBF-III, where we contribute three new and one improved algorithms. In particular, PBF-I studies strategies to effectively coarsen the studied network via the merger of less influential nodes, such that the computational efficiency of the follow-up PBF-II phase can be maximized. PBF-II considers the superiority of the belief propagation (BP) algorithm in the ND problem and proposes an improved BP to identify vital nodes from the coarse-grained network, which particularly focuses on the largest connected component and obtains the vital nodes from a filtered candidate set. In addition, PBF-III presents fine-tuning strategies to further improve the quality of solutions obtained in PBF-II. The effectiveness of the proposed framework is validated on over 10 empirical networks in regard to varied circumstances. Our results show that the developed framework can obtain dismantling node sets of much smaller sizes compared to the state-of-the-art in almost all cases. Meanwhile, our framework is also more effective, efficient, and stable compared to existing methods, and is capable of tackling the ND problem in extremely large networks. We are convinced that the model and methodology introduced in this paper could be applied to many applications, such as the robustness and resilience analysis of network-structural infrastructures, the suppression of epidemics, and the containment of misinformation on social networks. The source code of the proposed PBF framework will be made publicly available upon acceptance of the manuscript.