An Efficient Algorithm for Link Prediction Based on Local Information: Considering the Effect of Node Degree

摘要

There has been much interest in link prediction research with significant studies on how to predict missing links or future links in a network based on observed information. However, the key solution to tackle the link prediction problem is how to measure the similarity between the nodes in a network with higher accuracy. Several methods have been proposed that applies the similarity between nodes to estimate their proximity in the network. In this paper, an efficient link prediction algorithm that predicts relationships between links using the network structure is proposed, which uses common neighbors in addition to the degree distribution of the nodes to estimate the possibility of the presence of a link between two nodes in a network based on local information. Extensive experiments are carried out and compared with 10 standard similarity-based methods using 7 real-world datasets. The experimental results show that our proposed method has higher prediction accuracy compared with most of the local information based methods like the Common Neighbor and Preferential Attachment. It is also competitive with the quasi-local indicators such as LP and global indicators like Katz, with a lower computational complexity.