Peng Zhang, Futian Wang, Xiang Wang, An Zeng* and Jinghu Xiao. [Scientific Reports 5, 17287 (2015)]

http://www.nature.com/articles/srep17287?trendmd-shared=0

具有社团结构复杂网络的重构

摘要：

链路预测是在很多实际系统中非常重要的问题。至今为止，已经有很多链路预测方法被提出。这些方法基本都是基于节点在网络中的拓扑结构特性来推测节点间可能存在但没有被观测到的连边。然而，大部分相关工作还停留在缺失连边概率的估算，链路预测方法在网络重构中的表现尚未得到深入的讨论。本文将若干具有代表性的链路预测方法用于网络重构，即将存在概率高的连边添加到网络中。研究发现，现存的链路预测方法不能准确的推测出社团间的连边，以至于重构网络和实际网络在拓扑性质上有很大的差别。为解决此问题，本文提出了一个社团间连边优先的链路预测方法。结果显示本文方法显著提高了网络重构的效果。虽然本文关注的是一个具体问题，但是它指出了一个链路预测的重要方向：网络中的缺失连边不是同等重要的，预测或重构时应该优先考虑对网络更为重要的连边。本文用社团结构来判定连边重要性，更一般情况下可以使用例如边介数等指标。

Abstract:

Link prediction is a fundamental problem with applications in many fields ranging from biology to computer science. In the literature, most effort has been devoted to estimate the likelihood of the existence of a link between two nodes, based on observed links and nodes’ attributes in a network. In this paper, we apply several representative link prediction methods to reconstruct the network, namely to add the missing links with high likelihood of existence back to the network. We find that all these existing methods fail to identify the links connecting different communities, resulting in a poor reproduction of the topological and dynamical properties of the true network. To solve this problem, we propose a community-based link prediction method. We find that our method has high prediction accuracy and is very effective in reconstructing the inter-community links.