复杂网络社团发现算法研究新进展

《复杂网络社团发现算法研究新进展》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３３卷第１期国防科技大学学报Ｖｏｌ．３３Ｎｏ．１２０１１年２月ＪＯＵＲＮＡＬＯＦＮＡＴＩＯＮＡＬＵＮＩＶＥＲＳＩＴＹＯＦＤＥＦＥＮＳＥＴＥＣＨＮＯＬＯＧＹＦｅｂ．２０１１文章编号：１００１－２４８６（２０１１）０１－００４７－０６复杂网络社团发现算法研究新进展骆志刚，丁凡，蒋晓舟，石金龙（国防科技大学计算机学院，湖南长沙４１００７３）摘要：社团结构是复杂网络普遍存在的拓扑特性之一，发现复杂网络中的社团结构是复杂网络研究的基础性问题。针对非重叠社团发现和重叠社团发现两类问题，全面综述了当前复杂网络社团发现算法研究的新进展，分析了每类社团发现算法的特点，指出该领

2、域值得进一步探索的研究方向。关键词：复杂网络；社团发现算法；重叠社团中图分类号：ＴＰ３９１文献标识码：ＡＮｅｗＰｒｏｇｒｅｓｓｏｎＣｏｍｍｕｎｉｔｙＤｅｔｅｃｔｉｏｎｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓＬＵＯＺｈｉｇａｎｇ，ＤＩＮＧＦａｎ，ＪＩＡＮＧＸｉａｏｚｈｏｕ，ＳＨＩＪｉｎｌｏｎｇ（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ，ＮａｔｉｏｎａｌＵｎｉｖ．ｏｆＤｅｆｅｎｃｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｉｓｏｎｅｏｆｔｈｅｃｏｍｍｏｎｔｏｐｏｌｏｇｉｃａｌｃｈａｒａｃｔｅｒｉｓ

3、ｔｉｃｓｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｈａｓｂｅｃｏｍｅａｆｕｎｄａｍｅｎｔａｌｐｒｏｂｌｅｍｉｎｔｈｅｒｅｓｅａｒｃｈｆｉｅｌｄｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｔｈｅｎｅｗｐｒｏｇｒｅｓｓｏｆｃｕｒｒｅｎｔａｌｇｏｒｉｔｈｍｓｆｏｒｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｗａｓｒｅｖｉｅｗｅｄ．Ｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｓｅａｌｇｏｒｉｔｈｍｓｗｅｒｅｄｉｓｃｕｓｓｅｓｅｄ．Ｆｉｎａｌｌｙ，ｆｕｔｕｒｅｄｉｒｅｃｔｉｏｎｏｆｔｈｉｓａｃｔｉｖｅａｒｅａｗａｓｐｒｏｐｏｓｅｄ．Ｋｅｙｗｏｒｄｓ：ｃｏｍ

4、ｐｌｅｘｎｅｔｗｏｒｋｓ；ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎ；ｏｖｅｒｌａｐｐｉｎｇｃｏｍｍｕｉｎｔｙ复杂网络一般指节点众多、连接关系复杂的１非重叠社团发现算法网络。由于其灵活普适的描述能力，能够广泛应用于各科学领域对复杂系统进行建模、分析，近年非重叠社团发现是指识别出的社团之间互不来吸引了越来越多的人对其进行研究。随着研究重叠，每个节点有且仅属于一个社团。社团发现的深入，人们发现许多实际网络均具有社团结构，早期的研究工作大部分都围绕非重叠社团发现展即整个网络由若干个社团组成，社团之间的连接开，相关综述可参见文献［２－３］。近年来，基于对相对稀疏、社团内部的连

5、接相对稠密。社团发现社团结构的不同理解，研究者们在对节点集划分则是利用图拓扑结构中所蕴藏的信息从复杂网络时采用的标准和策略不同，衍生出许多风格迥异中解析出其模块化的社团结构，该问题的深入研的新算法，典型算法有模块度优化算法、谱分析究有助于以一种分而治之的方式研究整个网络的法、信息论方法、标号传播方法等。模块、功能及其演化，更准确地理解复杂系统的组１１基于模块度优化的社团发现算法织原则、拓扑结构与动力学特性，具有十分重要的基于模块度优化的社团发现算法是目前研究意义。最多的一类算法，其思想是将社团发现问题定义自２００２年Ｇｉｒｖａｎ和Ｎｅｗｍａｎ基于边介数提出为优

6、化问题，然后搜索目标值最优的社团结构。ＧＮ算法以来［１］，国际上掀起一股社团发现的研究［４］由Ｎｅｗｍａｎ等首先提出的模块度Ｑ值是目前使热潮，来自生物、物理、计算机等各学科领域的研用最广泛的优化目标，该指标通过比较真实网络究者们带来了许多新颖的思想和算法，并广泛应中各社团的边密度和随机网络中对应子图的边密用于各个学科领域的具体问题中。本文在归纳总度之间的差异来度量社团结构的显著性。模块度结的基础上，从非重叠社团发现和重叠社团发现优化算法根据社团发现时的计算顺序大致可分为两个方面综述当前社团发现算法的新进展，并展三类。望该领域未来的一些研究方向。第一类算法采用聚合

7、思想，自底向上进行，典收稿日期：２００９－１１－０２基金项目：国家自然科学基金资助项目（６０６７３０１８）作者简介：骆志刚（１９６２—），男，研究员，博士生导师。·４８·国防科技大学学报２０１１年［４］［５］型代表算法有Ｎｅｗｍａｎ快速算法、ＣＮＭ算法团内外连接度的差异时，引入了社团大小作为分［６］和ＭＳＧＭＶ算法等。Ｎｅｗｍａｎ快速算法将每个母进行平均，从理论和数值试验上证明了作为模节点看作是一个社团，每次迭代选择产生最大Ｑ块度Ｄ值要优于Ｑ值。值的两个社团合并，直至整个网络融合成一个社总的来说，模块度优化算法是目前应用最为团。整个过程可表示成一个树状图，从

8、中选择Ｑ广泛的一类算法，