适合复杂网络分析的最短路径近似算法

• 作者: 唐晋韬 王戟 王挺
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 社会网络 近似算法 网络性质 最短路径问题
• 年，卷（期）: 2011,（10）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 2279-2290
• 分类号: TP301
• 字数: 11904字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03924

摘要

基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出“无标度”等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王戟	国防科学技术大学计算机学院	44	1257	17.0	35.0
2	王挺	国防科学技术大学计算机学院	34	445	12.0	20.0
3	唐晋韬	国防科学技术大学计算机学院	10	134	6.0	10.0