An improved link prediction algorithm based on degrees and similarities of nodes

摘要

Link prediction is to calculate the probability of a potential link between a pair of unlinked nodes in the future. It has significance value in both theoretical and practical. The similarity of two nodes in the networks is an essential factor to determine the probability of a potential link between them. One of the important methods with the similarity of two nodes is to consider common neighbors of two nodes. However, the number of common neighbors only describes a kind of quantitative relationship without taking into account the topology of given networks and the information of local structure which consist of a pair of nodes and their common neighbors. Therefore, we introduce the concept of the degrees of nodes and the idea of community structure and propose a new similarity index, namely, local affinity structure(LAS). The LAS method describes the closeness of a pair of nodes and their common neighbors. We evaluated LAS on twelve different networks compared with other three similarity based indexes which consider the degree of nodes. From the experimental results, our method shows obvious superiority in improving the accuracy of link prediction.