SSDBA: the stretch shrink distance based algorithm for link prediction in social networks
Ruidong YAN1, Yi LI2, Deying LI1(), Weili WU2, Yongcai WANG1
1. School of Information, Renmin University of China, Beijing 100872, China 2. Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080, USA
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.
. [J]. Frontiers of Computer Science, 2021, 15(1): 151301.
Ruidong YAN, Yi LI, Deying LI, Weili WU, Yongcai WANG. SSDBA: the stretch shrink distance based algorithm for link prediction in social networks. Front. Comput. Sci., 2021, 15(1): 151301.
D Liben-Nowell, J Kleinberg. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019–1031 https://doi.org/10.1002/asi.20591
2
L Wu, Y Ge, Q Liu, E Chen, R Hong, J Du, M Wang. 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 https://doi.org/10.1109/TKDE.2017.2663422
3
Q Liu, B Xiang, N J Yuan, E Chen, H Xiong, Y Zheng, Y Yang. An influence propagation view of pagerank. ACM Transactions on Knowledge Discovery from Data (TKDD), 2017, 11(3): 30 https://doi.org/10.1145/3046941
4
E Bastami, A Mahabadi, E Taghizadeh. A gravitation-based link prediction approach in social networks. Swarm and Evolutionary Computation, 2019, 44: 176–186 https://doi.org/10.1016/j.swevo.2018.03.001
5
L Backstrom, C Dwork, J Kleinberg. 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 https://doi.org/10.1145/1242572.1242598
6
D Wang, D Pedreschi, C Song, F Giannotti, A L Barabasi. 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 https://doi.org/10.1145/2020408.2020581
7
A Clauset, C Moore, M E J Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 2008, 453(7191): 98 https://doi.org/10.1038/nature06830
8
H Ma, Z Lu, D Li, Y Zhu, L Fan, W Wu. Mining hidden links in social networks to achieve equilibrium. Theoretical Computer Science, 2014, 556: 13–24 https://doi.org/10.1016/j.tcs.2014.08.006
9
R Kuang, Q Liu, H Yu. Community-based link prediction in social networks. In: Proceedings of International Conference on Swarm Intelligence. 2016, 341–348 https://doi.org/10.1007/978-3-319-41009-8_37
10
J Shao, Z Han, Q Yang, T Zhou. Community detection based on distance dynamics. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 1075–1084 https://doi.org/10.1145/2783258.2783301
11
B Yan, S Gregory. Finding missing edges in networks based on their community structure. Physical Review E, 2012, 85(5): 056112 https://doi.org/10.1103/PhysRevE.85.056112
12
F Lorrain, H C White. Structural equivalence of individuals in social networks. The Journal of Mathematical Sociology, 1971, 1(1): 49–80 https://doi.org/10.1080/0022250X.1971.9989788
P Jaccard. Étude comparative de la distribution florale dans une portion des Alpes et des Jura. Bulletin Société Vaudoise Sciences Naturelles, 1901, 37: 547–579
H H Song, T W Cho, V Dave, Y Zhang, L Qiu. Scalable proximity estimation and link prediction in online social networks. In: Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement. 2009, 322–335 https://doi.org/10.1145/1644893.1644932
H Tong, C Faloutsos, C Faloutsos, Y Koren. 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 https://doi.org/10.1145/1281192.1281272
19
L Yin, H Zheng, T Bian, Y Deng. An evidential link prediction method and link predictability based on Shannon entropy. Physica A: Statistical Mechanics and its Applications, 2017, 482: 699–712 https://doi.org/10.1016/j.physa.2017.04.106
20
J B Schafer, D Frankowski, J Herlocker, S Sen. Collaborative Filtering Recommender Systems. The Adaptive Web. Springer, Berlin, Heidelberg, 2007, 291–324 https://doi.org/10.1007/978-3-540-72079-9_9
21
K Yu, W Chu, S Yu, V Tresp, Z Xu. Stochastic relational models for discriminative link prediction. In: Proceedings of Advances in Neural Information Processing Systems. 2007, 1553–1560
22
M Bilgic, GM Namata, L Getoor. Combining collective classification and link prediction. In: Proceedings of the 7th IEEE International Conference on Data Mining Workshops. 2007, 381–386 https://doi.org/10.1109/ICDMW.2007.35
23
A Narayanan, E Shi, B I P Rubinstein. 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 https://doi.org/10.1109/IJCNN.2011.6033446
24
L Wang, Y Wang, B Liu, L He, S Liu, G D Melo, Z Xu. Link prediction by exploiting network formation games in exchangeable graphs. In: Proceedings of the 2017 International Joint Conference on Neural Networks. 2017, 619–626 https://doi.org/10.1109/IJCNN.2017.7965910
25
J R Doppa, J Yu, P Tadepalli, L Getoor. 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
M Al Hasan, V Chaoji, S Salem, M Zaki. 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
S Oyama, C D Manning. Using feature conjunctions across examples for learning pairwise classifiers. In: Proceedings of the European Conference on Machine Learning. 2004, 322–333 https://doi.org/10.1007/978-3-540-30115-8_31
28
J Basilico, T Hofmann. Unifying collaborative and content-based filtering. In: Proceedings of the 21st International Conference on Machine Learning. 2004 https://doi.org/10.1145/1015330.1015394
29
X Li, N Du, H Li, K Li, J Gao, A Zhang. A deep learning approach to link prediction in dynamic networks. In: Proceedings of the 2014 SIAM International Conference on Data Mining. 2014, 289–297 https://doi.org/10.1137/1.9781611973440.33
30
F Liu, B Liu, C Sun, M Liu, X Wang. Deep belief network-based approaches for link prediction in signed social networks. Entropy, 2015, 17(4): 2140–2169 https://doi.org/10.3390/e17042140
31
C Hennig, B Hausdorf. Design of Dissimilarity Measures: A New Dissimilarity Between Species Distribution Areas. Data Science and Classification. Springer, Berlin, Heidelberg. 2006, 29–37 https://doi.org/10.1007/3-540-34416-0_4
32
M Rosvall, C T Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118–1123 https://doi.org/10.1073/pnas.0706851105
33
P Erdös, A Rényi. On random graphs. Publicationes Mathematicae Debrecen, 1959, 6: 290–297
34
J Leskovec, J Kleinberg, C Faloutsos. Graph evolution: densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007, 1(1): 2 https://doi.org/10.1145/1217299.1217301
35
J Yang, J Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 2015, 42(1): 181–213 https://doi.org/10.1007/s10115-013-0693-z
36
T Zhou, L Lü, Y C Zhang. Predicting missing links via local information. The European Physical Journal B, 2009, 71(4): 623–630 https://doi.org/10.1140/epjb/e2009-00335-8
37
J Ding, L Jiao, J Wu, F Liu. Prediction of missing links based on community relevance and ruler inference. Knowledge-Based Systems, 2016, 98: 200–215 https://doi.org/10.1016/j.knosys.2016.01.034
38
A De, S Bhattacharya, S Sarkar, N Ganguly, S Chakrabarti. Discriminative link prediction using local, community, and global signals. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(8): 2057–2070 https://doi.org/10.1109/TKDE.2016.2553665
39
D Quercia, M Bodaghi, J Crowcroft. Loosing friends on facebook. In: Proceedings of the 4th Annual ACM Web Science Conference. 2012, 251–254 https://doi.org/10.1145/2380718.2380751