SSDBA: the stretch shrink distance based algorithm for link prediction in social networks

In the field of social network analysis,Link Predictionis one of the hottest topics which has been attracted attentions in academia and industry. So far, literatures for solving link prediction can be roughly divided into two categories: similarity-based and learning-based methods. The learning-based methods have higher accuracy, but their time complexities are too high for complex networks. However, the similarity-based methods have the advantage of low time consumption, so improving their accuracy becomes a key issue. In this paper, we employ community structures of social networks to improve the prediction accuracy and propose thestretch shrink distance based algorithm(SSDBA). In SSDBA, we first detect communities of a social network and identify active nodes based oncommunity average threshold(CAT) andnode average threshold(NAT) in each community. Second, we propose thestretch shrink distance(SSD) model to iteratively calculate the changes of distances between active nodes and their local neighbors. Finally, we make predictions when these links' distances tend to converge. Furthermore, extensive parameters learning have been carried out in experiments. We compare our SSDBA with other popular approaches. Experimental results validate the effectiveness and efficiency of proposed algorithm.