Multi-evolutionary Features Based Link Prediction Algorithm for Social Network
HE Yulin1,2, LAI Junlong2, CUI Laizhong1,2, HUANG Zhexue1,2, YIN Jianfei2
1. Guangdong Laboratory of Artificial Intelligence and Digital Economy(SZ), Shenzhen 518107; 2. Big Data Institute, Shenzhen University, Shenzhen 518060
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.
Fund:Supported by General Project of Natural Science Foundation of Guangdong Province(No.2023A1515011667), Guangdong Basic and Applied Basic Research Foundation(No.2023B1515120020), General Project of Basic Research Foundation of Shenzhen(No.JCYJ20210324093609026), Science and Technology Major Project of Shenzhen(No.202302D074)
Corresponding Authors:
HE Yulin, Ph.D., professor. His research interests include big data system computing technologies, statistical analysis methods for multi-sample, and machine learning algorithms and their applications.
About author:: LAI Junlong, Master student. His research interests include link prediction algorithms for social networks, optimizations and applications of random weight networks. CUI Laizhong, Ph.D., professor. His research interests include internet architecture, edge computing, big data and AI-driven new network design and optimization. HUANG Zhexue, Ph.D., professor. His research interests include data mining, machine learning and big data system computing technologies. YIN Jianfei, Ph.D., associate professor. His research interests include big data, machine learning, and statistics and numerical optimizations.
HE Yulin,LAI Junlong,CUI Laizhong等. Multi-evolutionary Features Based Link Prediction Algorithm for Social Network[J]. Pattern Recognition and Artificial Intelligence, 2024, 37(7): 597-612.
[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.
2024, Vol. 37 
