第33卷 第1期 2011年 2月国 防 科 技 大 学 学 报
JOURNALOFNATIONALUNIVERSITYOFDEFENSETECHNOLOGYVol.33No.1
Feb. 2011
文章编号:1001-2486(2011)01-0047-06
复杂网络社团发现算法研究新进展
骆志刚,丁 凡,蒋晓舟,石金龙
(国防科技大学计算机学院,湖南长沙 410073)
摘 要:社团结构是复杂网络普遍存在的拓扑特性之一,发现复杂网络中的社团结构是复杂网络研究的基础性问题。针对非重叠社团发现和重叠社团发现两类问题,全面综述了当前复杂网络社团发现算法研究的新进展,分析了每类社团发现算法的特点,指出该领域值得进一步探索的研究方向。
关键词:复杂网络;社团发现算法;重叠社团中图分类号:TP391 文献标识码:A
NewProgressonCommunityDetectioninComplexNetworks
LUOZhi-gang,DINGFan,JIANGXiao-zhou,SHIJin-long
(CollegeofComputer,NationalUniv.ofDefenceTechnology,Changsha410073,China)
Abstract:Communitystructureisoneofthecommontopologicalcharacteristicsofcomplexnetworks.Communitydetectionhasbecomeafundamentalproblemintheresearchfieldofcomplexnetworks.Thenewprogressofcurrentalgorithmsforcommunitydetectionwasreviewed.Thecharacteristicsofthesealgorithmswerediscussesed.Finally,futuredirectionofthisactiveareawasproposed.
Keywords:complexnetworks;communitydetection;overlappingcommuinty
复杂网络一般指节点众多、连接关系复杂的网络。由于其灵活普适的描述能力,能够广泛应用于各科学领域对复杂系统进行建模、分析,近年来吸引了越来越多的人对其进行研究。随着研究的深入,人们发现许多实际网络均具有社团结构,即整个网络由若干个社团组成,社团之间的连接相对稀疏、社团内部的连接相对稠密。社团发现则是利用图拓扑结构中所蕴藏的信息从复杂网络
中解析出其模块化的社团结构,该问题的深入研究有助于以一种分而治之的方式研究整个网络的模块、功能及其演化,更准确地理解复杂系统的组织原则、拓扑结构与动力学特性,具有十分重要的意义。
自2002年Girvan和Newman基于边介数提出GN算法以来,国际上掀起一股社团发现的研究热潮,来自生物、物理、计算机等各学科领域的研究者们带来了许多新颖的思想和算法,并广泛应用于各个学科领域的具体问题中。本文在归纳总结的基础上,从非重叠社团发现和重叠社团发现两个方面综述当前社团发现算法的新进展,并展望该领域未来的一些研究方向。
[1]
1 非重叠社团发现算法
非重叠社团发现是指识别出的社团之间互不
重叠,每个节点有且仅属于一个社团。社团发现早期的研究工作大部分都围绕非重叠社团发现展开,相关综述可参见文献[2-3]。近年来,基于对社团结构的不同理解,研究者们在对节点集划分时采用的标准和策略不同,衍生出许多风格迥异的新算法,典型算法有模块度优化算法、谱分析法、信息论方法、标号传播方法等。1 1 基于模块度优化的社团发现算法
基于模块度优化的社团发现算法是目前研究最多的一类算法,其思想是将社团发现问题定义为优化问题,然后搜索目标值最优的社团结构。
[4]
由Newman等首先提出的模块度Q值是目前使用最广泛的优化目标,该指标通过比较真实网络中各社团的边密度和随机网络中对应子图的边密度之间的差异来度量社团结构的显著性。模块度优化算法根据社团发现时的计算顺序大致可分为三类。
第一类算法采用聚合思想,自底向上进行,典
收稿日期:2009-11-02
基金项目:国家自然科学基金资助项目(60673018)(),男,,
些堡盟塑咝坐坠翌堕匹堡旦墅婴墅望型盟垡塑复杂网络社团发现算法研究新进展‘骆志刚,丁凡,蒋晓舟,石金龙 国防科技大学学报 v01.33No.1 &坠:垫!! 文章...
2011 文章编号: 1001- 2486( 2011) 01- 0047- 06 复杂网络社团发现算法研究新进展骆志刚, 丁凡, 蒋晓舟, 石金龙 410073) ( 国 防科技大学 计算机学院, ...
( 19) : 41774187. 〔 3〕 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究 J〕 . 国防科技大学学报, 2011 , 33 ( 1 ): 4752. 新进展〔 〔 ...
( 19) : 41774187. 〔 3〕 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究 J〕 . 国防科技大学学报, 2011 , 33 ( 1 ): 4752. 新进展〔 〔 ...
张湘莉兰.苑波.骆志刚.Zhang Xianglilan.Yuan Bo....复杂网络中的社团结构算法综述[期刊论文]-电子科技...陈盖凯 基于约束熵的复杂系统重要节点崩溃控制研究[...
张湘莉兰.苑波.骆志刚.Zhang Xianglilan.Yuan Bo....复杂网络中的社团结构算法综述[期刊论文]-电子科技...陈盖凯 基于约束熵的复杂系统重要节点崩溃控制研究[...
热门文档