为提高城市公共交通系统的管理效率,提出一种复杂网路链路预测算法GCNs-LP。算法整合多源数据,设计了元路径随机游走和skip-gram模型训练,通过神经网络特征学习获得节点的低维向量表示,基于节点向量对的相似度进行链路预测。实验结果表明:该算法在深圳市、上海市和南京市的地铁网络数据集上均取得了优于基线方法(CN、PA、Node2Vec、LPNMF等)的预测性能,AUC值分别提升至少29%,14.6%,7.1%。GCNs-LP算法能有效捕捉交通网络中的复杂结构特性。
In order to improve the management efficiency of urban public transportation system, a complex network link prediction algorithm GCNs-LP is proposed. The algorithm integrates multi-source data, designs the meta-path random walk and skip-gram model training, obtains the low-dimensional vector representation of nodes through the feature learning of neural network, and makes link prediction based on the similarity of node vector pairs. The experimental results show that the proposed algorithm achieves better prediction performance than the baseline method (CN, PA, Node2Vec, LPNMF, etc.) on the subway network data sets of Shenzhen, Shanghai and Nanjing, and the AUC value increases by at least 29%, 14.6% and 7.1%, respectively. GCNs-LP algorithm can capture the complex structure characteristics of traffic network effectively.
[1] DAUD N N, AB HAMID S H, SAADOON M, et al. Applications of link prediction in social networks: a review[J]. Journal of Network and Computer Applications, 2020, 166: 102716.
[2] COŞKUN M, KOYUTÜRK M. Node similarity-based graph convolution forlink prediction in biological networks[J]. Bioinformatics, 2021, 37(23): 4501-4508.
[3] GU S, LI K, LIANG Y, et al. A transportation network evolution model based on link prediction[J]. International Journal of Modern Physics B, 2021, 35(31): 2150316.
[4] ISLEK I, OGUDUCU S G. A hierarchical recommendation system for E-commerce using online user reviews[J]. Electronic Commerce Research and Applications, 2022, 52: 101131.
[5] LIAO M, SUNDAR S S. When e-commerce personalization systems show and tell: investigating the relative persuasive appeal of content-based versus collaborative filtering[J]. Journal of Advertising, 2022, 51(2): 256-267.
[6] AHMAD I, AKHTAR M U, NOOR S, et al. Missing link prediction using common neighbor and centrality based parameterized algorithm[J]. Scientific Reports, 2020, 10(1): 364.
[7] ADAMIC L A, Adar E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211-230.
[8] BAG S, KUMAR S K, TIWARI M K. An efficient recommendation generation using relevant Jaccard similarity[J]. Information Sciences, 2019, 483: 53-64.
[9] PIVA G G, RIBEIRO F L, MATA A S. Networks with growth and preferential attachment: modelling and applications[J]. Journal of Complex Networks, 2021, 9(1): cnab008.
[10] NGUYEN D H, NGUYEN C H, MAMITSUKA H. Learning subtree pattern importance for Weisfeiler-Lehman based graph kernels[J]. Machine Learning, 2021, 110(7): 1585-1607.
[11] FOROUZANDEH S, BERAHMAND K, SHEIKHPOUR R, et al. A new method for recommendation based on embedding spectral clustering in heterogeneous networks (RESCHet)[J]. Expert Systems with Applications, 2023, 231: 120699.
[12] COŞKUN M, BAGGAG A, KOYUTÜRK M. Fast computation of Katz index for efficient processing of link prediction queries[J]. Data Mining and Knowledge Discovery, 2021, 35(4): 1342-1368.
[13] SAXENA A, FLETCHER G, PECHENIZKIY M. NodeSim: node similarity based network embedding for diverse link prediction[J]. EPJ Data Science, 2022, 11(1): 24.
[14] XIAO Y, LI R, LU X, et al. Link prediction based on feature representation and fusion[J]. Information Sciences, 2021, 548: 1-17.
[15] ZHANG M H, CHEN Y X. Link prediction based on graph neural networks[C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems. Montréal, Canada, 2018: 5171-5181.
[16] ZHANG K, TIAN Z, CAI Z, et al. Link-privacy preserving graph embedding data publication with adversarial learning[J]. Tsinghua Science and Technology, 2021, 27(2): 244-256.
[17] COLEY C W, JIN W, ROGERS L, et al. A graph-convolutional neural network model for the prediction of chemical reactivity[J]. Chemical Science, 2019, 10(2): 370-377.
[18] CAI H, ZHENG V W, CHANG K C C. A comprehensive survey of graph embedding: problems, techniques, and applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(9): 1616-1637.
[19] DONG Y, CHAWLA N V, SWAMI A. metapath2vec: Scalable representation learning for heterogeneous networks[DB/OL].[2024-05-20]. https://dl.acm.org/doi/abs/10.1145/3097983.3098036.
[20] CHEN J, WANG X, XU X. GC-LSTM: Graph convolution embedded LSTM for dynamic network link prediction[J]. Applied Intelligence, 2022, 52(7): 7513-7528.
[21] CHEN J, ZHANG J, XU X, et al. E-LSTM-D: A deep learning framework for dynamic network link prediction[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 51(6): 3699-3712.
[22] MAHMOODI R, SEYEDI S A, Tab F A, et al. Link prediction by adversarial nonnegative matrix factorization[J]. Knowledge-Based Systems, 2023, 280: 110998.
[23] HANLEY J A, MCNEIL B J. The meaning and use of the area under a receiver operating characteristic (ROC) curve[J]. Radiology, 1982, 143(1): 29-36.
