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

摘要：

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

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

所属期刊栏目：25

分类号：TP3;O1

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

在线出版日期：2016-06-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：107-112