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.
李巧丽, 韩华, 李秋晖, 曾茜. 基于最优路径相似度传输矩阵的链路预测方法[J]. 复杂系统与复杂性科学, 2023, 20(1): 9-17.
LI Qiaoli, HAN Hua, LI Qiuhui, ZENG Xi. Link Prediction Method Based on Optimal Path Similarity Transfer Matrix[J]. Complex Systems and Complexity Science, 2023, 20(1): 9-17.
[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.
