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

doi:10.1007/s11704-019-9083-3

Front. Comput. Sci.

2021, Vol. 15

Issue (1) : 151301 https://doi.org/10.1007/s11704-019-9083-3

RESEARCH ARTICLE

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

Ruidong YAN¹, Yi LI², Deying LI¹(

), Weili WU², Yongcai WANG¹

¹. School of Information, Renmin University of China, Beijing 100872, China
². Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080, USA

Download: PDF(829 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Deying LI

Just Accepted Date: 11 September 2019 Issue Date: 10 October 2020

Cite this article:

Ruidong YAN,Yi LI,Deying LI, et al. SSDBA: the stretch shrink distance based algorithm for link prediction in social networks[J]. Front. Comput. Sci., 2021, 15(1): 151301.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-019-9083-3
https://academic.hep.com.cn/fcs/EN/Y2021/V15/I1/151301

1	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
13	M E J Newman. Clustering and preferential attachment in growing networks. Physical Review E, 2001, 64(2): 025102 https://doi.org/10.1103/PhysRevE.64.025102
14	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
15	L A Adamic, E Adar. Friends and neighbors on the web. Social Networks, 2003, 25(3): 211–230 https://doi.org/10.1016/S0378-8733(03)00009-1
16	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
17	L Katz. A new status index derived from sociometric analysis. Psychometrika, 1953, 18(1): 39–43 https://doi.org/10.1007/BF02289026
18	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

[1]

Article highlights

Download

[1]	Di JIN, Jing HE, Bianfang CHAI, Dongxiao HE. Semi-supervised community detection on attributed networks using non-negative matrix tri-factorization with node popularity[J]. Front. Comput. Sci., 2021, 15(4): 154324-.
[2]	Gang WU, Zhiyong CHEN, Jia LIU, Donghong HAN, Baiyou QIAO. Task assignment for social-oriented crowdsourcing[J]. Front. Comput. Sci., 2021, 15(2): 152316-.
[3]	Ildar NURGALIEV, Qiang QU, Seyed Mojtaba Hosseini BAMAKAN, Muhammad MUZAMMAL. Matching user identities across social networks with limited profile data[J]. Front. Comput. Sci., 2020, 14(6): 146809-.
[4]	Qianchen YU, Zhiwen YU, Zhu WANG, Xiaofeng WANG, Yongzhi WANG. Estimating posterior inference quality of the relational infinite latent feature model for overlapping community detection[J]. Front. Comput. Sci., 2020, 14(6): 146323-.
[5]	Yiteng PAN, Fazhi HE, Haiping YU. A correlative denoising autoencoder to model social influence for top-N recommender system[J]. Front. Comput. Sci., 2020, 14(3): 143301-.
[6]	Kai LI, Guangyi LV, Zhefeng WANG, Qi LIU, Enhong CHEN, Lisheng QIAO. Understanding the mechanism of social tie in the propagation process of social network with communication channel[J]. Front. Comput. Sci., 2019, 13(6): 1296-1308.
[7]	Ratha PECH, Dong HAO, Hong CHENG, Tao ZHOU. Enhancing subspace clustering based on dynamic prediction[J]. Front. Comput. Sci., 2019, 13(4): 802-812.
[8]	Satoshi MIYAZAWA, Xuan SONG, Tianqi XIA, Ryosuke SHIBASAKI, Hodaka KANEDA. Integrating GPS trajectory and topics from Twitter stream for human mobility estimation[J]. Front. Comput. Sci., 2019, 13(3): 460-470.
[9]	Zhongqing WANG, Shoushan LI, Guodong ZHOU. Personal summarization from profile networks[J]. Front. Comput. Sci., 2017, 11(6): 1085-1097.
[10]	Yuan SU,Xi ZHANG,Lixin LIU,Shouyou SONG,Binxing FANG. Understanding information interactions in diffusion: an evolutionary game-theoretic perspective[J]. Front. Comput. Sci., 2016, 10(3): 518-531.
[11]	Siyuan LIU,Shuhui WANG,Ce LIU,Ramayya KRISHNAN. Understanding taxi drivers’ routing choices from spatial and social traces[J]. Front. Comput. Sci., 2015, 9(2): 200-209.
[12]	Peng ZHANG. Unbalanced graph cuts with minimum capacity[J]. Front. Comput. Sci., 2014, 8(4): 676-683.
[13]	Rong-Hua LI, Jianquan LIU, Jeffrey Xu YU, Hanxiong CHEN, Hiroyuki KITAGAWA. Co-occurrence prediction in a large location-based social network[J]. Front Comput Sci, 2013, 7(2): 185-194.
[14]	Xiaolong ZHENG, Yongguang ZHONG, Daniel ZENG, Fei-Yue WANG. Social influence and spread dynamics in social networks[J]. Front Comput Sci, 2012, 6(5): 611-620.
[15]	Tao WANG, Qingpeng ZHANG, Zhong LIU, Wenli LIU, Ding WEN. On social computing research collaboration patterns: a social network perspective[J]. Front Comput Sci, 2012, 6(1): 122-130.

Viewed

Full text

Abstract

Cited

Shared

Discussed