A hybrid method of link prediction in directed graphs

摘要

Link prediction is an important issue in complex network analysis and mining. Given the structure of a network, a link prediction algorithm obtains the probability that a link is established between two non-adjacent nodes in the future snapshots of the network. Many of the available link prediction methods are based on common neighborhood. A problem with these methods is that if two nodes do not have any common neighbors, they always predict a chance of zero for establishment of a link between them; however, such nodes have been shown to establish links in some real systems. Another issue with these measures is that they often disregard the connection direction. Here, we propose a novel measure based on common neighborhood that resolves the above issues. The proposed measures are applied on three benchmark networks in both unsupervised and supervised learning modes. Our experiments show the superior performance of the proposed measures over that of the state-of-the-art link prediction methods.