基于Katz自动编码器的城市路网链路预测模型
|
摘要
城市交通道路网络(以下简称"路网")是一种特殊的复杂网络,对路网进行链路预测在城市规划与城市结构演化方面有着重要的应用价值。针对路网的高度稀疏性、高度非线性特点,提出了一种基于Katz相似度自动编码器(Katz Auto Encoder Network Embedding,KAENE)的路网链路预测模型,它是一种基于自动编码器的深度学习网络嵌入模型,使用Katz相似度矩阵保存路网的结构特征,利用多层非线性自动编码器对路网进行网络表征学习,在模型训练阶段通过局部线性嵌入损失函数保存路网的局部特征,在此基础上引入L2范数来提高模型的泛化能力,最后结合路网的方向性特征提高路网的链路预测精确度。通过实验对比了KAENE模型与其他链路预测模型在国内外的不同城市路网数据上的表现以及不同嵌入维度对KAENE模型预测精度的影响,最后通过可视化了解了模型的网络表征学习过程。实验结果表明,KAENE在国内外6个具有代表性的路网数据集的链路预测任务中取得了良好的表现。
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 multilayer 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.
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 multilayer 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.
引文
[1]Zhao F,Sun H,Wu J,et al.Analysis of road network pattern considering population distribution and central business district[J].PloS One,2016,11(3):e0151676.
[2]Zhao Y,Wu Y J,Levina E,et al.Link prediction for partially observed networks[J].Journal of Computational and Graphical Statistics,2017.
[3]宋海权,郭进,刘刚.基于复杂网络的城市道路重要度评价及路网自动综合方法[J].测绘工程,2017,26(1):8-12.
[4]赵国锋,苑少伟,慈玉生.城市路网的复杂网络特性和鲁棒性研究[J].公路交通科技,2016,33(1):119-124.
[5]Goyal P,Ferrara E.Graph embedding techniques,applications,and performance:a survey[J].Knowledge-Based Systems,2018,151:78-94.
[6]吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39(5):651-661.
[7]Belkin M,Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Advances in Neural Information Processing Systems,2002:585-591.
[8]Grover A,Leskovec J.node2vec:scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining,2016:855-864.
[9]Wang D,Cui P,Zhu W.Structural deep network embedding[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2016:1225-1234.
[10]Ahmed A,Shervashidze N,Narayanamurthy S,et al.Distributed large-scale natural graph factorization[C]//Proceedings of the 22nd international Conference on World Wide Web,2013:37-48.
[11]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.
[12]Lee D.Learning the parts of objects with nonnegative matrix factorization[J].Nature,1999,401(6755):788.
[13]Dan K.A singularly valuable decomposition:the SVDof a matrix[J].College Mathematics Journal,1996,27(1):2-23.
[14]Ou M,Cui P,Pei J,et al.Asymmetric transitivity preserving graph embedding[C]//KDD,2016:1105-1114.
[15]Hinton G E,Salakhutdinov R R.Reducing the dimensionality of data with neural networks[J].Science,2006,313(5786):504-507.
[16]Hinton G E,Srivastava N,Krizhevsky A,et al.Improving neural networks by preventing co-adaptation of feature detectors[J].arXiv preprint arXiv:1207.0580,2012.
[17]Bengio Y,Lamblin P,Popovici D,et al.Greedy layerwise training of deep networks[C]//NIPS,2007.
[18]Rumelhart D E,Hinton G E,Williams R J.Learning representations by back-propagating errors[J].Nature,1986,323(6088):533.
[19]Hinton G E.A practical guide to training restricted Boltzmann machines[M]//Neural networks:tricks of the trade.Berlin,Heidelberg:Springer,2012:599-619.
[20]Chang S,Han W,Tang J,et al.Heterogeneous network embedding via deep architectures[C]//ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining,2015:119-128.
[21]Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.
[22]Zakzeski J,Bruijnincx P C A,Jongerius A L,et al.The catalytic valorization of lignin for the production of renewable chemicals[J].Chemical Reviews,2010,110(6):3552-3599.
[23]Haklay M,Weber P.OpenStreetMap:user-generated street maps[J].IEEE Pervasive Computing,2008,7(4):12-18.
[24]赵玲,邓敏,王佳璆,等.应用复杂网络理论的城市路网可靠性分析[J].测绘科学,2013,38(3):64-68.
[25]Kunegis J.Konect:the koblenz network collection[C]//Proceedings of the 22nd International Conference on World Wide Web,2013:1343-1350.
[2]Zhao Y,Wu Y J,Levina E,et al.Link prediction for partially observed networks[J].Journal of Computational and Graphical Statistics,2017.
[3]宋海权,郭进,刘刚.基于复杂网络的城市道路重要度评价及路网自动综合方法[J].测绘工程,2017,26(1):8-12.
[4]赵国锋,苑少伟,慈玉生.城市路网的复杂网络特性和鲁棒性研究[J].公路交通科技,2016,33(1):119-124.
[5]Goyal P,Ferrara E.Graph embedding techniques,applications,and performance:a survey[J].Knowledge-Based Systems,2018,151:78-94.
[6]吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39(5):651-661.
[7]Belkin M,Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Advances in Neural Information Processing Systems,2002:585-591.
[8]Grover A,Leskovec J.node2vec:scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining,2016:855-864.
[9]Wang D,Cui P,Zhu W.Structural deep network embedding[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2016:1225-1234.
[10]Ahmed A,Shervashidze N,Narayanamurthy S,et al.Distributed large-scale natural graph factorization[C]//Proceedings of the 22nd international Conference on World Wide Web,2013:37-48.
[11]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.
[12]Lee D.Learning the parts of objects with nonnegative matrix factorization[J].Nature,1999,401(6755):788.
[13]Dan K.A singularly valuable decomposition:the SVDof a matrix[J].College Mathematics Journal,1996,27(1):2-23.
[14]Ou M,Cui P,Pei J,et al.Asymmetric transitivity preserving graph embedding[C]//KDD,2016:1105-1114.
[15]Hinton G E,Salakhutdinov R R.Reducing the dimensionality of data with neural networks[J].Science,2006,313(5786):504-507.
[16]Hinton G E,Srivastava N,Krizhevsky A,et al.Improving neural networks by preventing co-adaptation of feature detectors[J].arXiv preprint arXiv:1207.0580,2012.
[17]Bengio Y,Lamblin P,Popovici D,et al.Greedy layerwise training of deep networks[C]//NIPS,2007.
[18]Rumelhart D E,Hinton G E,Williams R J.Learning representations by back-propagating errors[J].Nature,1986,323(6088):533.
[19]Hinton G E.A practical guide to training restricted Boltzmann machines[M]//Neural networks:tricks of the trade.Berlin,Heidelberg:Springer,2012:599-619.
[20]Chang S,Han W,Tang J,et al.Heterogeneous network embedding via deep architectures[C]//ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining,2015:119-128.
[21]Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.
[22]Zakzeski J,Bruijnincx P C A,Jongerius A L,et al.The catalytic valorization of lignin for the production of renewable chemicals[J].Chemical Reviews,2010,110(6):3552-3599.
[23]Haklay M,Weber P.OpenStreetMap:user-generated street maps[J].IEEE Pervasive Computing,2008,7(4):12-18.
[24]赵玲,邓敏,王佳璆,等.应用复杂网络理论的城市路网可靠性分析[J].测绘科学,2013,38(3):64-68.
[25]Kunegis J.Konect:the koblenz network collection[C]//Proceedings of the 22nd International Conference on World Wide Web,2013:1343-1350.