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

论文摘要

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

论文目录

• 1 引言
• 2 基本概念
• 3 基于k-shell的最短路径近似算法
•   3.1 信息预处理
•   3.2 最短路径近似搜索
• 4 实验结果与分析
•   4.1 数据集
•   4.2 算法对不同规模真实网络的适用性
•   4.3算法对无标度网络的适用性
• 5 总结

文章来源

类型: 期刊论文

作者: 张昕,严沛,郭阳,王慧慧

关键词: 复杂网络,最短路径,超点聚合,双向搜索树

来源: 计算机工程与应用 2019年14期

年度: 2019

分类: 信息科技,基础科学

专业: 数学,计算机软件及计算机应用

单位: 辽宁大学信息学院

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

分类号: TP301.6;O157.5

页码: 54-60

总页数: 7

文件大小: 1872K

下载量: 300