首页 | 本学科首页   官方微博 | 高级检索  
     

适合复杂网络分析的最短路径近似算法
引用本文:唐晋韬,王挺,王戟.适合复杂网络分析的最短路径近似算法[J].软件学报,2011,22(10):2279-2290.
作者姓名:唐晋韬  王挺  王戟
作者单位:国防科学技术大学计算机学院,湖南长沙,410073
基金项目:国家自然科学基金(60873097); 国家重点基础研究发展计划(973)(2005CB321802); 新世纪优秀人才计划(NCET-06-0926)
摘    要:基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出"无标度"等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.

关 键 词:社会网络  近似算法  网络性质  最短路径问题
收稿时间:2009/8/19 0:00:00
修稿时间:6/9/2010 12:00:00 AM

Shortest Path Approximate Algorithm for Complex Network Analysis
TANG Jin-Tao,WANG Ting and WANG Ji.Shortest Path Approximate Algorithm for Complex Network Analysis[J].Journal of Software,2011,22(10):2279-2290.
Authors:TANG Jin-Tao  WANG Ting and WANG Ji
Affiliation:TANG Jin-Tao,WANG Ting,WANG Ji(College of Computer,National University of Defense Technology,Changsha 410073,China)
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 no...
Keywords:social network  approximation algorithm  network property  shortest path problem  
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号