复杂网络中近似最短路径问题  

Approximate Shortest Path Problem in Complex Networks

作　　者：刘微[1] 肖华勇[1] 

机构地区：[1]西北工业大学理学院,西安710072

出　　处：《计算机系统应用》2016年第5期107-112,共6页Computer Systems & Applications

基　　金：国家磁约束核聚变能发展专项

摘　　要：随着网络规模的不断增大,经典算法(如Dijkstra等)效率越来越低.针对这一问题,研究者们提出了许多近似搜索算法,但如何既能提高搜索效率又能保持准确性一直是一大难点.本文根据复杂网络的结构特性引入区域划分,同时改进树分解的构造,将图构造成一棵树进行搜索,得到了一个新的适合于复杂网络的最短路径近似算法.此外通过实例验证,该算法不仅在一定程度上降低了计算复杂性,而且保持了较高的近似准确性.With the increasing of data in complex networks, the efficiency of classic algorithms such as Dijkstra algorithm is very low. To solve this problem, the researchers put forward a number of approximate search algorithms, but how to reduce the computational complexity and also keep the accuracy has been a big difficulty. According to the structural characteristics of complex networks, this article introduces regional division, improves the structure of the tree decomposition, and constructs graph into a tree to search the target vertex, getting a new the shortest path approximate algorithm for complex networks. In addition, the proposed algorithm not only reduces the computational complexity but also remains the high accuracy of approximation by examples.

关 键 词：复杂网络 树分解 树宽 树 最短路径近似算法 

分 类 号：O157.5[理学—数学]