【摘要】 网络分解是通过删除网络中最少规模的节点或者连边，将网络破坏至最大连通分支的规模不超过设定阈值.传统基于节点删除的网络分解算法忽略了删除代价.实际上，节点的删除导致相应连边的删除，代价是不同的.传统基于连边删除的网络分解算法虽然考虑删除代价，但是，无论是迭代计算连边中心性值，还是迭代划分最大连通分量，其性能和效率都亟待改善.本文提出了一种基于社区划分与连边逆序放回的网络分解算法，该算法是一种基于连边删除的方法，包含两个步骤，首先，利用社区划分算法将网络划分为多个社区，删除社区之间的全部连边使社区独立，破坏社区间的连通性；然后，每个社区内部采用连边逆序放回策略破坏其内部连通性，从而完成整个网络的分解.真实网络及人工网络上的实验结果表明：一方面，本文提出的网络分解算法能够以最小的连边删除代价将网络分解至设定阈值；另一方面，随着网络规模、网络结构以及分解阈值的变化，算法展现出良好的稳定性.更多还原

【Abstract】 Network dismantling aims to find the minimal set of nodes or edges that, if removed, will break the network into small components and the scale of the giant connected component shall not exceed the pre-defined threshold. Traditional node-deleting based methods ignore the cost of deletion. In fact, when we delete a node, the corresponding edges linked to this node should also be deleted. The cost is different. Although traditional edge-deleting based methods take the cost into consideration, performance and efficiency need to be further improved. This paper proposes an edge-deleting based network dismantling algorithm, which contains two stages: community detection and inverse reinsertion of edges. In the first stage, the whole network is divided into different communities by using community detection algorithm and then edges between communities are removed to destroy the connectivity of communities. In the second stage, the strategy of inverse reinsertion of edges is used to destroy the connectivity within each community. Thus, we can dismantle the whole network into pieces. Experiment results on real-world and artificial networks show that, on one hand, our proposed method can dismantle networks by removing a smaller set of edges than that of other state-of-the-art methods. On the other hand, our proposed method exhibits stable performance with the variation of network scale, network structure and the threshold of network dismantling.更多还原