计算机科学 ›› 2015, Vol. 42 ›› Issue (Z6): 285-289.

• 无线网络与通信 • 上一篇    下一篇

基于重叠社团划分的大规模道路网络双层路由算法

杨旭华,周诗杰   

  1. 浙江工业大学计算机科学与技术学院 杭州310023,浙江工业大学计算机科学与技术学院 杭州310023
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家自然科学基金(61374152)资助

Double Layers Routing Algorithm on Large Road Networks Based on Overlapping Communities Detecting

YANG Xu-hua and ZHOU Shi-jie   

  • Online:2018-11-14 Published:2018-11-14

摘要: 大规模道路网络中的最短路径快速搜索算法在交通系统的导航、交通分配等方面具有广泛的应用。现有的几种分层算法虽然在计算性能上比传统的算法有所改善,但仍存在计算量较大和计算效率较低等问题。提出了基于重叠社团划分的大规模道路网络双层路由算法,该算法在道路网络中探测基于重叠社团的分层结构,将整个网络划分为若干具有重叠节点的社团,并由此构成路网的双层结构:第一层为原始道路网络;第二层为社团连接逻辑层,其中的每一个点对应第一层的一个社团,第一层社团间的重叠节点和道路连接对应第二层节点间的连接。在此网络架构下,路由被分解为第二层社团节点间启发式的总体路由和第一层社团内部节点的局域路由。该算法提出将社团间的重叠节点作为相应两个社团之间的关键路由节点,并将其引入到基于社团的分层路由算法当中,可以有效地降低算法的搜索空间和计算复杂度,有效地提高了算法效率。几个真实城市路网的实验结果表明了本算法的有效性。

Abstract: The fast searching algorithms of shortest path on large road network have wide application in navigation,transportation system,traffic assignment,etc.Although the calculated performance in several existing hierarchical algorithms has been improved,there are still some problems such as heavy computation and low calculation efficiency.By detecting the hierarchical structure based on overlapping communities,we proposed a new hierarchical routing algorithm using overlapping communities.We divided the whole network into communities containing the overlapping nodes and constituted a double-layer structure of road network.The first layer contains the original road network nodes and in the second layer the communities are regarded as nodes,the overlapping nodes and intercommunity edges are regarded as the edges.Based on the network architecture,routing is broken into two processes,the heuristic overall routing in the second layer and local routing in the communities in the first layer.We denoted the overlapping node as the key routing node and used it into the hierarchical algorithms which can reduce the searching space and computational complexity effectively.Several experimental results of the real city road networks show the effectiveness of the algorithm.

Key words: Overlapping community,Double-layer routing,Large road networks

[1] Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische mathematik,1959,1(1):269-271
[2] Hart P E,Nilsson N J,Raphael B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107
[3] Song Q,Wang X.Efficient routing on large road networks using hierarchical communities[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(1):132-140
[4] Geisberger R,Sanders P,Schultes D,et al.Exact routing in large road networks using contraction hierarchies[J].Transportation Science,2012,46(3):388-404
[5] Abraham I,Delling D,Goldberg A V,et al.Hierarchical hub labelings for shortest paths[M]∥Algorithms-ESA 2012.Springer Berlin Heidelberg,2012:24-35
[6] Gubichev A,Bedathur S,Seufert S,et al.Fast and accurate estimation of shortest paths in large graphs[C]∥Proceedings of the 19th ACM International Conference on Information and Knowledge Management.ACM,2010:499-508
[7] Bauer R,Delling D,Sanders P,et al.Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm[J].ACM JEA,2010,15(2/3):1-31
[8] Jin R,Ruan N,Xiang Y,et al.A highway-centric labeling approach for answering distance queries on large sparse graphs[C]∥Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM,2012:445-456
[9] Kriegel H P,Renz M,Schubert M.Route skyline queries:Amulti-preference path planning approach[C]∥2010 IEEE 26th International Conference on Data Engineering(ICDE).IEEE,2010:261-272
[10] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826
[11] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826
[12] Yang J,Leskovec J.Defining and evaluating network communities based on ground-truth[C]∥Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics.ACM,2012:3
[13] Fortunato S,Castellano C.Community structure in graphs[M]∥Computational Complexity.Springer New York,2012:490-512
[14] Mucha P J,Richardson T,Macon K,et al.Community structure in time-dependent,multiscale,and multiplex networks[J].Science,2010,328(5980):876-878
[15] 黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法[J].软件学报,2013,4(9):2062-2077
[16] 付立东,高琳.模块密度谱分的网络社团发现方法[J].西安电子科技大学学报,2010,7(5):916-290
[17] Xie J,Szymanski B K,Liu X.Slpa:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]∥2011 IEEE 11th International Conference on Data Mining Workshops(ICDMW).IEEE,2011:344-349
[18] Havemann F,Heinz M,Struck A,et al.Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels[J].Journal of Statistical Mechanics:Theory and Experiment,2011,2011(1):P01023
[19] 刘玉华,张翼,徐翠,等.一种基于数据场的复杂网络聚类算法[J].计算机科学,2013,0(11):70-73,3
[20] Sun P G,Gao L,Shan Han S.Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks[J].Information Sciences,2011,181(6):1060-1071
[21] 杨博,刘大有,Liu Ji-ming,等.复杂网络聚类方法[J].软件学报,2009,0(1):54-66
[22] 陈端兵,尚明生,李霞.重叠社区发现的两段策略[J].计算机科学,2013,0(1):225-228
[23] Song Q,Wang X.Efficient routing on large road networks using hierarchical communities[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(1):132-140
[24] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,10(10):P10008
[25] Wang X,Jiao L,Wu J.Adjusting from disjoint to overlappingcommunity detection of complex networks[J].Physica A:Statistical Mechanics and its Applications,2009,388(24):5045-5056
[26] http://www.dis.uniroma1.it/challenge9/download.shtml

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!