###
Journal of Software:2011.22(10):2279-2290

适合复杂网络分析的最短路径近似算法
唐晋韬,王挺,王戟
(国防科学技术大学 计算机学院,湖南 长沙 410073)
Shortest Path Approximate Algorithm for Complex Network Analysis
TANG Jin-Tao,WANG Ting,WANG Ji
(College of Computer, National University of Defense Technology, Changsha 410073, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 4202   Download 6051
Received:August 19, 2009    Revised:June 09, 2010
> 中文摘要: 基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出“无标度”等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.
Abstract:The tremendous scale of the social networks mined from Internet is the main obstacle of a social network analysis application. The bottleneck of many network analysis algorithms is the extortionate computational complexity of calculating the shortest path. Real-World networks usually exhibit the same topological features as complex networks such as the “scale-free” and etc, which indicate the intrinsic laws of the shortest paths in complex networks. Based on the topological features of real-world networks, a novel shortest path approximate algorithm which uses an existent short path passing through some local center nodes to estimate the shortest path in complex networks, is proposed. This paper illustrates the advantage and feasibility of incorporating the proposed algorithm within the network properties, which suggests a new idea for complex social network analysis. The proposed algorithm has been evaluated both on synthetic network stage and real world network stage. Experimental results show that the proposed algorithm can largely reduce the computational complexity and remain highly effective in complex networks.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60873097); 国家重点基础研究发展计划(973)(2005CB321802); 新世纪优秀人才计划(NCET- 06-0926) 国家自然科学基金(60873097); 国家重点基础研究发展计划(973)(2005CB321802); 新世纪优秀人才计划(NCET- 06-0926)
Foundation items:
Reference text:

唐晋韬,王挺,王戟.适合复杂网络分析的最短路径近似算法.软件学报,2011,22(10):2279-2290

TANG Jin-Tao,WANG Ting,WANG Ji.Shortest Path Approximate Algorithm for Complex Network Analysis.Journal of Software,2011,22(10):2279-2290