一种发现交叠社团的快速层次化算法

被引：3

作者：

彭佳扬

杨路明

王建新

李敏

蔡娟

机构：

[1] 中南大学信息科学与工程学院

来源：

中南大学学报(自然科学版) | 2010年 / 41卷 / 05期

关键词：

复杂网络; 社团连通性; 社团发现; 层次化; 交叠;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

针对大多数层次聚类算法无法识别实际复杂网络中存在的交叠社区等缺陷,提出1种度量社团间连通性的指标,并在此基础上设计1种发现交叠社团的快速层次化算法F-HOC。F-HOC以社团连通性为依据,用凝聚法对k-团进行弱社团检测、递归合并,以达到网络可交叠层次化快速聚类的目的。采用人们普遍接受的基准随机网络作为标准数据对算法进行测试,并应用该算法对足球网络进行分解。研究结果表明:与目前可以发现交叠社团的层次化算法EAGLE相比,对于社团结构明显的复杂网络,F-HOC具有更大的敏感度和更高的运行效率;随着大规模网络数据的不断增加,EAGLE的运行时间呈指数增长,而F-HOC保持线性增长,F-HOC更适用于大规模的复杂网络。

引用

页码：1834 / 1840

页数：7

共 5 条

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

杨博 ;

刘大有 ;

金弟 ;

马海宾 .

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

[2]

E-Mail as Spectroscopy: Automated Discovery of Community Structure within Organizations[J] . Joshua R. Tyler,Dennis M. Wilkinson,Bernardo A. Huberman.The Information Society . 2005 (2)

[3]

Finding communities in linear time: a physics approach[J] . F. Wu,B. A. Huberman.The European Physical Journal B . 2004 (2)

[4] Detecting community structure in networks [J].

Newman, MEJ .

EUROPEAN PHYSICAL JOURNAL B, 2004, 38 (02) :321-330

[5]

Extracting communities from complex networks by the k-densemethod. Saito K,Yamada T,Kazama K. IEICE Transactions on Fundamentals of Electronics, Communications and ComputerSciences . 2008

← 1 →