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

Abstract

In the field of social network analysis, Link Prediction is 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 learningbased methods have higher accuracy, but their time complexities are too high for complex networks. However, the similaritybased 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 the stretch shrink distance based algorithm (SSDBA). In SSDBA, we first detect communities of a social network and identify active nodes based on community average threshold (CAT) and node average threshold (NAT) in each community. Second, we propose the stretch 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.

Keywords

link prediction / social network / stretch shrink distance model / dynamic distance / community detection

References

[1] Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019–1031

[2] Wu L, Ge Y, Liu Q, Chen E, Hong R, Du J, Wang M. Modeling the evolution of users’ preferences and social links in social networking services. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(6): 1240–1253

[3] Liu Q, Xiang B, Yuan N J, Chen E, Xiong H, Zheng Y, Yang Y. An influence propagation view of pagerank. ACM Transactions on Knowledge Discovery from Data (TKDD), 2017, 11(3): 30

[4] Bastami E, Mahabadi A, Taghizadeh E. A gravitation-based link prediction approach in social networks. Swarm and Evolutionary Computation, 2019, 44: 176–186

[5] Backstrom L, Dwork C, Kleinberg J. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In: Proceedings of the 16th International Conference on World Wide Web. 2007, 181–190

[6] Wang D, Pedreschi D, Song C, Giannotti F, Barabasi A L. Human mobility, social ties, and link prediction. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011, 1100–1108

[7] Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missing links in networks. Nature, 2008, 453(7191): 98

[8] Ma H, Lu Z, Li D, Zhu Y, Fan L, Wu W. Mining hidden links in social networks to achieve equilibrium. Theoretical Computer Science, 2014, 556: 13–24

[9] Kuang R, Liu Q, Yu H. Community-based link prediction in social networks. In: Proceedings of International Conference on Swarm Intelligence. 2016, 341–348

[10] Shao J, Han Z, Yang Q, Zhou T. Community detection based on distance dynamics. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 1075–1084

[11] Yan B, Gregory S. Finding missing edges in networks based on their community structure. Physical Review E, 2012, 85(5): 056112

[12] Lorrain F, White H C. Structural equivalence of individuals in social networks. The Journal of Mathematical Sociology, 1971, 1(1): 49–80

[13] Newman M E J. Clustering and preferential attachment in growing networks. Physical Review E, 2001, 64(2): 025102

[14] Jaccard P. Étude comparative de la distribution florale dans une portion des Alpes et des Jura. Bulletin Société Vaudoise Sciences Naturelles, 1901, 37: 547–579

[15] Adamic L A, Adar E. Friends and neighbors on the web. Social Networks, 2003, 25(3): 211–230

[16] Song H H, Cho T W, Dave V, Zhang Y, Qiu L. Scalable proximity estimation and link prediction in online social networks. In: Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement. 2009, 322–335

[17] Katz L. A new status index derived from sociometric analysis. Psychometrika, 1953, 18(1): 39–43

[18] Tong H, Faloutsos C, Faloutsos C, Koren Y. Fast direction-aware proximity for graph mining. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2007, 747–756

[19] Yin L, Zheng H, Bian T, Deng Y. An evidential link prediction method and link predictability based on Shannon entropy. Physica A: Statistical Mechanics and its Applications, 2017, 482: 699–712

[20] Schafer J B, Frankowski D, Herlocker J, Sen S. Collaborative Filtering Recommender Systems. The Adaptive Web. Springer, Berlin, Heidelberg, 2007, 291–324

[21] Yu K, Chu W, Yu S, Tresp V, Xu Z. Stochastic relational models for discriminative link prediction. In: Proceedings of Advances in Neural Information Processing Systems. 2007, 1553–1560

[22] Bilgic M, Namata GM, Getoor L. Combining collective classification and link prediction. In: Proceedings of the 7th IEEE International Conference on Data Mining Workshops. 2007, 381–386

[23] Narayanan A, Shi E, Rubinstein B I P. Link prediction by deanonymization: how we won the kaggle social network challenge. In: Proceedings of the 2011 International Joint Conference on Neural Networks. 2011, 1825–1834

[24] Wang L, Wang Y, Liu B, He L, Liu S, Melo G D, Xu Z. Link prediction by exploiting network formation games in exchangeable graphs. In: Proceedings of the 2017 International Joint Conference on Neural Networks. 2017, 619–626

[25] Doppa J R, Yu J, Tadepalli P, Getoor L. Chance-constrained programs for link prediction. In: Proceedings of the 23rd Annual Conference on Neural Information Processing Systems Workshop on Analyzing Networks and Learning with Graphs. 2009

[26] Al Hasan M, Chaoji V, Salem S, Zaki M. Link prediction using supervised learning. In: Proceedings of the SIAM Conference on Data Mining (SDM06): Workshop on Link Analysis, Counter-terrorism and Security. 2006

[27] Oyama S, Manning C D. Using feature conjunctions across examples for learning pairwise classifiers. In: Proceedings of the European Conference on Machine Learning. 2004, 322–333

[28] Basilico J, Hofmann T. Unifying collaborative and content-based filtering. In: Proceedings of the 21st International Conference on Machine Learning. 2004

[29] Li X, Du N, Li H, Li K, Gao J, Zhang A. A deep learning approach to link prediction in dynamic networks. In: Proceedings of the 2014 SIAM International Conference on Data Mining. 2014, 289–297

[30] Liu F, Liu B, Sun C, Liu M, Wang X. Deep belief network-based approaches for link prediction in signed social networks. Entropy, 2015, 17(4): 2140–2169

[31] Hennig C, Hausdorf B. Design of Dissimilarity Measures: A New Dissimilarity Between Species Distribution Areas. Data Science and Classification. Springer, Berlin, Heidelberg. 2006, 29–37

[32] Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118–1123

[33] Erdös P, Rényi A. On random graphs. Publicationes Mathematicae Debrecen, 1959, 6: 290–297

[34] Leskovec J, Kleinberg J, Faloutsos C. Graph evolution: densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007, 1(1): 2

[35] Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 2015, 42(1): 181–213

[36] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information. The European Physical Journal B, 2009, 71(4): 623–630

[37] Ding J, Jiao L, Wu J, Liu F. Prediction of missing links based on community relevance and ruler inference. Knowledge-Based Systems, 2016, 98: 200–215

[38] De A, Bhattacharya S, Sarkar S, Ganguly N, Chakrabarti S. Discriminative link prediction using local, community, and global signals. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(8): 2057–2070

[39] Quercia D, Bodaghi M, Crowcroft J. Loosing friends on facebook. In: Proceedings of the 4th Annual ACM Web Science Conference. 2012, 251–254

RIGHTS & PERMISSIONS

Higher Education Press