计算机工程与应用2019，Vol.55Issue(14)：54-60,7.DOI:10.3778/j.issn.1002-8331.1810-0418
基于k-shell的复杂网络最短路径近似算法
K-Shell Shortest Path Approximation Algorithm for Complex Networks
摘要
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 calcu-lation 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.关键词
复杂网络/最短路径/k-shell/超点聚合/双向搜索树Key words
complex network/shortest path/k-shell/super-node aggregation/bi-directional search tree分类
信息技术与安全科学引用本文复制引用
张昕,严沛,郭阳,王慧慧..基于k-shell的复杂网络最短路径近似算法[J].计算机工程与应用,2019,55(14):54-60,7.基金项目
国家自然科学基金(No.U1811261,No.61802160) （No.U1811261,No.61802160）
辽宁省博士科研启动基金(No.20170520323) （No.20170520323）
辽宁省公共舆情与网络安全大数据系统工程实验室资助项目(No.2016-294). （No.2016-294）
