Efficient network disintegration under incomplete information: the comic effect of link prediction.
Efficient network disintegration under incomplete information: the comic effect of link prediction.
复制标题
不完全信息下的高效网络瓦解：链接预测的喜剧效果
DOI：
10.1038/srep22916
复制
发表时间：
2016-03-10
影响因子：
4.6
通讯作者：
Lu X
中科院分区：
文献类型：
--
作者：
Tan SY;Wu J;Lü L;Li MJ;Lu X
网络瓦解的研究因其在抑制流行病传播、破坏恐怖主义网络稳定、防止金融传染、控制谣言扩散和干扰癌症网络等方面的广泛应用而备受关注。这个问题的关键是找到关键节点，删除将导致网络崩溃。本文研究了链接信息不完整的网络的解体问题。提出了一种利用链路预测技术寻找关键节点的有效方法。在模拟网络和真实的网络上的大量实验表明，通过链路预测方法提前恢复部分缺失链路，该方法可以大大提高网络的解体性能。此外，我们惊奇地发现，当缺失信息的大小相对较小时，我们的方法甚至优于基于完全信息的结果。我们将这种现象称为链接预测的“漫画效应”，这意味着通过添加一些链接来重塑网络，这些链接被链接预测算法识别，重塑后的网络就像是原始网络的夸张但具有特色的漫画，其中重要部分被强调。
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.