Abstract The key to dynamic link prediction is modeling network dynamics and extracting local structural features. Therefore, a method for dynamic network link prediction based on node representation and subgraph structure is proposed. To model node evolution dynamics, the node2vec model is introduced, and the node representations in historical snapshots are concatenated in temporal order. To model the local subgraph structure information, a graph isomorphism algorithm is employed to encode the topology structure of the local subgraph. In each historical snapshot, the node vectors of the target node pair and the topology structure of the local subgraph are fused by the ultimate feature representation of the target link. Extensive experiments demonstrate that the proposed method achieves better performance.
Corresponding Authors:
WANG Li, Ph.D., professor. Her research interests include big data computation and analysis, knowledge graph and data mining.
About author:: HAO Xiaorong, master student. Her research interests include dynamic network link prediction and knowledge representation lear-ning. LIAN Tao, Ph.D., lecturer. His research interests include recommendation system and data mining.
[1] 徐昭娣.动态网络的高效链接预测方法研究.硕士学位论文.重庆:重庆邮电大学, 2019. (XU Z D. Research on Efficient Link Prediction Methods for Dynamic Networks. Master Dissertation. Chongqing, China: Chong-qing University of Posts and Telecommunications, 2019.) [2] LIN D K. An Information-Theoretic Definition of Similarity // Proc of the 15th International Conference on Machine Learning. New York, USA: ACM, 1998: 296-304. [3] 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. DOI: 10.1103/PhysRevE.80.046122. [4] LIBEN-NOWELL D, KLEINBERG J M. The Link-Prediction Pro-blem for Social Networks // Proc of the 20th Annual ACM International Conference on Information and Knowledge Management. New York, USA: ACM, 2003: 556-559. [5] LÜ L Y, ZHOU T. Link Prediction in Complex Networks: A Survey. Physica A(Statistical Mechanics and Its Applications), 2011, 390(6): 1150-1170. [6] YANG X H, YANG X H, LING F, et al. Link Prediction Based on Local Major Path Degree. Modern Physics Letters B, 2018, 32(29): 1850348.1-1850348.12. [7] LIU W P, LÜ L Y. Link Prediction Based on Local Random Walk. EPL(Europhysics Letters), 2010, 89(5). DOI: 10.1209/0295-5075/89/58007. [8] PEROZZI B, AI-RFOU R, SKIENA S. Deepwalk: Online Learning of Social Representations // Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2014: 701-710. [9] GROVER A, LESKOVEC J. Node2vec: Scalable Feature Learning for Networks // Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2016: 855-864. [10] ZHANG M H, CHEN Y X. Weisfeiler-Lehman Neural Machine for Link Prediction // Proc of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2017. DOI: 10.1142/S0217984918503487. [11] GÜNES I, GÜNDÜZ-GÜDÜCÜ S, CATALTEPE Z. Link Prediction Using Time Series of Neighborhood-Based Node Similarity Scores. Data Mining and Knowledge Discovery, 2016, 30(1): 147-180. [12] MUNASINGHE L, ICHISE R. Time Aware Index for Link Prediction in Social Networks // Proc of the 13th International Conference on Data Warehousing and Knowledge Discovery. Berlin, Germany: Springer-Verlag, 2011: 342-353. [13] DE SILVA SOARES P R, PRUDÊNCIO R B C. Time Series Based Link Prediction // Proc of the International Joint Conference on Neural Networks. Washington, USA: IEEE, 2012. DOI: 10.1109/IJCNN.2012.6252471. [14] NGUYEN G H, LEE J B, ROSSI R A, et al. Continuous-Time Dynamic Network Embeddings[C/OL]. [2020-07-30]. http://ryanrossi.com/pubs/nguyen-et-al-WWW18-BigNet.pdf. [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] DE WINTER S, DECUYPERE T, MITROVIC S, et al. Combining Temporal Aspects of Dynamic Networks with Node2Vec for a More Efficient Dynamic Link Prediction // Proc of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Washington, USA: IEEE, 2018: 1234-1241. [17] HOCHREITER S, SCHMIDHUBER J. Long Short-Term Memory. Neural Computation, 1997, 9(8): 1735-1780. [18] CHO K, VAN MERRIËNBOER B V, BAHDANAU D, et al. On the Properties of Neural Machine Translation: Encoder-Decoder Approaches // Proc of the 8th Workshop on Syntax, Semantics and Structure in Statistical Translation. Berlin, Germany: Springer, 2014: 103-111. [19] GOYAL P, CHHETRI S R, CANEDO A. Dyngraph2vec: Capturing Network Dynamics Using Dynamic Graph Representation Lear-ning. Knowledge-Based Systems, 2020, 187: 104816.1-104816.9. [20] 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. [21] KIPF T N, WELLING M. Semi-supervised Classification with Graph Convolutional Networks[C/OL]. [2020-07-30]. https://arxiv.org/pdf/1609.02907.pdf. [22] GOODFELLOW I J, POUGET-ABADIE J, MIRZA M, et al. Ge-nerative Adversarial Nets // Proc of the 27th International Confe-rence on Neural Information Processing Systems. Cambridge, USA: The MIT Press, 2014: 2672-2680. [23] ROSSI R A, AHMED N K. The Network Data Repository with Interactive Graph Analytics and Visualization // Proc of the 29th AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2015: 4292-4293.
2021, Vol. 34 
