Hidden link prediction based on node centrality and weak ties

¹ Key Laboratory of Universal Wireless Communications (Beijing University of Posts and Telecommunications), Ministry of Education - Beijing, China
² School of Electronic Engineering and Computer Science Queen Mary, University of London London, UK, EU

Received: 30 September 2012
Accepted: 20 December 2012

Abstract

Link prediction has been widely used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. In this context, similarity-based algorithms have become the mainstream. However, most of them take into account the contributions of each common neighbor equally to the connection likelihood of two nodes. This paper proposes a model for link prediction, which is based on the node centrality of common neighbors. Three node centralities are discussed: degree, closeness and betweenness centrality. In our model, each common neighbor plays a different role to the node connection likelihood according to their centralities. Moreover, the weak-tie theory is considered for improving the prediction accuracy. Finally, extensive experiments on five real-world networks show that the proposed model can outperform the Common Neighbor (CN) algorithm and gives competitively good prediction of or even better than Adamic-Adar (AA) index and Resource Allocation (RA) index.