Research Of Routing Algorithm On Road Networks Based On Overlapping Communities Detecting

The study of complex networks is getting more and more attention; many features of the network are constantly been found and applied to different fields, especially the community structure feature. Based on the theory of community detecting in complex networks, combining the overlapping community with the routing, using the urban road network data, we are further finding that the community has significance to the routing strategy.In many real networks, communities may often overlap, but the majority of community detection algorithms don’t take the overlapping community into account, especially in the hierarchical routing algorithm. Routing on the hierarchical networks can effectively reduce the searching space; reducing the time complexity of the algorithm, with acceptable loss of accuracy.However, there may be overlapping communities on large road networks, affecting the efficient of routing and the optimal results. Therefore, introducing the overlapping communities, finding out the possible overlapping nodes in hierarchical routing algorithm, can improve the reliability of the routing strategy.In this paper, we study the road network routing algorithm based on overlapping community partition. The results showed that by road network community detecting and identifying overlapping communities, we can reduce the complexity of the algorithm. In routing,saving the most effective model for the upper network node, the information in edge node, and using traditional heuristic search algorithm to effective routing, combining multiple USA urban road network data, the proposed algorithm can find the shortest path faster than traditional search algorithms, has more important significance in the road network routing.