Ren Xiao-Long, Gleinig Niels, Helbing Dirk, Antulov-Fantulin Nino
Computational Social Science, ETH Zürich, 8092 Zürich, Switzerland.
Department of Computer Science, ETH Zürich, 8092 Zürich, Switzerland.
Proc Natl Acad Sci U S A. 2019 Apr 2;116(14):6554-6559. doi: 10.1073/pnas.1806108116. Epub 2019 Mar 15.
Finding an optimal subset of nodes in a network that is able to efficiently disrupt the functioning of a corrupt or criminal organization or contain an epidemic or the spread of misinformation is a highly relevant problem of network science. In this paper, we address the generalized network-dismantling problem, which aims at finding a set of nodes whose removal from the network results in the fragmentation of the network into subcritical network components at minimal overall cost. Compared with previous formulations, we allow the costs of node removals to take arbitrary nonnegative real values, which may depend on topological properties such as node centrality or on nontopological features such as the price or protection level of a node. Interestingly, we show that nonunit costs imply a significantly different dismantling strategy. To solve this optimization problem, we propose a method which is based on the spectral properties of a node-weighted Laplacian operator and combine it with a fine-tuning mechanism related to the weighted vertex cover problem. The proposed method is applicable to large-scale networks with millions of nodes. It outperforms current state-of-the-art methods and opens more directions for understanding the vulnerability and robustness of complex systems.
在网络中找到一个最优节点子集，使其能够有效破坏腐败或犯罪组织的运作，或遏制流行病或错误信息的传播，这是网络科学中一个高度相关的问题。在本文中，我们研究广义网络拆解问题，其目标是找到一组节点，从网络中移除这些节点会以最小的总成本将网络分割成亚临界网络组件。与之前的公式相比，我们允许节点移除成本取任意非负实值，这些值可能取决于诸如节点中心性等拓扑属性，或取决于诸如节点价格或保护级别等非拓扑特征。有趣的是，我们表明非单位成本意味着一种显著不同的拆解策略。为了解决这个优化问题，我们提出一种基于节点加权拉普拉斯算子谱特性的方法，并将其与与加权顶点覆盖问题相关的微调机制相结合。所提出的方法适用于具有数百万个节点的大规模网络。它优于当前的最先进方法，并为理解复杂系统的脆弱性和鲁棒性开辟了更多方向。
