| 基于k-shell的复杂网络最短路径近似算法 |
| |
| 引用本文： | 张昕,严沛,郭阳,王慧慧.基于k-shell的复杂网络最短路径近似算法[J].计算机工程与应用,2019,55(14):54-60. |
| |
| 作者姓名： | 张昕 严沛 郭阳 王慧慧 |
| |
| 作者单位： | 辽宁大学 信息学院,沈阳,110036;辽宁大学 信息学院,沈阳,110036;辽宁大学 信息学院,沈阳,110036;辽宁大学 信息学院,沈阳,110036 |
| |
| 基金项目： | 国家自然科学基金;辽宁省博士科研启动基金;辽宁省公共舆情与网络安全大数据系统工程实验室资助项目 |
| |
| 摘 要： | 复杂网络最短路径经典算法的处理效率较低，不适用于大规模复杂网络，而现有近似算法通用性有限，且计算准确率不理想，不能满足规模日益扩大的复杂网络中的最短路径计算需求。针对于此，提出基于k]-shell的复杂网络最短路径近似算法。算法利用节点的k]-shell值进行网络划分并引导搜索路径，利用超点聚合处理k]-shell子网来降低路径搜索中节点和连边的规模，通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率。实验结果表明，算法通用性较好，在现实与仿真大规模复杂网络中均具有较高的计算效率和准确率。
|
| 关 键 词： | 复杂网络 最短路径 k-shell 超点聚合 双向搜索树 |
K-Shell Shortest Path Approximation Algorithm for Complex Networks |
| |
| ZHANG Xin,YAN Pei,GUO Yang,WANG Huihui.K-Shell Shortest Path Approximation Algorithm for Complex Networks[J].Computer Engineering and Applications,2019,55(14):54-60. |
| |
| Authors: | ZHANG Xin YAN Pei GUO Yang WANG Huihui |
| |
| Affiliation: | College of Information, Liaoning University, Shenyang 110036, China |
| |
| Abstract: | The processing efficiency of classical shortest path algorithms for complex networks is not suitable for large-scale complex networks, moreover, the existing approximation algorithms are limited in generality and accuracy of calculation for increasing scale of complex networks. K]-shell shortest path approximation algorithm for complex networks is proposed to solve the above problem. The k]-shell value of nodes is used to divide the network and guide the search path, the k]-shell sub-net is processed by super-node aggregation to reduce the size of nodes and edges in the path search, and the computational efficiency and accuracy of the algorithm are improved by using the bi-directional search tree in the path search process. Experimental results show that the algorithm has better generality and higher computational efficiency and accuracy in real and simulated large-scale complex networks. |
| |
| Keywords: | complex network shortest path [k]-shell super-node aggregation bi-directional search tree |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
