基于最优路径相似度传输矩阵的链路预测方法

李巧丽; 韩华; 李秋晖; 曾茜; 李巧丽; 韩华; 李秋晖; 曾茜

doi:10.13306/j.1672-3813.2023.01.002

复杂系统与复杂性科学 >

2023 , Vol. 20 >Issue 1: 9 - 17

DOI: https://doi.org/10.13306/j.1672-3813.2023.01.002

基于最优路径相似度传输矩阵的链路预测方法

李巧丽 ,
韩华 ,
李秋晖 ,
曾茜 ,
李巧丽 ,
韩华 ,
李秋晖 ,
曾茜

展开

武汉理工大学理学院,武汉 430070

李巧丽(1991),女,河南平舆人,硕士,主要研究方向为复杂网络动力学、链路预测。

收稿日期: 2021-10-23

修回日期: 2021-12-07

网络出版日期: 2023-04-19

基金资助

国家自然科学基金青年科学基金(111701435);国家自然科学基金(12071364)

收起

Link Prediction Method Based on Optimal Path Similarity Transfer Matrix

LI Qiaoli ,
HAN Hua ,
LI Qiuhui ,
ZENG Xi ,
LI Qiaoli ,
HAN Hua ,
LI Qiuhui ,
ZENG Xi

Expand

Department of Science, Wuhan University of Technology, Wuhan 430070, China

Received date: 2021-10-23

Revised date: 2021-12-07

Online published: 2023-04-19

Fold

摘要

为解决现有的基于相似性的链路预测方法忽略了最优路径在节点间传递相似性的能力的问题,提出一种基于最优路径相似度传输矩阵的链路预测方法。首先,分析节点间最优路径对信息传输能力的影响,进而对节点间紧密中心性进行定义;其次,依据最优路径数和中心性构建相似度传输矩阵,综合节点间局部信息和全局属性衡量节点间相似度。最后,将所提方法与其他相似性指标,在6个真实网络上进行实证对比研究。结果表明,所提算法预测精度较高,且算法更加稳定。

关键词： 复杂网络; 链路预测; 最优路径; 相似度传输矩阵; 相似性度量; 中心性

本文引用格式

李巧丽 , 韩华 , 李秋晖 , 曾茜 , 李巧丽 , 韩华 , 李秋晖 , 曾茜 . 基于最优路径相似度传输矩阵的链路预测方法[J]. 复杂系统与复杂性科学, 2023 , 20(1) : 9 -17 . DOI: 10.13306/j.1672-3813.2023.01.002

Abstract

The current similarity-based link prediction methods ignore the ability of the optimal path to transfer similarity between nodes. To solve this problem, a link prediction method based on the optimal path similarity transmission matrix is proposed. Firstly, the influence of the optimal path between nodes on the information transmission capacity is analyzed, then the tight centrality between nodes is defined; secondly, the number of optimal paths and centrality is used to construct the similarity transmission matrix, and the local information between nodes and global attributes are integrated to evaluate the similarity between nodes. Finally, the proposed method is compared with other similarity-based algorithms in six real networks. The results show that the proposed algorithm has more accurate prediction accuracy and is more stable.

Key words： complex networks; link prediction; optimal path; similarity transfer matrix; similarity measurement; centrality

参考文献

[1] GUL H, AMIN A, ADNAN A, et al. A systematic analysis of link prediction in complex network[J]. IEEE Access, 2021, 9: 2053120541.
[2] BRUGERE I, GALLAGHER B, BERGER-WOLF T Y. Network structure inference, a survey: motivations, methods, and applications[J]. ACM Computing Surveys, 2018, 51(2): 139.
[3] ZHOU T, LÜ L Y, ZHANG Y C. Predicting missing links via local information[J]. European Physical Journal B, 2009, 71(4): 623630.
[4] CANNISTRACI C V, ALANIS-LOBATO G, RAVASI T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports, 2013, 3(4): 16131613.
[5] ASSOULI N, BENAHMED K, GASBAOUI B. How to predict crime informatics-inspired approach from link prediction[J]. Physica A: Statistical Mechanics and Its Applications, 2021(8): 125143.
[6] LORRAIN F, WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971, 1(1): 4980.
[7] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3): 211230.
[8] KATZ L. A new status index derived from sociometric index[J]. Psychometrika, 1953, 18(1): 3943.
[9] WU J H, SHEN J, ZHOU B, et al. General link prediction with influential node identification[J]. Physica A: Statistical Mechanics and Its Applications, 2019, 523( 6): 9961007.
[10] KUMAR A, SINGH S S, SINGH K, et al. Level-2 node clustering coefficient-based link prediction[J]. Applied Intelligence, 2019, 49(7): 27622779.
[11] YIN H, BENSON A R, LESKOVEC J. Higher-order clustering in networks[J]. Physical Review E, 2018, 97(5): 052306.
[12] 顾秋阳, 吴宝, 池仁勇. 基于高阶路径相似度的复杂网络链路预测方法[J]. 通信学报, 2021, 42(7): 6169.
GU Q Y, WU B, CHI R Y. Link prediction method based on the similarity of high path[J]. Journal on Communications, 2021, 42(7): 6169.
[13] YANG J, ZHANG X D. Predicting missing links in complex networks based on common neighbors and distance[J]. Scientific Reports, 2016, 6(1): 110.
[14] AHMAD I, AKHTAR M U, NOOR S, et al. Missing link prediction using common neighbor and centrality based paramete-rized algorithm[J]. Scientific Reports, 2020, 10(1): 19.
[15] 胡钢, 高浩, 徐翔, 等. 基于重要度传输矩阵的复杂网络节点重要性辨识方法[J]. 电子学报, 2020, 48(12): 24022408.
HU G, GAO H, XU X, et al. Importance identification method of complex network nodes based on importance transfer matrix[J]. Acta Electronica Sinica, 2020, 48(12): 24022408.
[16] KLEIN D J, RANDIC M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1): 8195.
[17] FOUSS F, PIROTTE A, RENDERS J M, et al. Random- walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(3): 355369.
[18] BAO Z K, MA C, XIANG B B, et al. Identification of influential nodes in complex networks: method from spreading probability viewpoint[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 468: 391397.
[19] GRIFFITH D A, CHUN Y. Spatial autocorrelation in spatial interactions models: geographic scale and resolution implications for network resilience and vulnerability[J]. Networks and Spatial Economics, 2015, 15(2): 337365.
[20] 周丽娜, 李发旭, 巩云超, 等. 基于K-shell的超网络关键节点识别方法[J].复杂系统与复杂性科学, 2021, 18(3): 1522.
ZHOU L N, LI F X, GONG Y C, et al. Identification methods of vital nodes based on K-shell in hypernetworks[J]. Complex Systems and Complexity Science, 2021, 18(3): 1522.
[21] 郭世泽, 陆哲明. 复杂网络基础理论[M].北京:科学出版社,2012.
[22] KUMAR A, MISHRA S, SINGH S S, et al. Link prediction in complex networks based on significance of higher-order path index (SHOPI)[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 545: 123790.
[23] ZHOU T, Lee Y L, Wang G. Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms[J]. Physica A: Statistical Mechanics and Its Applications, 2021, 564: 125532.
[24] LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396405.
[25] MILO, R. ITZKOVITZ S, KASHTAN N, et al. Superfamilies of evolved and designednetworks[J]. Science, 2004, 303(5663): 15381542.
[26] ZENG A, LIU W. Enhancing network robustness against malicious attacks[J]. Physical Review E, 2012, 85(6): 066130.
[27] GUIMERA R, DANON L, DIAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions[J]. Physical Review E, 2003, 68(6): 065103.
[28] ADAMIC L A, GLANCE N. The political blogosphere and the 2004 U.S. election: divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery, Chicago. USA, 2005: 3643.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献