摘要
随着网络规模的不断增大,经典算法(如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.
出处
《计算机系统应用》
2016年第5期107-112,共6页
Computer Systems & Applications
基金
国家磁约束核聚变能发展专项
关键词
复杂网络
树分解
树宽
树
最短路径近似算法
complex network
tree decomposition
tree-width
tree
shortest path approximate algorithm
