BGrR:基于粒计算的大规模网络路径的加速方法

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

大规模网络路径问题是社会网络信息处理的基本问题。将粒计算方法引入到大规模网络研究中,结合社会网络分层和社团结构性质建立网络的多粒度层次模型,实现网络的多粒度存储,将大规模网络复杂结构映射到不同粒度空间中。为了降低问题求解的复杂度,将最短路径问题映射到不同粒度空间中,将搜索过程从粗粒度空间向细粒度空间跳转以搜索路径信息,提出基于多粒度空间的最短路径搜索算法(BGrR)来加速大规模网络路径搜索。在实验中,以城市道路交通网络为数据源,通过与A*和ALT方法比较,验证了所提算法的有效性。

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 finding,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.