Link Prediction Algorithm Based on Resource Allocation and Graph Embedding Weighting

Abstract

Abstract: Most of the weighted link prediction algorithms with weight information have higher accuracy. However, most of the existing weighting algorithms are based on the external weight information, and there are few studies based on the weight of network topology. To solve this problem, a weighted link prediction algorithm is proposed, which uses the structural features of the unweighted network to generate the structure weight. Firstly, the resource allocation index is calculated to obtain the local structure similarity of the network. Then, the DeepWalk algorithm is used to learn the network structure features to generate the node vector to obtain the cosine similarity. The two similarities are combined to define the network structure weight. Finally, experiments are carried out on four network datasets, and three different types of similarity indices W-CN, W-LP and W-RWR are compared with those without weight information. The results show that the algorithm with structural weight information has higher prediction accuracy.

Key words: link prediction, similarity, graph embedding

WAN Yang-ye, GUO Jin-li. Link Prediction Algorithm Based on Resource Allocation and Graph Embedding Weighting[J]. Computer and Modernization, 2021, 0(07): 12-17.

References

［1］ L L, ZHOU T. Link prediction in complex networks: A survey［J］. Physica A: Statistical Mechanics and Its Applications, 2011,390(6):1150-1170.
［2］ 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(1):1-14.
［3］ MA C, ZHOU T, ZHANG H F. Playing the role of weak clique property in link prediction: A friend recommendation model［J］. Scientific Reports, 2016,6(1):1-12.
［4］ ADAMIC L A, ADAR E. Friends and neighbors on the Web［J］. Social Networks, 2003,25(3):211-230.
［5］ ZHOU T, L L, ZHANG Y C. Predicting missing links via local information［J］. The European Physical Journal B, 2009,71(4):623-630.
［6］ WU Z H, LIN Y F, WANG J, et al. Link prediction with node clustering coefficient［J］. Physica A: Statistical Mechanics and Its Applications, 2016,452:1-8.
［7］ L L, JIN C H, ZHOU T. Similarity index based on local paths for link prediction of complex networks［J］. Physical Review E：Statistical, Nonlinear, and Soft Matter Physics, 2009,80(4):046122.
［8］ KATZ L. A new status index derived from sociometric analysis［J］. Psychometrika, 1953,18(1):39-43.
［9］ BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine［J］. Computer Networks & ISDN Systems, 1998,30(1-7):107-117.
［10］BAI M, HU K, TANG Y. Link prediction based on a semi-local similarity index［J］. Chinese Physics B, 2011,20(12):128902.
［11］LIU W P, LU L Y. Link prediction based on local random walk［J］. EPL (Europhysics Letters), 2010,89(5):58007.
［12］郭景峰,刘苗苗,罗旭. 加权网络中基于多路径节点相似性的链接预测［J］. 浙江大学学报(工学版), 2016,50(7):1347-1352.
［13］白杨,邓贵仕. 结合用户互动加权图的社交网络链接预测［J］. 小型微型计算机系统, 2018,39(9):1988-1992.
［14］ZHU B Y, XIA Y X. Link prediction in weighted networks: A weighted mutual information model［J］. PLoS One, 2016,11(2):e0148265.
［15］WU J H, ZHANG G J, REN Y Z, et al. Weighted local naive bayes link prediction［J］. Journal of Information Processing Systems, 2017,13(4):914-927.
［16］XU Z Q, PU C L, SHARAFAT R R, et al. Entropy-based link prediction in weighted networks［J］. Chinese Physics B, 2017,26(1):584-590.
［17］WANG L, HU K, TANG Y. Robustness of link-prediction algorithm based on similarity and application to biological networks［J］. Current Bioinformatics, 2014,9(3):246-252.
［18］ZHU M X, CAO T J, JIANG X Y. Using clustering coefficient to construct weighted networks for supervised link prediction［J］. Social Network Analysis and Mining, 2014,4(1). DOI: 10.1007/s13278-014-0215-3.
［19］袁榕,宋玉蓉,孟繁荣. 一种基于加权网络拓扑权重的链路预测方法［J］. 计算机科学, 2020,47(5):265-270.
［20］PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk: Online learning of social representations［C］// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2014:701-710.
［21］GROVER A, LESKOVEC J. Node2vec: Scalable feature learning for networks［C］// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016:855-864.
［22］TANG J, QU M, WANG M, et al. LINE: Large-scale information network embedding［C］// Proceedings of the 24th International Conference on World Wide Web. 2015:1067-1077.
［23］MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality［C］// Proceedings of the 26th International Conference on Neural Information Processing Systems. 2013:3111-3119.

[1]	YANG Jun1, HU Wei1, ZHU Wenfu2. Visual SLAM Loop Closure Detection Algorithm Based on Improved MobileNetV3 [J]. Computer and Modernization, 2024, 0(10): 21-26.
[2]	LIU Wenliang1, WU Fei1, HE Deming1, ZHAO Weiwei2, PAN Jianhong3. Text Clustering Method for Fragmented Reply Based on Dissimilarity Matrix [J]. Computer and Modernization, 2024, 0(09): 56-60.
[3]	Renqingzhuoma1, 2, 3, Yongcuo1, 2, 3, TANG Chaochao1, 2, 3. Data Filtering Strategies for Tibetan-Chinese Neural Machine Translation [J]. Computer and Modernization, 2024, 0(06): 19-24.
[4]	WANG Hong-jie, XU Sheng-chao. Clustering Method of Cloud Platform Abnormal Transmission Data Based on Hilbert Similarity [J]. Computer and Modernization, 2023, 0(09): 27-31.
[5]	WANG Hong, GE Hong. Cross Modal Hash Retrieval Based on Attention Mechanism and Semantic Similarity [J]. Computer and Modernization, 2023, 0(08): 44-53.
[6]	WEN Zi-xin, LI Shao-ying, WANG Bin-cheng, LIU Bo, . Face Clustering Method Based on Nearest Neighborhood Aggregation [J]. Computer and Modernization, 2022, 0(12): 81-87.
[7]	LIU Guo-li, XU Hong-nan, TAN You-qian. Collaborative Filtering Recommendation Algorithm Combined with Expert Trust [J]. Computer and Modernization, 2022, 0(11): 60-68.
[8]	TIAN Feng, DENG Xiao-ping, ZHANG Gui-qing, WANG Bao-yi. A Non-intrusive Load Monitoring Method Based on Improved kNN Algorithm and Transient Steady State Features [J]. Computer and Modernization, 2022, 0(10): 29-35.
[9]	CHEN Guang-fu, LIAN Yan-ping, . Link Prediction in Directed Network Combining Node Centrality and Degree-related Clustering [J]. Computer and Modernization, 2022, 0(08): 36-42.
[10]	ZENG Yi-bin, GE Hong. Cross-modal Retrieval Based on Context Fusion and Multi-similarity Learning [J]. Computer and Modernization, 2022, 0(08): 50-56.
[11]	ZOU Meng-yuan, FAN Zhi-qiang, XU Luo, LIU Jie, LIANG Wan-lu. Similarity Measurement Method of Inf-ProA Information Activity Process Model [J]. Computer and Modernization, 2022, 0(02): 26-32.
[12]	ZHU Ding-kai, TIE Zhi-xin, HONG Shun-he. An Initialization Algorithm of HRG Model and Its Application in Link Prediction [J]. Computer and Modernization, 2022, 0(02): 38-44.
[13]	GENG Hua-cong, LIANG Hong-tao, LIU Guo-zhu. Recipe Recommendation Algorithm Based on Knowledge Graph and Collaborative Filtering [J]. Computer and Modernization, 2021, 0(08): 24-29.
[14]	HUANG Hao, CHEN Li. A Collaborative Filtering Algorithm Based on Information Entropy and Improved Similarity [J]. Computer and Modernization, 2021, 0(06): 29-34.
[15]	SHU Peng, DU Qing-wei. A Method for Mobile Community Detection Based on Multi-dimensional Informational Fusion [J]. Computer and Modernization, 2021, 0(05): 88-92.