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

摘要：

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

关键词：复杂网络、社团连通性、社团发现、层次化、交叠

所属期刊栏目：41

分类号：TP399(计算技术、计算机技术)

资助基金：国家重点基础研究计划”973”计划前期研究专项基金资助项目2008CB317107;教育部博士点专项基金新教师基金资助项目20090162120073

在线出版日期：2011-01-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1834-1840