Computer Science ›› 2014, Vol. 41 ›› Issue (11): 265-268.doi: 10.11896/j.issn.1002-137X.2014.11.051

Previous Articles     Next Articles

BGrR:Large-scale Network Routing Speedup Techniques Based on Granular Computing

HE Fu-gui,LIU Ren-jin,ZHANG Yan-ping and ZHANG Ling   

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

Abstract: Large-scale network routing is one of the fundamental problems in social network information processing.A granular analysis method of network based on granular computing was put forward.From basic problems of granular computing,using hierarchy topology and community structure of social network,this paper studied how to select grain of network and how to deal with problems among different granular spaces.By hierarchical granular chain,complex and large-scale network was mapped into different granular spaces.To reduce complexity of problem solving,network routing problem was mapped into different granular spaces. Throught the change of searching process from coarse granular space to fine granular space,network routing problem was solved.In order to speedup large-scale network routing fin-ding,a Between-Granular Routing Algorithm(BGrR) was put forward.In experiment,using urban road network as data source,the proposed method was compared with other heuristic searching path methods (A* and ALT ).The result of experiments shows that the proposed method is effective.

Key words: Granular computing,Network structure analysis,Shortest path

[1] 李国杰.大数据研究的科学价值[J].中国计算机学会通讯,2012,8(9):8-15
[2] Zadeh L.Fuzzy logic equals computing with words[J].IEEEtransactions on Fuzzy Systems,1996,4(2):103-111
[3] Zadeh L.Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J].Fuzzy Sets and System,1997,0(2):111-127
[4] Zadeh L.Some reflections on soft computing,granular computing and their roles in the conception,design and utilization of information/intelligent systems[J].Soft computing,1998,2(1):23-25
[5] Zadeh L.A new direction in AI-Toward a computational theory of perceptions[J].Artificial Intelligence Magazine,2001,2(1):73-84
[6] Granularity H J R.Proceedings of IJCAI[C]∥Los Angeles.1985:432-435
[7] Yager R R,Filev D.Operations for granularity computing:mixing words with numbers[C]∥Proceedings of 1998 IEEE International conference on Fuzzy Systems.1998:123-128
[8] Zhang B,Zhang L.Theory and applications of problem solving[M].North-Holland:Elsevier science publishers,1992
[9] 鲍培明.距离寻优中Dijkstra算法的优化[J].计算机研究与发展,2001,38(3):307-311
[10] 周培德.交通道路网中任意两点之间最短路径的快速算法[J].计算机研究与发展,2004,24(2):35-37
[11] Goldberg A V,Harrelson C.Computing the Shortest Path :A* Search Meets Graph Theory[R].Vancouver,2004
[12] Subramani K,Madduri K.Two-level heaps:a new priority queue structure with applications to the single source shortest path problem[C]∥Third International Conference of COCOA 2009.2009:186-196
[13] 宋青,汪小帆.最短路径算法加速技术研究综述[J].电子科技大学学报,2012,1(2):176-184
[14] Goldberg A V.Point-to-Point Shortest Path Algorithms withPreprocessing[C]∥Theory and Practice of Computer Science Lecture Notes in Computer Science.volume 4362,2007:88-102
[15] Maue J,Sanders P,Matijevic D.Goal-Directed Shortest-PathQueries Using Precomputed Cluster Distances[J].ACM Journal of Experimental Algorithmics,2009,14(3):1-27
[16] Goldberg A V.Reach for A*:Efficient Point-to-Point Shortest Path Algorithms[C]∥SIAM Workshop on Algorithms Engineering and Experimentation (ALENEX 06).2006:129-143
[17] Pochter N,Zohar A,Rosenschein J S,et al.Search Space Reduction Using Swamp Hierarchies[C]∥Twenty-Fourth AAAI Conference on Artificial Intelligence.2010:155-160
[18] Sanders P,Schultes D.Highway hierarchies hasten exact shortest path queries[C]∥European Symposium on Algorithms.2005:568-579
[19] Sanders P,Schultes D.Engineering Highway Hierarchies[C]∥the 14th European Symposium on Algorithms(ESA 2006).2006:804-816
[20] Song Qing,Wang Xiao-fan.Efficient routing on large road networks using hierarchical communities[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(1):132-140
[21] Wagner D,Willhalm T,Zaroliagis C D.Geometric containers for efficient shortest-path computation[J].ACM Journal of Expe-rimental Algorithmics,2005,10:1-3 (下转第281页)(上接第268页)
[22] Mohring R H,Schilling H,Schutz B,et al.Partitioning graphs to speedup dijkstra’s algorithm[J].Experimental and Efficient Algorithmics,2005,3503:189-202
[23] Bast H,Funke S,Matijevic D.TRANSIT:Ultrafast Shortest-Path Queries with Linear-Time Preprocessing[C]∥Proc.of Proc.9th DIMACS Implementation Challenge.2006:1-13
[24] Bauer R,Delling D.Sharc:Fast and robust unidirectional routing[J].ACM Journal of Experimental Algorithmics,2009,14(4)
[25] Botea A.Improving AI Planning and Search with Automatic Abstraction[D].Canada: University of Alberta,Edmonton,2006
[26] Kishimoto A,Fukunaga A,Botea A.On the scaling behavior of hda*[C]∥Proceedings of the Third Annual Symposium on Combinatorial Search SoCS-2010.Stone Mountain,Atlanta,GA,USA,2010
[27] Car A.Hierarchical Spatial Reasoning:Theoretical Considera-tion and Its Application to Modeling Way Finding[D].Vienna:Department of Geo-information,Technical University of Vienna,1997
[28] 李楷,钟耳顺,曾志明,等.基于分层网络拓扑结构的最优路径算法[J].中国图象图形学报,2006,11(7):1004-1009
[29] 陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报,2000,25(3):226-232
[30] 翁敏,毋河海,李林燕.层次空间推理的机制及其在路径寻找方面的应用[J].测绘科学,2006,31(5):119-121
[31] Weng S J M,Qu R.Hierarchical spatial reasoning and case of way-finding[J].Geo-spatial Information Science,2008,11(4):269-272
[32] Zhang Ling,He Fu-gui,Zhang Yan-ping,et al.A New Algo-rithm for Optimal Path Finding in Complex Networks Based on the Quotient Space[J].Fundamenta Informaticae,2009,93(4):459-469
[33] 张燕平,罗斌,姚一豫,等.商空间与粒计算:结构化问题求解理论与方法[M].北京:科学出版社,2010
[34] He Fu-gui,Zhang Yan-ping,Zhao Shu,et al.Computing thePoint-to-Point Shortest Path:Quotient Space Theory’s Application in Complex Network[C]∥Yu J,et al.,eds.RSKT 2010,LNAI 6401.Springer,Heidelberg,2010:751-758
[35] He Fu-gui,Zhang Yan-ping,Chen Jie,et al.Path Queries onMassive Graphs Based on Multi-granular Graph Partitioning[C]∥Yao J T,et al.,eds.RSKT 2011,LNCS 6954.Springer,Heidelberg,2011:569-578
[36] 汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006
[37] Watts D J,Strogatz S H.Collective dynamics of small world networks[J].Nature,1998,3(4):440-442
[38] Barabási AL,Albert R.Emergence of scaling in random networks[J].Science,1999,6(5439):509-512
[39] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proc.of the National Academy of Sciences of the Uni-ted States of America,2002,9(12):7821-7826
[40] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,9(2):026113
[41] Newman M E J.Modularity and community structure in net-works[J]Proc.of the National Academy of Sciences of the Uni-ted States of America,2006,3(23):8577-8582
[42] Wang L,Dai G Z.Community finding in complex networks:theo-ry and applications[J].Science & Technology Review,2005,3(8):62-66
[43] Bellman R.On a routing problem[J].Quarterly of Applied Mathematics,1958,16(1):87-90
[44] Hai Zhu-ge,Zhang Jun-sheng.Topological centrality and its e-Science applications[J].JASIST,2010,1(9):1824-1841
[45] 淦文燕,赫南,李德毅,等.一种基于拓扑势的网络社区发现方法[J].软件学报,2009,20(8):2241-2254

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!