A Link Prediction Algorithm for Urban Public Transportation Network Based on Graph Convolution
YE Yanjun, YANG Shengwen, QIAN Chenhao
a. School of Machinery and Transportation; b. Key Laboratory of Environmental Protection and Safety of Motor Vehicles in Highland Mountainous Areas of Yunnan University, Southwest Forestry University, Kunming 650224, China
Abstract：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.
叶延军, 杨圣文, 钱琛浩. 基于图卷积的城市公共交通网络链路预测算法[J]. 复杂系统与复杂性科学, 2026, 23(3): 64-72.
YE Yanjun, YANG Shengwen, QIAN Chenhao. A Link Prediction Algorithm for Urban Public Transportation Network Based on Graph Convolution[J]. Complex Systems and Complexity Science, 2026, 23(3): 64-72.
[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.
