基于k-shell的复杂网络最短路径近似算法

摘要：

复杂网络最短路径经典算法的处理效率较低,不适用于大规模复杂网络,而现有近似算法通用性有限,且计算准确率不理想,不能满足规模日益扩大的复杂网络中的最短路径计算需求.针对于此,提出基于k-shell的复杂网络最短路径近似算法.算法利用节点的k-shell值进行网络划分并引导搜索路径,利用超点聚合处理k-shell子网来降低路径搜索中节点和连边的规模,通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率.实验结果表明,算法通用性较好,在现实与仿真大规模复杂网络中均具有较高的计算效率和准确率.

关键词：复杂网络、最短路径、k-shell、超点聚合、双向搜索树

所属期刊栏目：55

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金U1811261,61802160;辽宁省博士科研启动基金20170520323;辽宁省公共舆情与网络安全大数据系统工程实验室资助项目2016-294

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

页数：共7页

页码：54-60