A novel similarity measure for mining missing links in long-path networks

doi:10.1088/1674-1056/ac4483

中国物理B ›› 2022, Vol. 31 ›› Issue (6): 68902-068902.doi: 10.1088/1674-1056/ac4483

所属专题： SPECIAL TOPIC — Interdisciplinary physics: Complex network dynamics and emerging technologies

A novel similarity measure for mining missing links in long-path networks

Yijun Ran(冉义军)¹, Tianyu Liu(刘天宇)¹, Tao Jia(贾韬)^1,†, and Xiao-Ke Xu(许小可)^2,‡

1 College of Computer and Information Science, Southwest University, Chongqing 400715, China;
2 College of Information and Communication Engineering, Dalian Minzu University, Dalian 116600, China

收稿日期:2021-08-04 修回日期:2021-12-01 接受日期:2021-12-21 出版日期:2022-05-17 发布日期:2022-06-07
通讯作者: Tao Jia, Xiao-Ke Xu E-mail:tjia@swu.edu.cn;xuxiaoke@foxmail.com
基金资助:
Project supported by the National Natural Science Foundation of China (Grant Nos. 61773091 and 62173065), the Industry-University-Research Innovation Fund for Chinese Universities (Grant No. 2021ALA03016), the Fund for University Innovation Research Group of Chongqing (Grant No. CXQT21005), the National Social Science Foundation of China (Grant No. 20CTQ029), and the Fundamental Research Funds for the Central Universities (Grant No. SWU119062).

A novel similarity measure for mining missing links in long-path networks

Yijun Ran(冉义军)¹, Tianyu Liu(刘天宇)¹, Tao Jia(贾韬)^1,†, and Xiao-Ke Xu(许小可)^2,‡

1 College of Computer and Information Science, Southwest University, Chongqing 400715, China;
2 College of Information and Communication Engineering, Dalian Minzu University, Dalian 116600, China

Received:2021-08-04 Revised:2021-12-01 Accepted:2021-12-21 Online:2022-05-17 Published:2022-06-07
Contact: Tao Jia, Xiao-Ke Xu E-mail:tjia@swu.edu.cn;xuxiaoke@foxmail.com
Supported by:
Project supported by the National Natural Science Foundation of China (Grant Nos. 61773091 and 62173065), the Industry-University-Research Innovation Fund for Chinese Universities (Grant No. 2021ALA03016), the Fund for University Innovation Research Group of Chongqing (Grant No. CXQT21005), the National Social Science Foundation of China (Grant No. 20CTQ029), and the Fundamental Research Funds for the Central Universities (Grant No. SWU119062).

摘要/Abstract

摘要： Network information mining is the study of the network topology, which may answer a large number of application-based questions towards the structural evolution and the function of a real system. The question can be related to how the real system evolves or how individuals interact with each other in social networks. Although the evolution of the real system may seem to be found regularly, capturing patterns on the whole process of evolution is not trivial. Link prediction is one of the most important technologies in network information mining, which can help us understand the evolution mechanism of real-life network. Link prediction aims to uncover missing links or quantify the likelihood of the emergence of nonexistent links from known network structures. Currently, widely existing methods of link prediction almost focus on short-path networks that usually have a myriad of close triangular structures. However, these algorithms on highly sparse or long-path networks have poor performance. Here, we propose a new index that is associated with the principles of structural equivalence and shortest path length (SESPL) to estimate the likelihood of link existence in long-path networks. Through a test of 548 real networks, we find that SESPL is more effective and efficient than other similarity-based predictors in long-path networks. Meanwhile, we also exploit the performance of SESPL predictor and of embedding-based approaches via machine learning techniques. The results show that the performance of SESPL can achieve a gain of 44.09% over GraphWave and 7.93% over Node2vec. Finally, according to the matrix of maximal information coefficient (MIC) between all the similarity-based predictors, SESPL is a new independent feature in the space of traditional similarity features.

关键词: structural equivalence, shortest path length, long-path networks, missing links

Abstract: Network information mining is the study of the network topology, which may answer a large number of application-based questions towards the structural evolution and the function of a real system. The question can be related to how the real system evolves or how individuals interact with each other in social networks. Although the evolution of the real system may seem to be found regularly, capturing patterns on the whole process of evolution is not trivial. Link prediction is one of the most important technologies in network information mining, which can help us understand the evolution mechanism of real-life network. Link prediction aims to uncover missing links or quantify the likelihood of the emergence of nonexistent links from known network structures. Currently, widely existing methods of link prediction almost focus on short-path networks that usually have a myriad of close triangular structures. However, these algorithms on highly sparse or long-path networks have poor performance. Here, we propose a new index that is associated with the principles of structural equivalence and shortest path length (SESPL) to estimate the likelihood of link existence in long-path networks. Through a test of 548 real networks, we find that SESPL is more effective and efficient than other similarity-based predictors in long-path networks. Meanwhile, we also exploit the performance of SESPL predictor and of embedding-based approaches via machine learning techniques. The results show that the performance of SESPL can achieve a gain of 44.09% over GraphWave and 7.93% over Node2vec. Finally, according to the matrix of maximal information coefficient (MIC) between all the similarity-based predictors, SESPL is a new independent feature in the space of traditional similarity features.

Key words: structural equivalence, shortest path length, long-path networks, missing links

中图分类号: (Networks and genealogical trees)

89.75.Hc

89.65.-s (Social and economic systems) 89.20.Ff (Computer science and technology)

Yijun Ran(冉义军), Tianyu Liu(刘天宇), Tao Jia(贾韬), and Xiao-Ke Xu(许小可). A novel similarity measure for mining missing links in long-path networks[J]. 中国物理B, 2022, 31(6): 68902-068902.

Yijun Ran(冉义军), Tianyu Liu(刘天宇), Tao Jia(贾韬), and Xiao-Ke Xu(许小可). A novel similarity measure for mining missing links in long-path networks[J]. Chin. Phys. B, 2022, 31(6): 68902-068902.

参考文献

[1] Fortunato S, Bergstrom C T, Börner K, et al. 2018 Science 359 6379
[2] Zeng A, Shen Z, Zhou J, Wu J, Fan Y, Wang Y and Stanley H 2017 Phys. Rep. 714 1
[3] Niu R W and Pan G J 2016 Chin. Phys. Lett. 33 068901
[4] Wang W X, Lai Y C, Grebogi C and Ye J 2011 Phys. Rev. X 1 021021
[5] Peixoto T P 2019 Phys. Rev. Lett. 123 128301
[6] Kirk P D W, Babtie A C and Stumpf M P H 2015 Science 350 386
[7] Girdhar N, Minz S and Bharadwaj K K 2019 Soft Comput. 23 12123
[8] Lü L and Zhou T 2011 Physica A 390 1150
[9] Lü L, Chen D, Ren X L, Zhang Q M, Zhang Y C and Zhou T 2016 Phys. Rep. 650 1
[10] Cui W, Xiao J, Li T and Xu X 2019 Chin. Phys. B 28 068901
[11] Zhu L H 2016 Chin. Phys. Lett. 33 050501
[12] Clauset A, Moore C and Newman M E J 2008 Nature 453 98
[13] Newman M E, Barabási A L and Watts D J 2006 The structure and dynamics of networks (Princeton University Press)
[14] Cannistraci C V, Alanis-Lobato G and Ravasi T 2013 Sci. Rep. 3 1
[15] Jia T, Wang D and Szymanski B K 2017 Nat. Hum. Behav. 1 1
[16] Kovács I A, Luck K, Spirohn K, et al. 2019 Nat. Commun. 10 1
[17] Ran Y, Deng X, Wang X and Jia T. 2020 Chaos 30 083127
[18] Shang K, Li T, Small M, Burton D and Wang Y 2019 Chaos 29 061103
[19] Cao R M, Liu S Y and Xu X K 2019 Chaos 29 103102
[20] Lü L and Zhou T 2010 Europhys. Lett. 89 18001
[21] Soundarajan S and Hopcroft J 2012 WWW 607
[22] Sun D, Liu S and Gong X 2020 Chin. Phys. B 29 108707
[23] Xu Z, Pu C, Sharafat R R, Li L and Yang J 2017 Chin. Phys. B 26 018902
[24] Ghasemian A, Hosseinmardi H, Galstyan A, Airoldi E M and Clauset A 2020 Proc. Natl. Acad. Sci. USA 117 23393
[25] Wang J S, Yuan J, Li Q and Yuan R X 2011 Chin. Phys. B 20 050506
[26] Ruan Y R, Lao S Y, Xiao Y D, Wang J D and Bai L 2016 Chin. Phys. Lett. 33 028901
[27] Perozzi B, Al-Rfou R and Skiena S 2014 SIGKDD 701
[28] Grover A and Leskovec J 2016 SIGKDD 855
[29] Lorrain F and White H C 1971 J. Math. Sociol. 1 49-80
[30] Liben-Nowell D and Kleinberg J 2007 J. Am. Soc. Inf. Sci. Tec. 58 1019-1031
[31] Wang K L, Wu C X, Ai J and Su Z 2019 Acta Phys. Sin. 68 196402 (in Chinese)
[32] Benson A R, Abebe R, Schaub M T, Jadbabaie A and Kleinberg J 2018 Proc. Natl. Acad. Sci. USA 115 E11221
[33] Tang D, Du W, Shekhtman L, Wang Y, Havlin S, Cao X and Yan G 2020 Natl. Sci. Rev. 5 929
[34] Newman M E J 2001 Phys. Rev. E 64 025102
[35] Jakse N and Pasturel A 2003 Phys. Rev. Lett. 91 195501
[36] Jia T, Spivey R F, Szymanski B and Korniss G 2015 PLoS One 10 e0129804
[37] Kang L, Xiang B B, Zhai S L, Bao Z K and Zhang H F 2018 Acta Phys. Sin. 67 198901 (in Chinese)
[38] Lü L, Jin C H and Zhou T 2009 Phys. Rev. E 80 046122
[39] Lv L S, Zhang K, Zhang T and Ma M Y 2019 Chin. Phys. B 28 020501
[40] Katz L 1953 Psychometrika 18 39
[41] Barabási A L and Albert R 1999 Science 286 509
[42] Cai H, Zheng V W and Chang K C C 2018 IEEE Trans. Knowl. Data Eng. 30 1616
[43] Brochier R, Guille A and Velcin J 2019 WWW 283
[44] Chen W, Zhu Z, Wang X and Jia T 2020 Acta Phys. Sin. 69 127 (in Chinese)
[45] Zhang M and Chen Y 2018 NeurIPS 31 5165
[46] Van der Maaten L and Hinton G 2008 J. Mach. Learn. Res. 9
[47] Horadam K J 2012 Hadamard matrices and their applications (Princeton University Press)
[48] Donnat C, Zitnik M, Hallac D and Leskovec J 2018 SIGKDD 1320
[49] Hogg M A 2020 Social identity theory (Stanford University Press)
[50] Pržulj N 2007 J. Bioinform. 23 e177-e183
[51] Aliakbary S, Motallebi S, Rashidian S, Habibi J and Movaghar A 2015 Chaos 25 023111
[52] Schieber T A, Carpi L, Díaz-Guilera A, Pardalos P M, Masoller C and Ravetti M G 2017 Nat. Commun. 8 1
[53] Faust K 1997 Soc. Netw. 19 157
[54] Lin J 1991 IEEE Trans. Inf. Theory 37 145
[55] Johnson D B 1973 J. ACM 20 385-388
[56] Reshef D N, Reshef Y A, Finucane H K, Grossman S R, McVean G, Turnbaugh P J, Lander E S, Mitzenmacher M and Sabeti P C 2011 Science 334 1518

A novel similarity measure for mining missing links in long-path networks

A novel similarity measure for mining missing links in long-path networks

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Fuzhong Nian(年福忠) and Xia Zhang(张霞). Topological phase transition in network spreading[J]. 中国物理B, 2023, 32(3): 38901-038901.
[2]	Dan-Dan Zhao(赵丹丹), Wang-Xin Peng(彭王鑫), Hao Peng(彭浩), and Wei Wang(王伟). Effects of heterogeneous adoption thresholds on contact-limited social contagions[J]. 中国物理B, 2022, 31(6): 68906-068906.
[3]	Dong-Jie Qian(钱冬杰). Explosive synchronization in a mobile network in the presence of a positive feedback mechanism[J]. 中国物理B, 2022, 31(1): 10503-010503.
[4]	Yu-Wei Yan(严玉为), Yuan Jiang(蒋沅), Rong-Bin Yu(余荣斌), Song-Qing Yang(杨松青), and Cheng Hong(洪成). Cascading failures of overload behaviors using a new coupled network model between edges[J]. 中国物理B, 2022, 31(1): 18901-018901.
[5]	Fuzhong Nian(年福忠), Jingzhou Li(李经洲), and Xin Guo(郭鑫). Evolution mechanism of Weibo top news competition[J]. 中国物理B, 2021, 30(12): 128901-128901.
[6]	Dongli Duan(段东立), Tao Chai(柴涛), Xixi Wu(武茜茜), Chengxing Wu(吴成星), Shubin Si(司书宾), and Genqing Bian(边根庆). Identification of unstable individuals in dynamic networks[J]. 中国物理B, 2021, 30(9): 90501-090501.
[7]	Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Complex network perspective on modelling chaotic systems via machine learning[J]. 中国物理B, 2021, 30(6): 60506-060506.
[8]	Xiao-Long Peng(彭小龙) and Yi-Dan Zhang(张译丹). Contagion dynamics on adaptive multiplex networks with awareness-dependent rewiring[J]. 中国物理B, 2021, 30(5): 58901-058901.
[9]	Zi-Wei Yuan(袁紫薇), Chang-Chun Lv(吕长春), Shu-Bin Si(司书宾), and Dong-Li Duan(段东立). Dynamical robustness of networks based on betweenness against multi-node attack[J]. 中国物理B, 2021, 30(5): 50501-050501.
[10]	. [J]. 中国物理B, 2021, 30(4): 48901-.
[11]	. [J]. 中国物理B, 2020, 29(12): 128901-.
[12]	. [J]. 中国物理B, 2020, 29(12): 128902-.
[13]	苏桂锋, 李晓温, 张小兵, 张一. Finite density scaling laws of condensation phase transition in zero-range processes on scale-free networks[J]. 中国物理B, 2020, 29(8): 88904-088904.
[14]	闫小丽, 崔亚鹏, 倪顺江. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. 中国物理B, 2020, 29(4): 48902-048902.
[15]	凌翔, 王晓坤, 陈俊杰, 刘冬, 朱孔金, 郭宁. Major impact of queue-rule choice on the performance of dynamic networks with limited buffer size[J]. 中国物理B, 2020, 29(1): 18901-018901.