Sun Jiachen, Liu Rong, Fan Zhengping, Xie Jiarong, Ma Xiao, Hu Yanqing
School of Electronics and Information Technology, Sun Yat-sen University, Guangzhou 510006, China.
School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China.
Chaos. 2018 Jun;28(6):063128. doi: 10.1063/1.5024338.
The network dismantling problem is one of the most fundamental problems in network science. It aims to identify the minimum number of nodes, such that after their removal the network is broken into many disconnected pieces with a sub-extensive size. However, the identification of the minimum removed nodes belongs to the class of nondeterministic polynomial problems. Although many heuristic algorithms have been proposed to identify the removed nodes, the smallest dismantling set remains unknown. Therefore, the determination of a good lower bound of dismantling sets is of great significance to evaluating the performances of heuristic algorithms. The minimum number of deleted nodes to dismantle a network is strictly no smaller than that to dismantle its any subnetwork in nature. Any lower bound of a subnetwork is indeed a lower bound of the original network. Utilizing the heterogeneous degree distribution and 2-core properties, we find that with previous removal of some appropriate nodes, the lower bound obtained on the basis of the subnetwork is counterintuitively significantly better than the one obtained directly on the original network, especially for the real-world networks.
网络拆解问题是网络科学中最基本的问题之一。它旨在确定最少数量的节点，使得在这些节点被移除后，网络被分解为许多规模次广泛的不相连部分。然而，确定最少移除节点属于非确定性多项式问题类别。尽管已经提出了许多启发式算法来识别移除节点，但最小拆解集仍然未知。因此，确定拆解集的良好下界对于评估启发式算法的性能具有重要意义。本质上，拆解一个网络所需删除的最少节点数严格不小于拆解其任何子网所需的最少节点数。子网的任何下界实际上都是原始网络的下界。利用异质度分布和2-核属性，我们发现，通过事先移除一些合适的节点，基于子网获得的下界比直接在原始网络上获得的下界在直观上要好得多，特别是对于现实世界的网络。
