复杂网络链接预测的路径抽样方法

Link Prediction in Complex Networks Based on Path Sampling

链接预测问题在社会学、人类学、信息科学以及计算机科学等各个领域都受到了广泛的关注.在许多现实应用中,只需要对用户感兴趣顶点的相似度进行预测,而不需要预测复杂网络中的所有顶点.提出一种快速的以路径相似度为基础的方法来预测指定的顶点对间的链接.在该方法中,首先定义顶点之间的路径相似度的概念,然后对给出的节点对之间构造一个的路径的集合,通过设定该集合适当的大小,可以将相似度的误差限制在一个给定的阈值范围内.由于只要计算相关路径的个数,因此该算法可以大大减少计算时间.以对单个节点的路径抽样方法为基础,提出了整个网络的链接预测算法.通过在实际网络上的实验结果表明,本算法与其他方法相比,在更短的时间可以获得更高精度的结果.

The link prediction problem has received extensive attention in the fields of sociology, anthropology, information science, computer science and so on. In many practical applications, we only need to predict the similarity of the vertices the users interested, but not to predict all the vertices in the complex network. In this paper, we propose a fast approach based on similarity to predict the inter link of the specified vertex pair. In the method, we first define the concept of path similarity between the nodes,and then construct a path set according to the given nodes. By setting the appropriate size of this path set, we can limit the similarity error within a given threshold. As long as the number of relevant path is calculated, the algorithm can greatly reduce the computation time. We also propose a link prediction algorithm for the whole network based on the path sampling method of a single node. Experimental results on real net- works indicate that our algorithm can obtain results with higher accuracy in less time than other methods.