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

被引：40

作者：

唐晋韬

王挺

王戟

机构：

[1] 国防科学技术大学计算机学院

来源：

软件学报 | 2011年 / 22卷 / 10期

关键词：

社会网络; 近似算法; 网络性质; 最短路径问题;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：2279 / 2290

页数：12

共 16 条

[1] 复杂网络聚类方法 [J].

杨博 ;

刘大有 ;

金弟 ;

马海宾 .

软件学报, 2009, 20 (01) :54-66

[2] 复杂动力网络及其在软件工程中的应用 [J].

吕金虎 ;

王红春 ;

何克清 .

计算机研究与发展, 2008, (12) :2052-2059

[3] 基于个性特征仿真邮件分析系统挖掘犯罪网络核心 [J].

乔少杰 ;

唐常杰 ;

彭京 ;

刘威 ;

温粉莲 ;

邱江涛 .

计算机学报, 2008, (10) :1795-1803

[4] 基于社会网络可视化分析的数据挖掘(英文) [J].

杨育彬 ;

李宁 ;

张瑶 .

软件学报, 2008, (08) :1980-1994

[5] Internet网络的访问直径分析 [J].

徐野 ;

赵海 ;

苏威积 ;

张文波 ;

张昕 .

计算机学报, 2006, (05) :690-698

[6] Distance estimation and object location via rings of neighbors [J].

Slivkins, Aleksandrs .

DISTRIBUTED COMPUTING, 2007, 19 (04) :313-333

[7] COMPLEX NETWORKS [J].

Holovatch, Yu. ;

Olemskoi, O. ;

von Ferber, C. ;

Holovatch, T. ;

Mryglod, O. ;

Olemskoi, I. ;

Palchykov, V. .

JOURNAL OF PHYSICAL STUDIES, 2006, 10 (04) :247-289

[8] Approximate distance oracles [J].

Thorup, M ;

Zwick, U .

JOURNAL OF THE ACM, 2005, 52 (01) :1-24

[9]

Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks[J] . Peter S. Bearman,James Moody,Katherine Stovel.American Journal of Sociology . 2004 (1)

[10] All-pairs small-stretch paths [J].

Cohen, E ;

Zwick, U .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 38 (02) :335-353

← 1 2 →