基于多演化特征的社交网络链路预测算法

doi:10.16451/j.cnki.issn1003-6059.202407003

摘要
图/表
参考文献
相关文章 (10)

全文: PDF (3257 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要社交网络链路预测旨在根据已知的网络信息预测未来的链接关系,在推荐系统和合著网络中具有重要作用.然而,现有链路预测算法往往忽视社交网络的多元演化特点,训练时间复杂度较高,限制其执行效率.针对上述问题,文中提出基于多演化特征的社交网络链路预测算法(Multi-evolutionary Features Based Link Prediction Algorithm for Social Network, MEF-LP).首先,设计一种简单高效的时间极限学习机模型,利用门控网络和极限学习机自编码器传递与聚合社交网络快照序列的时间信息.然后,构建多个深度极限学习机,对时间特征进行多角度映射,挖掘社交网络不同的演化特征,并最终融合成综合演化特征.最后,使用基于极限学习机的分类器完成链路预测.在6个真实社交网络上的实验表明,MEF-LP能合理学习社交网络的多演化特征,并获得较优的预测性能.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	何玉林
	赖俊龙
	崔来中
	黄哲学
	尹剑飞

关键词 ：社交网络分析, 链路预测, 多元演化, 网络快照, 极限学习机

Abstract：Social network link prediction aims to predict future link relationships based on known network information, in which there are important applications for recommender systems and co-authorship networks. However, existing link prediction algorithms often ignore multi-evolutionary features of social networks and have high training time complexity, limiting their execution efficiency and application performance. To address these problems, a multi-evolutionary features based link prediction algorithm for social network(MEF-LP) is proposed. Firstly, a simple and efficient time extreme learning machine model is designed to transfer and aggregate the temporal information of social network snapshot sequences, using gated networks and extreme learning machine self-encoders. Secondly, multiple multilayer extreme learning machines are constructed to map temporal features from multiple perspectives, mining different evolutionary features of social networks and ultimately integrating them into comprehensive evolutionary features. Finally, the extreme learning machine-based classifiers are utilized to complete the link prediction. Experiments on six real social networks show that MEF-LP can reasonably learn the multi-evolution features of social networks and achieve better prediction performance.

Key words： Social Network Analysis Link Prediction Multiple Evolution Network Snapshot Extreme Learning Machine

收稿日期: 2024-06-26

ZTFLH:

TP391

基金资助:广东省自然科学基金面上项目(No.2023A1515011667)、广东省基础与应用基础研究基金粤深联合基金重点项目(No.2023B1515120020)、深圳市基础研究面上项目(No.JCYJ20210324093609026)、深圳市科技重大专项项目(No.202302D074)资助

通讯作者: 何玉林,博士,研究员,主要研究方向为大数据系统计算技术、多样本统计分析方法、机器学习算法及应用.E-mail:yulinhe@gml.ac.cn.

作者简介: 赖俊龙,硕士研究生,主要研究方向为社交网络链路预测算法、随机权重网络优化及应用.E-mail:junlong_lai1@163.com.崔来中,博士,教授,主要研究方向为互联网体系结构、边缘计算、大数据、人工智能驱动的新型网络优化设计.E-mail: cuilz@szu.edu.cn.黄哲学,博士,教授,主要研究方向为数据挖掘、机器学习、大数据系统计算技术.E-mail:zx.huang@szu.edu.cn.尹剑飞,博士,副教授,主要研究方向为大数据、机器学习、统计和数值优化.E-mail: yjf@szu.edu.cn.

引用本文:

何玉林, 赖俊龙, 崔来中, 黄哲学, 尹剑飞. 基于多演化特征的社交网络链路预测算法[J]. 模式识别与人工智能, 2024, 37(7): 597-612. HE Yulin, LAI Junlong, CUI Laizhong, HUANG Zhexue, YIN Jianfei. Multi-evolutionary Features Based Link Prediction Algorithm for Social Network. Pattern Recognition and Artificial Intelligence, 2024, 37(7): 597-612.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.202407003 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2024/V37/I7/597

[1] NASIRI E, BERAHMAND K, SAMEI Z, et al. Impact of Centrality Measures on the Common Neighbors in Link Prediction for Multiplex Networks. Big Data, 2022, 10(2): 138-150.
[2] VITAL A, AMANCIO D R. A Comparative Analysis of Local Similarity Metrics and Machine Learning Approaches: Application to Link Prediction in Author Citation Networks. Scientometrics, 2022, 127(10): 6011-6028.
[3] ORZECHOWSKI K P, MROWINSKI M J, FRONCZAK A, et al. Asymmetry of Social Interactions and Its Role in Link Predictability: The Case of Coauthorship Networks. Journal of Informetrics, 2023, 17(2). DOI: 10.1016/j.joi.2023.101405.
[4] MA Z M, NANDY S. Community Detection with Contextual Multilayer Networks. IEEE Transactions on Information Theory, 2023, 69(5): 3203-3239.
[5] ADAMIC L A, ADAR E. Friends and Neighbors on the Web. Social Networks, 2003, 25(3): 211-230.
[6] KATZ L. A New Status Index Derived from Sociometric Analysis. Psychometrika, 1953, 18(1):39-43.
[7] NEWMAN M E J. Clustering and Preferential Attachment in Growing Networks. Physical Review E, 2001, 64(2). DOI: 10.1103/Phys-RevE.64.025102.
[8] ZHOU T, LÜ L Y, ZHANG Y C. Predicting Missing Links via Local Information. The European Physical Journal B, 2009, 71(4): 623-630.
[9] JEH G, WIDOM J. SimRank: A Measure of Structural-Context Simi-larity // Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2002: 538-543.
[10] LÜ L Y, JIN C H, ZHOU T. Similarity Index Based on Local Paths for Link Prediction of Complex Networks. Physical Review E, 2009, 80(4). DOI: 10.1103/PhysRevE.80.046122.
[11] KUMARI A, BEHERA R K, SAHOO K S, et al. Supervised Link Prediction Using Structured-Based Feature Extraction in Social Network. Concurrency and Computation: Practice and Experience, 2022, 34(13). DOI: 10.1002/cpe.5839.
[12] KUMAR S, MALLIK A, PANDA B S. Link Prediction in Complex Networks Using Node Centrality and Light Gradient Boosting Machine. World Wide Web, 2022, 25(6): 2487-2513.
[13] LIU X Y, LI X. A Social Network Link Prediction Method Based on Stacked Generalization. The Computer Journal, 2022, 65(10): 2693-2708.
[14] CHAUBEY V P, SHARMA A, SHARMA T, et al. Link Prediction for Social Network Analysis Using Random Forest and XG-Boost Algorithm // Proc of the 2nd International Conference on Informatics. Washington, USA: IEEE, 2023. DOI: 10.1109/ICI60088.2023.10421655.
[15] AHMED N M, CHEN L, WANG Y L, et al. DeepEye: Link Prediction in Dynamic Networks Based on Non-negative Matrix Factorization. Big Data Mining and Analytics, 2018, 1(1): 19-33.
[16] MA X K, SUN P G, WANG Y. Graph Regularized Nonnegative Matrix Factorization for Temporal Link Prediction in Dynamic Networks. Physica A: Statistical Mechanics and Its Applications, 2018, 496: 121-136.
[17] MAHMOODI R, SEYEDI S A, TAB F A, et al. Link Prediction by Adversarial Nonnegative Matrix Factorization. Knowledge-Based Systems, 2023, 280. DOI: 10.1016/j.knosys.2023.110998.
[18] NASIRI E, BERAHMAND K, LI Y F. Robust Graph Regularization Nonnegative Matrix Factorization for Link Prediction in Attributed Networks. Multimedia Tools and Applications, 2023, 82(3): 3745-3768.
[19] CHEN G F, WANG H B, FANG Y L, et al. Link Prediction by Deep Non-negative Matrix Factorization. Expert Systems with Applications, 2022, 188. DOI: 10.1016/j.eswa.2021.115991.
[20] MA X K, TAN S Y, XIE X H,et al. Joint Multi-label Learning and Feature Extraction for Temporal Link Prediction. Pattern Re-cognition, 2022, 121. DOI: 10.1016/j.patcog.2021.108216.
[21] YU W C, AGGARWAL C C, WANG W. Temporally Factorized Network Modeling for Evolutionary Network Analysis // Proc of the 10th ACM International Conference on Web Search and Data Mi-ning. New York, USA: ACM, 2017: 455-464.
[22] YU W C, CHENG W, AGGARWAL C C, et al. Link Prediction with Spatial and Temporal Consistency in Dynamic Networks // Proc of the 26th International Joint Conference on Artificial Intelligence. San Francisco, USA: IJCAI, 2017: 3343-3349.
[23] CHEN J Y, ZHANG J, XU X H, et al. E-LSTM-D: A Deep Lear-ning Framework for Dynamic Network Link Prediction. IEEE Transactions on Systems, Man, and Cybernetics(Systems), 2021, 51(6): 3699-3712.
[24] JIAO P F, GUO X, JING X, et al. Temporal Network Embedding for Link Prediction via VAE Joint Attention Mechanism. IEEE Tran-sactions on Neural Networks and Learning Systems, 2021, 33(12): 7400-7413.
[25] CHEN J Y, WANG X K, XU X H. GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Network Link Prediction. Applied Intelligence, 2022, 52: 7513-7528.
[26] TAN S Y, YOU J Y, LI D Y. Temporality- and Frequency-Aware Graph Contrastive Learning for Temporal Network // Proc of the 31st ACM International Conference on Information and Knowledge Management. New York, USA: ACM, 2022: 1878-1888.
[27] MEI P, ZHAO Y H. Dynamic Network Link Prediction with Node Representation Learning from Graph Convolutional Networks. Scientific Reports, 2024, 14(1). DOI: 10.1038/s41598-023-50977-6.
[28] QIN M, ZHANG C R, BAI B,et al. High-Quality Temporal Link Prediction for Weighted Dynamic Graphs via Inductive Embedding Aggregation. IEEE Transactions on Knowledge and Data Enginee-ring, 2023, 35(9): 9378-9393.
[29] YIN Y T, WU Y J, YANG X B, et al. Super Resolution Graph with Conditional Normalizing Flows for Temporal Link Prediction. IEEE Transactions on Knowledge and Data Engineering, 2024, 36(3): 1311-1327.
[30] ZHOU L K, YANG Y, REN X, et al. Dynamic Network Embe-dding by Modeling Triadic Closure Process. Proceedings of the AAAI Conference on Artificial Intelligence, 2018, 32(1): 571-578.
[31] SANKAR A, WU Y H, GOU L, et al. DySAT: Deep Neural Re-presentation Learning on Dynamic Graphs via Self-Attention Networks // Proc of the 13th International Conference on Web Search and Data Mining. New York, USA: ACM, 2020: 519-527.
[32] HUANG G B, ZHU Q Y, SIEW C K. Extreme Learning Machine: Theory and Applications. Neurocomputing, 2006, 70(1/2/3): 489-501.
[33] HUANG G B, ZHOU H M, DING X J, et al. Extreme Learning Machine for Regression and Multiclass Classification. IEEE Transactions on Systems, Man, and Cybernetics(Cybernetics), 2012, 42(2): 513-529.
[34] RAO C R, MITRA S K. Generalized Inverse of a Matrix and Its Applications // Proc of the 6th Berkeley Symposium on Mathematical Statistics and Probability. Oakland, USA: University of California Press, 1972: 601-620.
[35] HUANG G, HUANG G B, SONG S J, et al. Trends in Extreme Learning Machines: A Review. Neural Networks, 2015, 61: 32-48.
[36] HUANG G B, BAI Z, LEKAMALAGE L, et al. Local Receptive Fields Based Extreme Learning Machine. IEEE Computational Intelligence Magazine, 2015, 10(2): 18-29.
[37] LEI K, QIN M, BAI B, et al. GCN-GAN: A Non-linear Temporal Link Prediction Model for Weighted Dynamic Networks // Proc of the IEEE Conference on Computer Communications. Washington, USA: IEEE, 2019: 388-396.
[38] FIRE M, TENENBOIM L, LESSER O, et al. Link Prediction in Social Networks Using Computationally Efficient Topological Features // Proc of the IEEE 3rd International Conference on Privacy, Security, Risk and Trust and IEEE 3rd International Conference on Social Computing. Washington, USA: IEEE, 2011: 73-80.
[39] HUANG Z, LI X, CHEN H. Link Prediction Approach to Collaborative Filtering // Proc of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries. New York, USA: ACM, 2005: 141-142.
[40] QI Y, LUO J W. Prediction of Essential Proteins Based on Local Interaction Density. IEEE/ACM Transactions on Computational Bio-logy and Bioinformatics, 2016, 13(6): 1170-1182.
[41] RIQUELME F, GONZALEZ-CANTERGIANI P, MOLINERO X, et al. Centrality Measure in Social Networks Based on Linear Thre-shold Model. Knowledge-Based Systems, 2018, 140: 92-102.
[42] SCARDONI G, PETTERLINI M, LAUDANNA C. Analyzing Biological Network Parameters with CentiScaPe. Bioinformatics, 2009, 25(21): 2857-2859.
[43] KLEINBERG J M. Authoritative Sources in a Hyperlinked Environ-ment. Journal of the ACM, 1999, 46(5): 604-632.
[44] BRIN S, PAGE L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/6/7): 107-117.