A Survey on Link Prediction Problem in Social Networks
Link prediction is a crucial task in analysis of online social networks. It can be used for friend recommendations in social networks. It also has applications in other areas like bioinformatics, information retrieval and e commerce. Currently, variety of techniques is available to deal with link prediction problem, ranging from local feature based approaches to global feature based approaches. Some recent techniques combine the advantages of these two approaches and comes under hybrid category. all these methods differ from each other with respect to prediction performance in terms of accuracy, efficiency, and generalization ability. In this paper, we survey some representative link prediction techniques under each category. We largely consider three types of approaches. First category is of local feature based approaches which do not exploit the whole network structure. Second category is of global feature based approaches which use the overall path structure of a network. And, finally the hybrid approaches which combine the advantages of above two approaches (local and global) in computation of similarity scores between each pair of nodes in a network. We discuss some recent existing approaches corresponding to these broad categories and analyze their strength and weaknesses. We conclude the paper with discussion on recent developments and future research direction.