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

随着网络规模的不断增大,经典算法(如Dijkstra等)效率越来越低.针对这一问题,研究者们提出了许多近似搜索算法,但如何既能提高搜索效率又能保持准确性一直是一大难点.本文根据复杂网络的结构特性引入区域划分,同时改进树分解的构造,将图构造成一棵树进行搜索,得到了一个新的适合于复杂网络的最短路径近似算法.此外通过实例验证,该算法不仅在一定程度上降低了计算复杂性,而且保持了较高的近似准确性.

Approximate Shortest Path Problem in Complex Networks

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.