第33卷第1期 国防科技大学学报 Ⅴol.33No.l 2011年2月 JOURNAL OF NATIONAL UNIVERSITY OF DEFENSE TECHNOLOGY Feb.2011 文章编号:1001-2486(201)01-0047-06 复杂网络社团发现算法研究新进展 骆志刚,丁凡,蒋晓舟,石金龙 (国防科技大学计算机学院,湖南长沙410073) 要:社团结构是复杂网络普遍存在的拓扑特性之一,发现复杂网络中的社团结构是复杂网络研究的 基础性问题。针对非重叠社团发现和重叠社团发现两类问题,全面综述了当前复杂网络社团发现算法研究的 新进展,分析了每类社团发现算法的特点,指出该领域值得进一步探索的研究方向。 关键词:;复杂网络;社团发现算法;重叠社团 中图分类号:TP391文献标识码:A New Progress on Community Detection in Complex Networks LUO Zhi-gang, DING Fan, JIANG Xiaozhou, SHI Jin- College of Computer, National Univ. of Defence Technology, Changsha munity structure is one of the common topological characteristics of complex networks. Community detection has become a fundamental problem in the research field of complex networks. The new progress of current algorithms for community detection was reviewed. The characteristics of these algorithms were discussesed. Finally, future direction of this active area was propo Key words: complex networks; community detection; overlapping commuinty 复杂网络一般指节点众多、连接关系复杂的 1非重叠社团发现算法 网络。由于其灵活普适的描述能力,能够广泛应 用于各科学领域对复杂系统进行建模、分析,近年 非重叠社团发现是指识别出的社团之间互不 来吸引了越来越多的人对其进行研究。随着研究重叠,每个节点有且仅属于一个社团。社团发现 的深入,人们发现许多实际网络均具有社团结构,早期的研究工作大部分都围绕非重叠社团发现展 即整个网络由若干个社团组成,社团之间的连接开,相关综述可参见文献[2-3]。近年来,基于对 相对稀疏、社团内部的连接相对稠密。社团发现社团结构的不同理解,研究者们在对节点集划分 则是利用图拓扑结构中所蕴藏的信息从复杂网络时采用的标准和策略不同,衍生出许多风格迥异 中解析出其模块化的社团结构,该问題的深入研的新算法,典型算法有模块度优化算法、谱分析 究有助于以一种分而治之的方式研究整个网络的法、信息论方法、标号传播方法等。 模块、功能及其演化,更准确地理解复杂系统的组1.1基于模块度优化的社团发现算法 织原则、拓扑结构与动力学特性,具有十分重要的 基于模块度优化的社团发现算法是目前研究 意义。 最多的一类算法,其思想是将社团发现问题定义 自2002年 Girvan和 Newman基于边介数提出为优化问题,然后搜索目标值最优的社团结构 GN算法以来,国际上掀起一股社团发现的研究由 Newman等首先提出的模块度Q值是目前使 热潮,来自生物、物理、计算机等各学科领域的研用最广泛的优化目标,该指标通过比较真实网络 究者们带来了许多新颖的思想和算法,并广泛应中各社团的边密度和随机网络中对应子图的边密 用于各个学科领域的具体问题中。本文在归纳总度之间的差异来度量社团结构的显著性。模块度 结的基础上,从非重叠社团发现和重叠社团发现优化算法根据社团发现时的计算顺序大致可分为 两个方面综述当前社团发现算法的新进展,并展三类。 望该领域未来的一些研究方向。 第一类算法采用聚合思想,自底向上进行,典 收稿日期:2009-11-02 基金项目:国家自然科学基金资助项目(60673018 作者简介:骆志刚(1962—),男,研究员,博士生导师文章编号：１００１－２４８６（２０１１）０１－００４７－０６ 复杂网络社团发现算法研究新进展 骆志刚，丁 凡，蒋晓舟，石金龙 （国防科技大学 计算机学院，湖南 长沙 ４１００７３） 摘 要：社团结构是复杂网络普遍存在的拓扑特性之一，发现复杂网络中的社团结构是复杂网络研究的 基础性问题。针对非重叠社团发现和重叠社团发现两类问题，全面综述了当前复杂网络社团发现算法研究的 新进展，分析了每类社团发现算法的特点，指出该领域值得进一步探索的研究方向。 关键词：复杂网络；社团发现算法；重叠社团 中图分类号：ＴＰ３９１ 文献标识码：Ａ ＮｅｗＰｒｏｇｒｅｓｓｏｎＣｏｍｍｕｎｉｔｙＤｅｔｅｃｔｉｏｎｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ ＬＵＯＺｈｉｇａｎｇ，ＤＩＮＧＦａｎ，ＪＩＡＮＧＸｉａｏｚｈｏｕ，ＳＨＩＪｉｎｌｏｎｇ （ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ，ＮａｔｉｏｎａｌＵｎｉｖ．ｏｆＤｅｆｅｎｃｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｉｓｏｎｅｏｆｔｈｅｃｏｍｍｏｎｔｏｐｏｌｏｇｉｃａｌｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｈａｓ ｂｅｃｏｍｅａｆｕｎｄａｍｅｎｔａｌｐｒｏｂｌｅｍｉｎｔｈｅｒｅｓｅａｒｃｈｆｉｅｌｄｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｔｈｅｎｅｗｐｒｏｇｒｅｓｓｏｆｃｕｒｒｅｎｔａｌｇｏｒｉｔｈｍｓｆｏｒｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎ ｗａｓｒｅｖｉｅｗｅｄ．Ｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｓｅａｌｇｏｒｉｔｈｍｓｗｅｒｅｄｉｓｃｕｓｓｅｓｅｄ．Ｆｉｎａｌｌｙ，ｆｕｔｕｒｅｄｉｒｅｃｔｉｏｎｏｆｔｈｉｓａｃｔｉｖｅａｒｅａｗａｓｐｒｏｐｏｓｅｄ． Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ；ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎ；ｏｖｅｒｌａｐｐｉｎｇｃｏｍｍｕｉｎｔｙ 复杂网络一般指节点众多、连接关系复杂的 网络。由于其灵活普适的描述能力，能够广泛应 用于各科学领域对复杂系统进行建模、分析，近年 来吸引了越来越多的人对其进行研究。随着研究 的深入，人们发现许多实际网络均具有社团结构， 即整个网络由若干个社团组成，社团之间的连接 相对稀疏、社团内部的连接相对稠密。社团发现 则是利用图拓扑结构中所蕴藏的信息从复杂网络 中解析出其模块化的社团结构，该问题的深入研 究有助于以一种分而治之的方式研究整个网络的 模块、功能及其演化，更准确地理解复杂系统的组 织原则、拓扑结构与动力学特性，具有十分重要的 意义。 自 ２００２年 Ｇｉｒｖａｎ和 Ｎｅｗｍａｎ基于边介数提出 ＧＮ算法以来［１］ ，国际上掀起一股社团发现的研究 热潮，来自生物、物理、计算机等各学科领域的研 究者们带来了许多新颖的思想和算法，并广泛应 用于各个学科领域的具体问题中。本文在归纳总 结的基础上，从非重叠社团发现和重叠社团发现 两个方面综述当前社团发现算法的新进展，并展 望该领域未来的一些研究方向。 １ 非重叠社团发现算法 非重叠社团发现是指识别出的社团之间互不 重叠，每个节点有且仅属于一个社团。社团发现 早期的研究工作大部分都围绕非重叠社团发现展 开，相关综述可参见文献［２－３］。近年来，基于对 社团结构的不同理解，研究者们在对节点集划分 时采用的标准和策略不同，衍生出许多风格迥异 的新算法，典型算法有模块度优化算法、谱分析 法、信息论方法、标号传播方法等。 １１ 基于模块度优化的社团发现算法 基于模块度优化的社团发现算法是目前研究 最多的一类算法，其思想是将社团发现问题定义 为优化问题，然后搜索目标值最优的社团结构。 由 Ｎｅｗｍａｎ等［４］ 首先提出的模块度 Ｑ值是目前使 用最广泛的优化目标，该指标通过比较真实网络 中各社团的边密度和随机网络中对应子图的边密 度之间的差异来度量社团结构的显著性。模块度 优化算法根据社团发现时的计算顺序大致可分为 三类。 第一类算法采用聚合思想，自底向上进行，典  收稿日期：２００９－１１－０２ 基金项目：国家自然科学基金资助项目（６０６７３０１８） 作者简介：骆志刚（１９６２—），男，研究员，博士生导师。 第 ３３卷 第 １期 国 防 科 技 大 学 学 报 Ｖｏｌ．３３Ｎｏ．１ ２０１１年 ２月 ＪＯＵＲＮＡＬＯＦＮＡＴＩＯＮＡＬＵＮＩＶＥＲＳＩＴＹＯＦＤＥＦＥＮＳＥＴＥＣＨＮＯＬＯＧＹ Ｆｅｂ． ２０１１