Link prediction based on sampling in complex networks

摘要

The link prediction problem has received extensive attention in fields such as sociology, anthropology, information science, and computer science. In many practical applications, we only need to predict the potential links between the vertices of interest, instead of predicting all of the links in a complex network. In this paper, we propose a fast similarity based approach for predicting the links related to a given node. We construct a path set connected to the given node by a random walk. The similarity score is computed within a small sub-graph formed by the path set connected to the given node, which significantly reduces the computation time. By choosing the appropriate number of sampled paths, we can restrict the error of the estimated similarities within a given threshold. Our experimental results on a number of real networks indicate that the algorithm proposed in this paper can obtain accurate results in less time than existing methods.