面向大规模道路网的最短路径近似算法
|
摘要
节点重要性对大规模道路网下最短路径的计算有着重要影响。本文提出了顾及节点重要性的最短路径估计方法,该方法基于Critic方法与复杂网络理论评价节点的重要性,结合限制策略实现网络划分,通过层次结构网络的构建,实现大规模道路网数据的有效化简和最短路径的快速有效计算。试验结果表明,该方法能够使中心节点均衡地分布于网络,更好地均衡划分后子网络的规模;随着限制参数的增大,网络规模逐渐降低,查询精度最高达到1.026,相比于单一指标和无限制参数的方法,本文方法显著降低了网络的规模,在最短路径的近似计算上保持了较高的准确性,为大规模复杂网络的近似分析提供分析思路。
Node importance has significant influence on the calculation of shortest path of large-scale road network.A shortest path estimation method based on node importance is proposed in this paper that is suitable for large-scale network.This method integrates the criteria importance though intercrieria correlation(CRITIC)method with complex network theory,with a view to evaluate nodes importance.By combining the restriction strategy to realize network division,the effective simplification of large-scale road network and shortest path estimation are realized through the construction of hierarchical network.The results show that this method can be used to distribute the center nodes evenly,and make little difference in the size of the subnetwork.As the constraint parameter increases,the numbers of nodes and edges reduced gradually,and the query accuracy reached 1.026.Compared with single index and unlimited parameters methods,this paper significantly reduces the size of the network and obtains a high accuracy on the approximate calculation of the shortest path.These will provide a new way of thinking for approximate analysis of large-scale complex networks.
Node importance has significant influence on the calculation of shortest path of large-scale road network.A shortest path estimation method based on node importance is proposed in this paper that is suitable for large-scale network.This method integrates the criteria importance though intercrieria correlation(CRITIC)method with complex network theory,with a view to evaluate nodes importance.By combining the restriction strategy to realize network division,the effective simplification of large-scale road network and shortest path estimation are realized through the construction of hierarchical network.The results show that this method can be used to distribute the center nodes evenly,and make little difference in the size of the subnetwork.As the constraint parameter increases,the numbers of nodes and edges reduced gradually,and the query accuracy reached 1.026.Compared with single index and unlimited parameters methods,this paper significantly reduces the size of the network and obtains a high accuracy on the approximate calculation of the shortest path.These will provide a new way of thinking for approximate analysis of large-scale complex networks.
引文
[1] BOVY P H L,STERN E.Route choice:wayfinding in transport networks[M].Alphen,Netherlands:Kluwer Academic Publishers,2012.
[2]宋青.大规模网络最短路径的分层优化算法研究[D].上海:上海交通大学,2012.SONG Qing.Research on hierarchical shortest path algorithms for large-scale networks[D].Shanghai:Shanghai Jiao Tong University,2012.
[3] MIHALAK M,RAMEK R,WIDMAYER P.Approximately counting approximately-shortest paths in directed acyclic graphs[J].Theory of Computing Systems,2016,58(1):45-59.
[4] MAUE J,SANDERS P,MATIJEVIC D.Goal directed shortest path queries using precomputed cluster distances[C]∥Proceedings of 2006International Workshop on Experimental and Efficient Algorithms.Berlin:Springer,2006:316-327.
[5] GOLDBERG A V,WERNECK R F.Computing point-topoint shortest paths from external memory[C]∥Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics.Vancouver:SIAM,2005,:26-40.
[6] IDWAN S,ETAIWI W.Computing breadth first search in large graph using hMetis partitioning[J].European Journal of Scientific Research,2009,29(2):215-221.
[7] QIAO Miao.Query processing in large-scale networks[D].Hong Kong:The Chinese University of Hong Kong,2013.
[8] POTAMIAS M,BONCHI F,CASTILLO C,et al.Fast shortest path distance estimation in large networks[C]∥Proceedings of the 18th ACM Conference on Information and Knowledge Management.Hong Kong,China:ACM,2009:867-876.
[9] KRIEGEL H P,KRGER P,RENZ M,et al.Hierarchical graph embedding for efficient query processing in very large traffic networks[M]∥Scientific and Statistical Database Management.Berlin:Springer,2008:150-167.
[10] KLEINBERG J,SLIVKINS A,WEXLER T.Triangulation and embedding using small sets of beacons[C]∥Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science.Rome,Italy:IEEE Computer Society,2004:444-453.
[11] FRANCIS P,JAMIN S,JIN Cheng,et al.IDMaps:a global internet host distance estimation service[J].IEEE/ACM Transactions on Networking,2001,9(5):525-540.
[12] WANG Shibo,ZHAO Jinlou.Multi-attribute integrated measurement of node importance in complex networks[J].Chaos,2015,25(11):113105.
[13]于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013,62(2):54-62.YU Hui,LIU Zun,LI Yongjun.Key nodes in complex networks identified by multi-attribute decision-making method[J].Acta Physica Sinica,2013,62(2):54-62.
[14] FREEMAN L C.Centrality in social networks conceptual clarification[J].Social Networks,1978,1(3):215-239.
[15] BRANDES U.A faster algorithm for betweenness centrality[J].Journal of Mathematical Sociology,2001,25(2):163-177.
[16] BAVELAS A.Communication patterns in task-oriented groups[J].Journal of the Acoustical Society of America,1950,22(6):725-730.
[17] WATTS D J,STROGATZ S H.Collective dynamics of‘small-world’networks[J].Nature,1998,393(6684):440-442.
[18] BONACICH P.Some unique properties of eigenvector centrality[J].Social Networks,2007,29(4):555-564.
[19]刘刚,李永树,杨骏,等.对偶图节点重要度的道路网自动选取方法[J].测绘学报,2014,43(1):97-104.DOI:10.13485/j.cnki.11-2089.2014.0014.LIU Gang,LI Yongshu,YANG Jun,et al.Auto-selection method of road networks based on evaluation of node importance for dual graph[J].Acta Geodaetica et Cartographica Sinica,2014,43(1):97-104.DOI:10.13485/j.cnki.11-2089.2014.0014.
[20] YANG Yunyun,XIE Gang,XIE Jun.Mining important nodes in directed weighted complex networks[J].Discrete Dynamics in Nature and Society,2017(5):1-7.
[21]栾学晨,杨必胜,张云菲.城市道路复杂网络结构化等级分析[J].武汉大学学报(信息科学版),2012,37(6):728-732.LUAN Xuechen, YANG Bisheng, ZHANG Yunfei.Structural hierarchy analysis of streets based on complex network theory[J].Geomatics and Information Science of Wuhan University,2012,37(6):728-732.
[22]李清泉,曾喆,杨必胜,等.城市道路网络的中介中心性分析[J].武汉大学学报(信息科学版),2010,35(1):37-41.LI Qingquan,ZENG Zhe,YANG Bisheng,et al.Betweenness centrality analysis for urban road networks[J].Geomatics and Information Science of Wuhan University,2010,35(1):37-41.
[23] DIAKOULAKI D,MAVROTAS G,PAPAYANNAKIS L,et al.Determining objective weights in multiple criteria problems:the CRITIC method[J].Computers&Operations Research,1995,22(7):763-770.
[24]唐晋韬,王挺,王戟.适合复杂网络分析的最短路径近似算法[J].软件学报,2011,22(10):2279-2290.TANG Jintao,WANG Ting,WANG Ji.Shortest path approximate algorithm for complex network analysis[J].Journal of Software,2011,22(10):2279-2290.
[25] DIJKSTRA E W.A note on Two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.
[26]陆锋.最短路径算法:分类体系与研究进展[J].测绘学报,2001,30(3):269-275.LU Feng.Shortest path algorithms:taxonomy and advance in research[J].Acta Geodaetica et Cartographica Sinica,2001,30(3):269-275.
[27] LI Qingquan,CHEN Biyu,WANG Yafei,et al.A hybrid link-node approach for finding shortest paths in road networks with turn restrictions[J].Transactions in GIS,2015,19(27):3059-3068.
[2]宋青.大规模网络最短路径的分层优化算法研究[D].上海:上海交通大学,2012.SONG Qing.Research on hierarchical shortest path algorithms for large-scale networks[D].Shanghai:Shanghai Jiao Tong University,2012.
[3] MIHALAK M,RAMEK R,WIDMAYER P.Approximately counting approximately-shortest paths in directed acyclic graphs[J].Theory of Computing Systems,2016,58(1):45-59.
[4] MAUE J,SANDERS P,MATIJEVIC D.Goal directed shortest path queries using precomputed cluster distances[C]∥Proceedings of 2006International Workshop on Experimental and Efficient Algorithms.Berlin:Springer,2006:316-327.
[5] GOLDBERG A V,WERNECK R F.Computing point-topoint shortest paths from external memory[C]∥Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics.Vancouver:SIAM,2005,:26-40.
[6] IDWAN S,ETAIWI W.Computing breadth first search in large graph using hMetis partitioning[J].European Journal of Scientific Research,2009,29(2):215-221.
[7] QIAO Miao.Query processing in large-scale networks[D].Hong Kong:The Chinese University of Hong Kong,2013.
[8] POTAMIAS M,BONCHI F,CASTILLO C,et al.Fast shortest path distance estimation in large networks[C]∥Proceedings of the 18th ACM Conference on Information and Knowledge Management.Hong Kong,China:ACM,2009:867-876.
[9] KRIEGEL H P,KRGER P,RENZ M,et al.Hierarchical graph embedding for efficient query processing in very large traffic networks[M]∥Scientific and Statistical Database Management.Berlin:Springer,2008:150-167.
[10] KLEINBERG J,SLIVKINS A,WEXLER T.Triangulation and embedding using small sets of beacons[C]∥Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science.Rome,Italy:IEEE Computer Society,2004:444-453.
[11] FRANCIS P,JAMIN S,JIN Cheng,et al.IDMaps:a global internet host distance estimation service[J].IEEE/ACM Transactions on Networking,2001,9(5):525-540.
[12] WANG Shibo,ZHAO Jinlou.Multi-attribute integrated measurement of node importance in complex networks[J].Chaos,2015,25(11):113105.
[13]于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013,62(2):54-62.YU Hui,LIU Zun,LI Yongjun.Key nodes in complex networks identified by multi-attribute decision-making method[J].Acta Physica Sinica,2013,62(2):54-62.
[14] FREEMAN L C.Centrality in social networks conceptual clarification[J].Social Networks,1978,1(3):215-239.
[15] BRANDES U.A faster algorithm for betweenness centrality[J].Journal of Mathematical Sociology,2001,25(2):163-177.
[16] BAVELAS A.Communication patterns in task-oriented groups[J].Journal of the Acoustical Society of America,1950,22(6):725-730.
[17] WATTS D J,STROGATZ S H.Collective dynamics of‘small-world’networks[J].Nature,1998,393(6684):440-442.
[18] BONACICH P.Some unique properties of eigenvector centrality[J].Social Networks,2007,29(4):555-564.
[19]刘刚,李永树,杨骏,等.对偶图节点重要度的道路网自动选取方法[J].测绘学报,2014,43(1):97-104.DOI:10.13485/j.cnki.11-2089.2014.0014.LIU Gang,LI Yongshu,YANG Jun,et al.Auto-selection method of road networks based on evaluation of node importance for dual graph[J].Acta Geodaetica et Cartographica Sinica,2014,43(1):97-104.DOI:10.13485/j.cnki.11-2089.2014.0014.
[20] YANG Yunyun,XIE Gang,XIE Jun.Mining important nodes in directed weighted complex networks[J].Discrete Dynamics in Nature and Society,2017(5):1-7.
[21]栾学晨,杨必胜,张云菲.城市道路复杂网络结构化等级分析[J].武汉大学学报(信息科学版),2012,37(6):728-732.LUAN Xuechen, YANG Bisheng, ZHANG Yunfei.Structural hierarchy analysis of streets based on complex network theory[J].Geomatics and Information Science of Wuhan University,2012,37(6):728-732.
[22]李清泉,曾喆,杨必胜,等.城市道路网络的中介中心性分析[J].武汉大学学报(信息科学版),2010,35(1):37-41.LI Qingquan,ZENG Zhe,YANG Bisheng,et al.Betweenness centrality analysis for urban road networks[J].Geomatics and Information Science of Wuhan University,2010,35(1):37-41.
[23] DIAKOULAKI D,MAVROTAS G,PAPAYANNAKIS L,et al.Determining objective weights in multiple criteria problems:the CRITIC method[J].Computers&Operations Research,1995,22(7):763-770.
[24]唐晋韬,王挺,王戟.适合复杂网络分析的最短路径近似算法[J].软件学报,2011,22(10):2279-2290.TANG Jintao,WANG Ting,WANG Ji.Shortest path approximate algorithm for complex network analysis[J].Journal of Software,2011,22(10):2279-2290.
[25] DIJKSTRA E W.A note on Two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.
[26]陆锋.最短路径算法:分类体系与研究进展[J].测绘学报,2001,30(3):269-275.LU Feng.Shortest path algorithms:taxonomy and advance in research[J].Acta Geodaetica et Cartographica Sinica,2001,30(3):269-275.
[27] LI Qingquan,CHEN Biyu,WANG Yafei,et al.A hybrid link-node approach for finding shortest paths in road networks with turn restrictions[J].Transactions in GIS,2015,19(27):3059-3068.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |