Finding an optimal subset of nodes in a network that is able to disrupt the functioning of a corrupt or criminal organization or contain an epidemic or the spread of misinformation is still one of the open problems in modern network science. In this paper, we introduce the generalized network dismantling problem, which aims at finding a minimum set of nodes that, when removed from a network, results in the fragmentation of a network into sub-critical network components at minimum cost. Contrary to previous formulations, we allow the costs for node removal to take arbitrary non-negative real value. For unit costs, our formulation becomes equivalent to the standard network dismantling problem. Our non-unit cost generalization allows one to consider topological cost functions related to node centrality or non-topological features such as the price or protection level of a node. In order to solve this optimization problem, we propose a method, which is based on the spectral properties of a novel node-weighted Laplacian operator. The proposed GND method is applicable to large-scale networks with millions of nodes. It outperforms current state-of-the-art methods and opens new directions for understanding the vulnerability and robustness of complex systems.
