Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (8): 116-123.DOI: 10.3778/j.issn.1002-8331.1801-0002

Previous Articles     Next Articles

Katz Auto Encoder for Urban Road Network Link Prediction Model

SHENG Jinfang, LIU Jiaguang, WANG Bin   

  1. School of Information Science and Engineering, Central South University, Changsha 410083, China
  • Online:2019-04-15 Published:2019-04-15

基于Katz自动编码器的城市路网链路预测模型

盛津芳,刘家广,王  斌   

  1. 中南大学 信息科学与工程学院,长沙 410083

Abstract: Urban road network is a special complex network. The link prediction of road network has important application value in urban planning and urban structure evolution. As the road network is highly sparse and nonlinear, this paper proposes a road network link prediction model based on the Katz Auto Encoder Network Embedding(hereafter as KAENE). This prediction model is a deep learning network embedding model based on the auto encoder with the following characteristics. First, it uses Katz similarity matrix to preserve the structural characteristics of the road network. Second, the multi-layer non-linear auto encoder is used to learn network characterization of the road network. Third, during the model training period, it uses LLEloss function to preserve the local characteristics of the road network. Forth, it also uses L2-norm to prevent overfitting. Finally, it combines with the directional characteristics of the road network to improve the link prediction accuracy of the road network. Through experiments, this paper compares the different performance between KAENE model and other link prediction models using different urban road network data, at the same time, it also identifies the influence of different embedded dimensions on the prediction accuracy of KAENE model. At last, the network characterization learning process of this model through visualization is known. The experimental results show that KAENE achieves a good performance in the link prediction tasks of six representative road network datasets at home and aboard.

Key words: complex networks, link prediction, network embedding, auto encoder, urban road network

摘要: 城市交通道路网络(以下简称“路网”)是一种特殊的复杂网络,对路网进行链路预测在城市规划与城市结构演化方面有着重要的应用价值。针对路网的高度稀疏性、高度非线性特点,提出了一种基于Katz相似度自动编码器(Katz Auto Encoder Network Embedding,KAENE)的路网链路预测模型,它是一种基于自动编码器的深度学习网络嵌入模型,使用Katz相似度矩阵保存路网的结构特征,利用多层非线性自动编码器对路网进行网络表征学习,在模型训练阶段通过局部线性嵌入损失函数保存路网的局部特征,在此基础上引入L2范数来提高模型的泛化能力,最后结合路网的方向性特征提高路网的链路预测精确度。通过实验对比了KAENE模型与其他链路预测模型在国内外的不同城市路网数据上的表现以及不同嵌入维度对KAENE模型预测精度的影响,最后通过可视化了解了模型的网络表征学习过程。实验结果表明,KAENE在国内外6个具有代表性的路网数据集的链路预测任务中取得了良好的表现。

关键词: 复杂网络, 链路预测, 网络嵌入, 自动编码器, 城市路网