CNDP: Link prediction based on common neighbors degree penalization

In social network analysis, link prediction is a fundamental tool to determine new relationships among users which are most likely to occur in the future. Link prediction by means of a similarity metric is common in which a pair of similar nodes is likely to be connected. In this paper, we propose a similarity-based link prediction algorithm, referred to as CNDP, which similarity score is determined according to the structure and specific characteristics of the network, as well as the topological characteristics. In the proposed method, a new metric for link prediction is introduced, considering clustering coefficient as a structural property of the network. Moreover, the presented method considers the neighbors of shared neighbors in addition to only shared neighbors of each pair of nodes, which leads to achieve better performance than other similar link prediction methods. The empirical results of evaluation on synthetic and real-world networks demonstrate that the proposed algorithm achieves higher accuracy prediction results with lower complexity, and performs superior compared to other algorithms.