Tan Suo-Yi, Wu Jun, Lü Linyuan, Li Meng-Jun, Lu Xin
College of Information System and Management, National University of Defense Technology, Changsha, Hunan, 410073, P. R. China.
Alibaba Research Center for Complexity Sciences, Alibaba Business College, Hangzhou Normal University, Hangzhou, Zhejiang, 311121, P. R.China.
Sci Rep. 2016 Mar 10;6:22916. doi: 10.1038/srep22916.
The study of network disintegration has attracted much attention due to its wide applications, including suppressing the epidemic spreading, destabilizing terrorist network, preventing financial contagion, controlling the rumor diffusion and perturbing cancer networks. The crux of this matter is to find the critical nodes whose removal will lead to network collapse. This paper studies the disintegration of networks with incomplete link information. An effective method is proposed to find the critical nodes by the assistance of link prediction techniques. Extensive experiments in both synthetic and real networks suggest that, by using link prediction method to recover partial missing links in advance, the method can largely improve the network disintegration performance. Besides, to our surprise, we find that when the size of missing information is relatively small, our method even outperforms than the results based on complete information. We refer to this phenomenon as the "comic effect" of link prediction, which means that the network is reshaped through the addition of some links that identified by link prediction algorithms, and the reshaped network is like an exaggerated but characteristic comic of the original one, where the important parts are emphasized.
由于网络瓦解在抑制疫情传播、破坏恐怖网络、防止金融传染、控制谣言扩散以及扰乱癌症网络等广泛应用中具有重要作用，因此受到了广泛关注。问题的关键在于找到那些移除后会导致网络崩溃的关键节点。本文研究了链路信息不完整的网络瓦解问题。提出了一种借助链路预测技术来寻找关键节点的有效方法。在合成网络和真实网络上进行的大量实验表明，通过提前使用链路预测方法恢复部分缺失链路，该方法能够显著提高网络瓦解性能。此外，令我们惊讶的是，我们发现当缺失信息规模相对较小时，我们的方法甚至比基于完整信息的结果表现更好。我们将这种现象称为链路预测的“漫画效应”，即通过添加一些由链路预测算法识别出的链路来重塑网络，重塑后的网络就像是原始网络的一幅夸张但具有特色的漫画，其中重要部分得到了强调。
