查询结果:   汤天波.Pathfinder算法优化研究[J].计算机应用与软件,2015,32(11):277 - 280.
中文标题
Pathfinder算法优化研究
发表栏目
算法
摘要点击数
680
英文标题
RESEARCH ON PATHFINDER ALGORITHM OPTIMISATION
作 者
汤天波 Tang Tianbo
作者单位
上海市科学学研究所 上海 200235     
英文单位
Shanghai Institute for Science of Science, Shanghai 200235, China     
关键词
复杂网络 可视化 Pathfinder算法 Prim算法
Keywords
Complex networks Visualisation Pathfinder algorithm Prim algorithm
基金项目
作者资料
汤天波,助理研究员,主研领域:大数据分析,知识管理与可视化。 。
文章摘要
Pathfinder算法是复杂网络分析及可视化的重要方法,但现有算法时间复杂度大,难以在大数据环境下广泛应用。提出一种基于Prim算法的Pathfinder优化算法,在求解复杂网络图的最小生成树的过程中,通过距离矩阵计算得到Pathfinder算法的结果图。算法时间复杂度可稳定为O(n2)。实验结果表明,在顶点数为500的稠密网络上,该算法的运行时间有较大的优势。
Abstract
Pathfinder algorithm is an important method for complex network analysis and visualisation. However, the time complexity of existing algorithms is too big to be widely applied in big data environment. We proposed a Prim algorithm-based optimisation of Pathfinder algorithm, which can get the result graph of Pathfinder algorithm by calculating the distance matrix in the process of solving the minimum spanning tree of the complex networks graph. The time complexity of the algorithm can be levelled off to O(n2). Experimental results show that the algorithm has a great advantage in running time on dense networks with vertex number of 500.
下载PDF全文