第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—),男,研究员,博士生导师
文章编号：１００１－２４８６（２０１１）０１－００４７－０６ 复杂网络社团发现算法研究新进展 骆志刚，丁 凡，蒋晓舟，石金龙 （国防科技大学 计算机学院，湖南 长沙 ４１００７３） 摘 要：社团结构是复杂网络普遍存在的拓扑特性之一，发现复杂网络中的社团结构是复杂网络研究的 基础性问题。针对非重叠社团发现和重叠社团发现两类问题，全面综述了当前复杂网络社团发现算法研究的 新进展，分析了每类社团发现算法的特点，指出该领域值得进一步探索的研究方向。 关键词：复杂网络；社团发现算法；重叠社团 中图分类号：ＴＰ３９１ 文献标识码：Ａ ＮｅｗＰｒｏｇｒｅｓｓｏｎＣｏｍｍｕｎｉｔｙＤｅｔｅｃｔｉｏｎｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ ＬＵＯＺｈｉｇａｎｇ，ＤＩＮＧＦａｎ，ＪＩＡＮＧＸｉａｏｚｈｏｕ，ＳＨＩＪｉｎｌｏｎｇ （ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ，ＮａｔｉｏｎａｌＵｎｉｖ．ｏｆＤｅｆｅｎｃｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｉｓｏｎｅｏｆｔｈｅｃｏｍｍｏｎｔｏｐｏｌｏｇｉｃａｌｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｈａｓ ｂｅｃｏｍｅａｆｕｎｄａｍｅｎｔａｌｐｒｏｂｌｅｍｉｎｔｈｅｒｅｓｅａｒｃｈｆｉｅｌｄｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｔｈｅｎｅｗｐｒｏｇｒｅｓｓｏｆｃｕｒｒｅｎｔａｌｇｏｒｉｔｈｍｓｆｏｒｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎ ｗａｓｒｅｖｉｅｗｅｄ．Ｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｓｅａｌｇｏｒｉｔｈｍｓｗｅｒｅｄｉｓｃｕｓｓｅｓｅｄ．Ｆｉｎａｌｌｙ，ｆｕｔｕｒｅｄｉｒｅｃｔｉｏｎｏｆｔｈｉｓａｃｔｉｖｅａｒｅａｗａｓｐｒｏｐｏｓｅｄ． Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ；ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎ；ｏｖｅｒｌａｐｐｉｎｇｃｏｍｍｕｉｎｔｙ 复杂网络一般指节点众多、连接关系复杂的 网络。由于其灵活普适的描述能力，能够广泛应 用于各科学领域对复杂系统进行建模、分析，近年 来吸引了越来越多的人对其进行研究。随着研究 的深入，人们发现许多实际网络均具有社团结构， 即整个网络由若干个社团组成，社团之间的连接 相对稀疏、社团内部的连接相对稠密。社团发现 则是利用图拓扑结构中所蕴藏的信息从复杂网络 中解析出其模块化的社团结构，该问题的深入研 究有助于以一种分而治之的方式研究整个网络的 模块、功能及其演化，更准确地理解复杂系统的组 织原则、拓扑结构与动力学特性，具有十分重要的 意义。 自 ２００２年 Ｇｉｒｖａｎ和 Ｎｅｗｍａｎ基于边介数提出 ＧＮ算法以来［１］ ，国际上掀起一股社团发现的研究 热潮，来自生物、物理、计算机等各学科领域的研 究者们带来了许多新颖的思想和算法，并广泛应 用于各个学科领域的具体问题中。本文在归纳总 结的基础上，从非重叠社团发现和重叠社团发现 两个方面综述当前社团发现算法的新进展，并展 望该领域未来的一些研究方向。 １ 非重叠社团发现算法 非重叠社团发现是指识别出的社团之间互不 重叠，每个节点有且仅属于一个社团。社团发现 早期的研究工作大部分都围绕非重叠社团发现展 开，相关综述可参见文献［２－３］。近年来，基于对 社团结构的不同理解，研究者们在对节点集划分 时采用的标准和策略不同，衍生出许多风格迥异 的新算法，典型算法有模块度优化算法、谱分析 法、信息论方法、标号传播方法等。 １１ 基于模块度优化的社团发现算法 基于模块度优化的社团发现算法是目前研究 最多的一类算法，其思想是将社团发现问题定义 为优化问题，然后搜索目标值最优的社团结构。 由 Ｎｅｗｍａｎ等［４］ 首先提出的模块度 Ｑ值是目前使 用最广泛的优化目标，该指标通过比较真实网络 中各社团的边密度和随机网络中对应子图的边密 度之间的差异来度量社团结构的显著性。模块度 优化算法根据社团发现时的计算顺序大致可分为 三类。 第一类算法采用聚合思想，自底向上进行，典 收稿日期：２００９－１１－０２ 基金项目：国家自然科学基金资助项目（６０６７３０１８） 作者简介：骆志刚（１９６２—），男，研究员，博士生导师。 第 ３３卷 第 １期 国 防 科 技 大 学 学 报 Ｖｏｌ．３３Ｎｏ．１ ２０１１年 ２月 ＪＯＵＲＮＡＬＯＦＮＡＴＩＯＮＡＬＵＮＩＶＥＲＳＩＴＹＯＦＤＥＦＥＮＳＥＴＥＣＨＮＯＬＯＧＹ Ｆｅｂ． ２０１１
国防科技大学学报 011年 型代表算法有 Newman快速算法、CNM算法团内外连接度的差异时,引入了社团大小作为分 和MSG-Mv算法等。 Newman快速算法将每个母进行平均,从理论和数值试验上证明了作为模 节点看作是一个社团,每次迭代选择产生最大Q块度D值要优于Q值。 值的两个社团合并,直至整个网络融合成一个社 总的来说,模块度优化算法是目前应用最为 团。整个过程可表示成一个树状图,从中选择Q广泛的一类算法,但是在具体分析中,很难确定一 值最大的层次划分得到最终的社团结构。该算法种合理的优化目标,使得分析结果难以反应真实 的总体时间复杂度为0(m(m+n)。在 Newman的社团结构,尤其是分析大规模复杂网络时,搜索 快速算法的基础上,CNM算法采用堆数据结构来空间非常大,使得许多模块度近似优化算法的结 计算和更新网络的模块度,大大提高了计算速度;果变得更不可靠。 MSG-MV算法则引入多步扩展迭代过程中每次1.2基于谱分析的社团发现算法 可合并多对社团以避免过早地收缩到少数较大的 谱分析法建立在谱图理论基础上,其主要思 社团。 想是根据特定图矩阵的特征向量导出对象的特 第二类算法主要采用分裂的思想,自顶向下 征,利用导出特征来推断对象之间的结构关系 进行。例如, Newman最早提出的GN算法就属于 通常选用的特定图矩阵有拉普拉斯矩阵和随机矩 这类算法,算法通过依次删去网络中边介数(即阵两类。图的拉普拉斯矩阵定义为L=D-W, 网络中经过每条边的最短路径数)最大的边,直至 其中D为以每个节点的度为对角元的对角矩阵, 每个节点单独退化为社团,然后从整个删边过程 中选取对应最大Q值时的结果。该算法复杂度W为图的邻接矩阵;随机矩阵则是根据邻接矩阵 较高,为0(n3)。随后,Nwmn等人通过定义模出的概率转移矩阵P=D-W。这两类矩阵有 个共同性质,同一社团节点对应的特征分量近 块度矩阵,将模块度用矩阵的特征向量表示,提出 种用于划分网络社团结构的谱方法。该算法 似相等,这成为目前谱分析方法实现社团发现的 通过求解模块度矩阵的最大正特征值以及对应的 理论基础。 基于谱分析的社团发现算法普遍做法是将节 特征向量,依据特征向量中元素的符号将网络不 断递归二分,直至子网络再细分已不能增大Q 点对应的矩阵特征分量看作空间坐标,将网络节 值。整个算法的平均时间复杂度为,较GN算法 点映射到多维特征向量空间中,运用传统的聚类 在计算速度和准确度上均有较大提高。 方法将节点聚成社团。例如, Donetti等山基于节 第三类算法则是直接寻优法,如Dh等提出点之间的距离度量,在不同维度的特征空间中建 的EO算法以及Agwl等提出的整数规划方立聚类树图,从中选择全局模块度最大的划分作 法。EO算法的思想是将每个节点对模块度Q为社团发现结果。Cmxi等则基于同一社团 值的贡献大小定义为局部变量,然后在随机初始的节点对应的随机矩阵特征分量强相关这一性质 划分的基础上,通过贪婪策略调整局部变量(具有提出计算特征向量的 Pearson相关系数来度量节 最小贡献度的变量)来提高全局目标函数Q值。点之间的相似度 整数规划方法则通过求解对应的松弛线性规划问 应用谱分析法不可避免地要计算矩阵特征 题能够给出最大模块度的一个上界,这是以前方 值,计算开销大,但由于能够通过特征谱将节点映 法所不具备的。此外,还有一些基于遗传算法、蚁射至欧拉空间,并能够直接应用传统向量聚类的 群算法等智能算法的社团发现算法也可归为此众多研究成果,灵活性较大 类 1.3基于信息论的社团发现算法 近年来越来越多的研究发现:模块度优化方 从信息论的角度出发, rosvall等把网络的 法无法发现小于一定粒度的社团0-。在实际模块化描述看作对网络拓扑结构的一种有损压 网络中,尤其是大规模网络中,社团的大小不 缩,从而将社团发现问题转换为信息论中的一个 该问题尤为突出。为此,研究者们提出一些局部基础问题:寻找拓扑结构的有效压缩方式。如图 调整策略。如Ruan等凹结合谱平分法和局部搜1所示,原拓扑结构X通过编码器产生模块描述 索方法提出的Hqt算法,在分裂网络前增加统Y,解码器对Y进行解码,推测出原结构Z,那么 计测试来判断是否需进一步细分。此外,部分研何种模块描述Y是最优的?以信息论的观点来 究者提岀新的模块度来避免ρ值存在的粒度问看,互信息I(X,Y)最大时,即最能反应原始结构 题。如李珍萍等提出的模块度D值,在衡量社x的Y是最优的。在该框架下,互信息(X,Y)
型代表算法有 Ｎｅｗｍａｎ快速算法［４］ 、ＣＮＭ算法［５］ 和 ＭＳＧＭＶ算法［６］等。Ｎｅｗｍａｎ快速算法将每个 节点看作是一个社团，每次迭代选择产生最大 Ｑ 值的两个社团合并，直至整个网络融合成一个社 团。整个过程可表示成一个树状图，从中选择 Ｑ 值最大的层次划分得到最终的社团结构。该算法 的总体时间复杂度为 Ｏ（ｍ（ｍ＋ｎ））。在 Ｎｅｗｍａｎ 快速算法的基础上，ＣＮＭ算法采用堆数据结构来 计算和更新网络的模块度，大大提高了计算速度； ＭＳＧＭＶ算法则引入多步扩展，迭代过程中每次 可合并多对社团以避免过早地收缩到少数较大的 社团。 第二类算法主要采用分裂的思想，自顶向下 进行。例如，Ｎｅｗｍａｎ最早提出的 ＧＮ算法就属于 这类算法［１］ ，算法通过依次删去网络中边介数（即 网络中经过每条边的最短路径数）最大的边，直至 每个节点单独退化为社团，然后从整个删边过程 中选取对应最大 Ｑ值时的结果。该算法复杂度 较高，为 Ｏ（ｎ３）。随后，Ｎｅｗｍａｎ等人通过定义模 块度矩阵，将模块度用矩阵的特征向量表示，提出 一种用于划分网络社团结构的谱方法［７］ 。该算法 通过求解模块度矩阵的最大正特征值以及对应的 特征向量，依据特征向量中元素的符号将网络不 断递归二分，直至子网络再细分已不能增大 Ｑ 值。整个算法的平均时间复杂度为，较 ＧＮ算法 在计算速度和准确度上均有较大提高。 第三类算法则是直接寻优法，如 Ｄｕｃｈ等提出 的 ＥＯ算法［８］以及 Ａｇａｒｗａｌ等提出的整数规划方 法［９］ 。ＥＯ算法的思想是将每个节点对模块度 Ｑ 值的贡献大小定义为局部变量，然后在随机初始 划分的基础上，通过贪婪策略调整局部变量（具有 最小贡献度的变量）来提高全局目标函数 Ｑ值。 整数规划方法则通过求解对应的松弛线性规划问 题能够给出最大模块度的一个上界，这是以前方 法所不具备的。此外，还有一些基于遗传算法、蚁 群算法等智能算法的社团发现算法也可归为此 类。 近年来越来越多的研究发现：模块度优化方 法无法发现小于一定粒度的社团［１０－１１］ 。在实际 网络中，尤其是大规模网络中，社团的大小不一， 该问题尤为突出。为此，研究者们提出一些局部 调整策略。如 Ｒｕａｎ等［１２］ 结合谱平分法和局部搜 索方法提出的 ＨＱｃｕｔ算法，在分裂网络前增加统 计测试来判断是否需进一步细分。此外，部分研 究者提出新的模块度来避免 Ｑ值存在的粒度问 题。如李珍萍等［１３］ 提出的模块度 Ｄ值，在衡量社 团内外连接度的差异时，引入了社团大小作为分 母进行平均，从理论和数值试验上证明了作为模 块度 Ｄ值要优于 Ｑ值。 总的来说，模块度优化算法是目前应用最为 广泛的一类算法，但是在具体分析中，很难确定一 种合理的优化目标，使得分析结果难以反应真实 的社团结构，尤其是分析大规模复杂网络时，搜索 空间非常大，使得许多模块度近似优化算法的结 果变得更不可靠。 １２ 基于谱分析的社团发现算法 谱分析法建立在谱图理论基础上，其主要思 想是根据特定图矩阵的特征向量导出对象的特 征，利用导出特征来推断对象之间的结构关系。 通常选用的特定图矩阵有拉普拉斯矩阵和随机矩 阵两类。图的拉普拉斯矩阵定义为 Ｌ＝Ｄ－Ｗ， 其中 Ｄ为以每个节点的度为对角元的对角矩阵， Ｗ 为图的邻接矩阵；随机矩阵则是根据邻接矩阵 导出的概率转移矩阵 Ｐ＝Ｄ－１Ｗ。这两类矩阵有 一个共同性质，同一社团节点对应的特征分量近 似相等，这成为目前谱分析方法实现社团发现的 理论基础。 基于谱分析的社团发现算法普遍做法是将节 点对应的矩阵特征分量看作空间坐标，将网络节 点映射到多维特征向量空间中，运用传统的聚类 方法将节点聚成社团。例如，Ｄｏｎｅｔｔｉ等［１４］基于节 点之间的距离度量，在不同维度的特征空间中建 立聚类树图，从中选择全局模块度最大的划分作 为社团发现结果。Ｃａｐｏｃｃｉ等［１５］则基于同一社团 的节点对应的随机矩阵特征分量强相关这一性质 提出计算特征向量的 Ｐｅａｒｓｏｎ相关系数来度量节 点之间的相似度。 应用谱分析法不可避免地要计算矩阵特征 值，计算开销大，但由于能够通过特征谱将节点映 射至欧拉空间，并能够直接应用传统向量聚类的 众多研究成果，灵活性较大。 １３ 基于信息论的社团发现算法 从信息论的角度出发，Ｒｏｓｖａｌｌ等［１１］把网络的 模块化描述看作对网络拓扑结构的一种有损压 缩，从而将社团发现问题转换为信息论中的一个 基础问题：寻找拓扑结构的有效压缩方式。如图 １所示，原拓扑结构 Ｘ通过编码器产生模块描述 Ｙ，解码器对 Ｙ进行解码，推测出原结构 Ｚ，那么 何种模块描述 Ｙ是最优的？以信息论的观点来 看，互信息 Ｉ（Ｘ，Ｙ）最大时，即最能反应原始结构 Ｘ的 Ｙ是最优的。在该框架下，互信息 Ｉ（Ｘ，Ｙ） · ４８· 国 防 科 技 大 学 学 报 ２０１１年
骆志刚等:复杂网络社团发现算法研究新进展49 最大等价于求条件信息H(XIy)最小, rosal等点严格地划分到某个社团中,而真实世界中这种 给出了条件信息的量化表示并运用模拟退火优化硬划分并不能真正反应节点和社团的实际关系, 算法进行求解,可实现上千个节点的网络社团发例如蛋白质相互作用网络中由于蛋白质功能的多 现。测试表明,对于社团大小及边密度不一的社样性,单个蛋白质在不同的时空条件下参与不同 团发现问题,该发现算法要明显优于基于模块度的功能模块中。同样的现象普遍存在于各种真实 优化的社团发现算法。后来, rosvall等进一步以网络之中,如社会网络中的人属于多个集体、网络 描述图中信息的扩散过程为目标,将问题转换中的网页属于多个主题等。因此,重叠社团发现 为寻找描述网络上随机游走的有效编码方式,使更符合真实世界的社团组织规律,成为近几年社 该方法更适合于捕捉社团内部节点之间的长程相团发现研究的新热点,涌现出许多新颖算法。 关性已有文献测试表明该方法是目前非重叠社2.1基于团渗透改进的重叠社团发现算法 团发现算法里准确度最高的一类方法 由Pll等提出的团渗透算法是首个能够 发现重叠社团的算法,文献[2]中已对其进行详细 -A Encoder Decoder 介绍。该类算法认为社团是由一系列相互可达的 图1从信息论的角度看社团发现 k-团(即大小为k的完全子图)组成的,即k-社 Fig 1 Community detection from the view of 团。算法通过合并相邻的k-团来实现社团发 现,而那些处于多个k-社团中的节点即是社团 1.4基于标号传播的社团发现算法 的“重叠”部分。 很多情况下,复杂网络的边表示的是个体之 Kumpula等在前人工作基础上进一步提出 间的信息传播,其传播的结果通常是使得社团内种快速团渗透算法(SCP算法)。该算法分两阶 部节点之间共享相同的信息。 Raghavan等基段进行,第一阶段将网络的边按顺序(如加权网络 于该思想提出一种快速的标号传播算法(简称为按权值大小顺序)插入到网络中,并同时检测出现 IPA算法)。如图2所示,PA算法首先为每个节的k-团;第二阶段将检测的k-团,根据是否与 点指派唯一标号,在每一步迭代中,每个节点将自已有k-社团相邻,并入k-社团或形成新的k 身标号更新为其邻节点出现次数最多的标号,如社团。由于边插入的顺序性,在第二阶段检测时 果存在多个相同的最多标号,则随机选择一个作SCP算法只需依次对k-团进行局部判断;而且 为更新值,若干次迭代后密集相连的节点会收敛SCP算法能够在一遍运行中检测不同权重阈值下 于同一标号,最终,具有相同标号的节点归为一个的k-社团,较大地提高了团渗透算法的计算速 社团。 度 基于团渗透思想的算法需要以团为基本单元 来发现重叠,这对于很多真实网络尤其是稀疏网 络而言,限制条件过于严格,只能发现少量的重叠 图2标号传播过程示意 社团{2。 Fig.2 The process of label propagation(s 2.2基于模糊聚类的重叠社团发现算法 LPA算法最大的优点在于不需要任何参数输 另一观点认为可将重叠社团发现归于传统模 入,比如社团的数目、大小等,而且算法具有线性糊聚类问题加以解决,以计算节点到社团的模糊 的时间复杂度为0(m),m为网络的边数,收敛速隶属度来揭示节点的社团关系。这类算法通常从 度非常快,可适用于规模较大的复杂网络。随后,构建节点距离出发,再结合传统模糊聚类求解隶 Leung等对标号更新规则进行了改进。在IPA属度矩阵。 迭代过程中引入衷减因子,每次迭代由衷减因子 张世华等首先应用这一思想,他们结合谱 边权重、偏好特征决定更新的标号,同时增加标号分析方法将网络中的节点近似映射到欧拉空间中 更新的选择性,比如共享最大标号的邻居少于某的数据点,进而利用FCM算法对空间中的数据点 个比例时才进行更新,降低了计算开销。 进行聚类,从而得到节点与社团之间的隶属度矩 2重叠社团发现算法 阵。由于模糊聚类算法FCM本身要求预先知道 社团数,该算法在模块度Q值的基础上引入新的 前面所介绍的非重叠社团发现方法把每个节模块度指标模糊模块度Q,选取使得Q值最大的
最大等价于求条件信息 Ｈ（Ｘ｜Ｙ）最小，Ｒｏｓｖａｌｌ等 给出了条件信息的量化表示并运用模拟退火优化 算法进行求解，可实现上千个节点的网络社团发 现。测试表明，对于社团大小及边密度不一的社 团发现问题，该发现算法要明显优于基于模块度 优化的社团发现算法。后来，Ｒｏｓｖａｌｌ等进一步以 描述图中信息的扩散过程为目标［１６］ ，将问题转换 为寻找描述网络上随机游走的有效编码方式，使 该方法更适合于捕捉社团内部节点之间的长程相 关性，已有文献测试表明该方法是目前非重叠社 团发现算法里准确度最高的一类方法［１７］ 。 图 １ 从信息论的角度看社团发现［１１］ Ｆｉｇ．１ Ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｆｒｏｍｔｈｅｖｉｅｗｏｆ ｉｎｆｏｒｍａｔｉｏｎｔｈｅｏｒｙ ［１１］ １４ 基于标号传播的社团发现算法 很多情况下，复杂网络的边表示的是个体之 间的信息传播，其传播的结果通常是使得社团内 部节点之间共享相同的信息。Ｒａｇｈａｖａｎ等［１８］基 于该思想提出一种快速的标号传播算法（简称为 ＬＰＡ算法）。如图 ２所示，ＬＰＡ算法首先为每个节 点指派唯一标号，在每一步迭代中，每个节点将自 身标号更新为其邻节点出现次数最多的标号，如 果存在多个相同的最多标号，则随机选择一个作 为更新值，若干次迭代后密集相连的节点会收敛 于同一标号，最终，具有相同标号的节点归为一个 社团。 图 ２ 标号传播过程示意［１８］ Ｆｉｇ．２ Ｔｈｅｐｒｏｃｅｓｓｏｆｌａｂｅｌｐｒｏｐａｇａｔｉｏｎ ［１８］ ＬＰＡ算法最大的优点在于不需要任何参数输 入，比如社团的数目、大小等，而且算法具有线性 的时间复杂度为 Ｏ（ｍ），ｍ为网络的边数，收敛速 度非常快，可适用于规模较大的复杂网络。随后， Ｌｅｕｎｇ等对标号更新规则进行了改进［１９］ 。在 ＬＰＡ 迭代过程中引入衷减因子，每次迭代由衷减因子、 边权重、偏好特征决定更新的标号，同时增加标号 更新的选择性，比如共享最大标号的邻居少于某 个比例时才进行更新，降低了计算开销。 ２ 重叠社团发现算法 前面所介绍的非重叠社团发现方法把每个节 点严格地划分到某个社团中，而真实世界中这种 硬划分并不能真正反应节点和社团的实际关系， 例如蛋白质相互作用网络中由于蛋白质功能的多 样性，单个蛋白质在不同的时空条件下参与不同 的功能模块中。同样的现象普遍存在于各种真实 网络之中，如社会网络中的人属于多个集体、网络 中的网页属于多个主题等。因此，重叠社团发现 更符合真实世界的社团组织规律，成为近几年社 团发现研究的新热点，涌现出许多新颖算法。 ２１ 基于团渗透改进的重叠社团发现算法 由 Ｐａｌｌａ等［２０］ 提出的团渗透算法是首个能够 发现重叠社团的算法，文献［２］中已对其进行详细 介绍。该类算法认为社团是由一系列相互可达的 ｋ－团（即大小为 ｋ的完全子图）组成的，即 ｋ－社 团。算法通过合并相邻的 ｋ－团来实现社团发 现，而那些处于多个 ｋ－社团中的节点即是社团 的“重叠”部分。 Ｋｕｍｐｕｌａ等在前人工作基础上进一步提出一 种快速团渗透算法（ＳＣＰ算法）［２１］ 。该算法分两阶 段进行，第一阶段将网络的边按顺序（如加权网络 按权值大小顺序）插入到网络中，并同时检测出现 的 ｋ－团；第二阶段将检测的 ｋ－团，根据是否与 已有 ｋ－社团相邻，并入 ｋ－社团或形成新的 ｋ－ 社团。由于边插入的顺序性，在第二阶段检测时 ＳＣＰ算法只需依次对 ｋ－团进行局部判断；而且 ＳＣＰ算法能够在一遍运行中检测不同权重阈值下 的 ｋ－社团，较大地提高了团渗透算法的计算速 度。 基于团渗透思想的算法需要以团为基本单元 来发现重叠，这对于很多真实网络尤其是稀疏网 络而言，限制条件过于严格，只能发现少量的重叠 社团［２２］ 。 ２２ 基于模糊聚类的重叠社团发现算法 另一观点认为可将重叠社团发现归于传统模 糊聚类问题加以解决，以计算节点到社团的模糊 隶属度来揭示节点的社团关系。这类算法通常从 构建节点距离出发，再结合传统模糊聚类求解隶 属度矩阵。 张世华等首先应用这一思想［２３］ ，他们结合谱 分析方法将网络中的节点近似映射到欧拉空间中 的数据点，进而利用 ＦＣＭ算法对空间中的数据点 进行聚类，从而得到节点与社团之间的隶属度矩 阵。由于模糊聚类算法 ＦＣＭ本身要求预先知道 社团数，该算法在模块度 Ｑ值的基础上引入新的 模块度指标模糊模块度珟Ｑ，选取使得珟Ｑ值最大的 第 １期 骆志刚，等：复杂网络社团发现算法研究新进展 · ４９·
国防科技大学学报 011年 模糊聚类结果作为最终的社团划分结果。 降低算法对初始条件的敏感性,扩大了适用范围。 上述方法在判断社团数上需要预先给定或花2.4基于种子扩展思想的重叠社团发现算法 费大量计算以确定合理的社团数目。我们在文献 此类算法的基本思想是以具有某种特征的子 [24]中提出基于通信-时间核构建距离矩阵,输网络为种子,通过合并扩展等操作向邻接节点扩 入到模糊相似性传播聚类来实现重叠社团发现, 展,直至获得评价函数最大的社团。该类算法近 在考虑节点长程相关性的同时,可以自适应地确两年来得到了迅速发展。 定社团数。值得一提的是,此类算法的关键在于 Lancichinetti等切提出以若干个节点为种子 所构建的距离矩阵,采用何种节点距离更符合实 通过扩展形成对整个网络的覆盖,即LMF算法 际情况在具体应用中是一个值得探索的问题。 该算法定义了两个适应度函数:社团的适应度和 23基于非负矩阵分解的重叠社团发现算法节点对社团的适应度。其种子扩展的基本步骤 非负矩阵分解方法是一种聚类和降维技术,是:以单个节点为初始社团g,考虑所有与其相 已经在多个领域取得广泛应用。它将特征矩阵邻的节点A,将对g的适应度最大的邻节点加入 V近似分解为两个非负矩阵Wnxk和Hx,使得到当前社团形成s,重新计算g中各节点的适应 两者的乘积尽可能等于原有特征矩阵。将非负矩度,将适应度为负的节点剔除,重复上述过程直至 阵分解应用于社团发现,其思想是特征矩阵V中扩展后的社团其邻节点对它的适应度均为负。通 的每个行向量ν可以近似地看作H的列向量的过一定的种子选取策略(每次选取尚未指派到社 线性组合:=wH,w其中是W的行向量,从而可团的节点),可以由扩展得到的若干个局部社团生 以用相对于V更少的基向量H来表示整个数据成整个网络的覆盖,保证网络中每个节点至少被 空间,而w则表示各基向量对于产生数据点所个局部社团所覆盖。 起到的权重。因此,可以利用W将各节点聚成k 此外,尚明生、陈端兵等也提出类似的种子扩 个类,而W各分量值表示每个节点到每个社团的展思想{x-列,主要区别在于种子选择策略、扩展 绝对隶属度。从图3所示的w分量曲线可以看评价函数上的不同。如文献[28]提出节点强度的 出,节点6和节点11分别与两个社团呈现出一定概念,即节点所有邻接边的权重之和,依次以最大 的隶属关系,说明节点6和节点11是潜在的社团强度的单个节点为种子;文献[29]则是以最大团 重叠区域。算法关键在于如何选取特征矩阵以表为种子,通过合并和扩展两步逐步形成最终的社 示复杂网络中所蕴含的拓扑信息 团,而两者均以考虑节点隶属度的重叠模块度Q 为扩展评价函数。 2.5基于混合概率模型的重叠社团发现 前述很多算法均是先给出社团结构的定义或 量化特征,然后再设计相应的算法寻找社团。换 句话说,这些方法均需对社团结构作出假设。针 012345678910111213l 对此问题, Newman等建立了社团结构的混合概率 模型,以概率方法对复杂网络的社团结构进行探 图3一个包含两个重叠节点的简单网络 及其对应的分量 索,以求得期望最大的社团结构,从而避开社团定 Fig 3 A simple network with two overlapping node 义的问题。他们认为社团是由具有相似连接 correspondingwentries 的节点组成的,因此定义两个模型参数和π用 张世华等首次将NMF应用于重叠社团发 来刻画社团r的特征,其中bn表示社团r中某节 现,他们以扩散核为基础,将正规化后的核矩 点对节点i的连接概率,丌,表示社团r的节点数 阵作为特征矩阵V,同时采用一种梯度下降的迭 代方法来求解W和H。该算法最大的优点在于占整个网络节点数的比例。通过这两个参数,可 能够给出节点与社团之间所属关系的绝对概率, 以将网络的邻接矩阵A看作是观察数据,并引入 这是上述算法所不具备的。但该算法依然需要预缺失数据g={g},用来表示节点i所属社团,由 先给定k参数不可避免在确定k值时带来较高此将问题转换为典型的带缺失数据的最大似然估 的计算开销仅适用较小规模的网络。Zmei等则计间题,其似然度计算如下: 引入新的节点-节点关联矩阵作为特征矩阵, L= InP(A ,) =lnP(A|g,π,)P(g|π,0)
模糊聚类结果作为最终的社团划分结果。 上述方法在判断社团数上需要预先给定或花 费大量计算以确定合理的社团数目。我们在文献 ［２４］中提出基于通信 －时间核构建距离矩阵，输 入到模糊相似性传播聚类来实现重叠社团发现， 在考虑节点长程相关性的同时，可以自适应地确 定社团数。值得一提的是，此类算法的关键在于 所构建的距离矩阵，采用何种节点距离更符合实 际情况在具体应用中是一个值得探索的问题。 ２３ 基于非负矩阵分解的重叠社团发现算法 非负矩阵分解方法是一种聚类和降维技术， 已经在多个领域取得广泛应用。它将特征矩阵 Ｖ近似分解为两个非负矩阵 Ｗｎ×ｋ和 Ｈｋ×ｎ，使得 两者的乘积尽可能等于原有特征矩阵。将非负矩 阵分解应用于社团发现，其思想是特征矩阵 Ｖ中 的每个行向量 ｖ可以近似地看作 Ｈ的列向量的 线性组合：ｖ＝ｗＨ，ｗ其中是Ｗ 的行向量，从而可 以用相对于 Ｖ更少的基向量 Ｈ来表示整个数据 空间，而 ｗ则表示各基向量对于产生数据点 ｖ所 起到的权重。因此，可以利用 Ｗ 将各节点聚成 ｋ 个类，而 Ｗ 各分量值表示每个节点到每个社团的 绝对隶属度。从图 ３所示的 ｗ分量曲线可以看 出，节点 ６和节点 １１分别与两个社团呈现出一定 的隶属关系，说明节点 ６和节点 １１是潜在的社团 重叠区域。算法关键在于如何选取特征矩阵以表 示复杂网络中所蕴含的拓扑信息。 图 ３ 一个包含两个重叠节点的简单网络 及其对应的 ｗ分量 Ｆｉｇ．３ Ａｓｉｍｐｌｅｎｅｔｗｏｒｋｗｉｔｈｔｗｏｏｖｅｒｌａｐｐｉｎｇｎｏｄｅ ａｎｄｃｏｒｒｅｓｐｏｎｄｉｎｇｗｅｎｔｒｉｅｓ 张世华等首次将 ＮＭＦ应用于重叠社团发 现［２５］ ，他们以扩散核为基础，将正规化后的核矩 阵作为特征矩阵 Ｖ，同时采用一种梯度下降的迭 代方法来求解 Ｗ 和 Ｈ。该算法最大的优点在于 能够给出节点与社团之间所属关系的绝对概率， 这是上述算法所不具备的。但该算法依然需要预 先给定 ｋ参数，不可避免在确定 ｋ值时带来较高 的计算开销，仅适用较小规模的网络。Ｚａｒｅｉ等则 引入新的节点 －节点关联矩阵作为特征矩阵［２６］ ， 降低算法对初始条件的敏感性，扩大了适用范围。 ２４ 基于种子扩展思想的重叠社团发现算法 此类算法的基本思想是以具有某种特征的子 网络为种子，通过合并、扩展等操作向邻接节点扩 展，直至获得评价函数最大的社团。该类算法近 两年来得到了迅速发展。 Ｌａｎｃｉｃｈｉｎｅｔｔｉ等［２７］ 提出以若干个节点为种子， 通过扩展形成对整个网络的覆盖，即 ＬＭＦ算法。 该算法定义了两个适应度函数：社团的适应度和 节点对社团的适应度。其种子扩展的基本步骤 是：以单个节点 ｖ为初始社团 ｇ，考虑所有与其相 邻的节点 Ａ，将对 ｇ的适应度最大的邻节点加入 到当前社团形成 ｇ′，重新计算 ｇ′中各节点的适应 度，将适应度为负的节点剔除，重复上述过程直至 扩展后的社团其邻节点对它的适应度均为负。通 过一定的种子选取策略（每次选取尚未指派到社 团的节点），可以由扩展得到的若干个局部社团生 成整个网络的覆盖，保证网络中每个节点至少被 一个局部社团所覆盖。 此外，尚明生、陈端兵等也提出类似的种子扩 展思想［２８－２９］ ，主要区别在于种子选择策略、扩展 评价函数上的不同。如文献［２８］提出节点强度的 概念，即节点所有邻接边的权重之和，依次以最大 强度的单个节点为种子；文献［２９］则是以最大团 为种子，通过合并和扩展两步逐步形成最终的社 团，而两者均以考虑节点隶属度的重叠模块度 Ｑｏ 为扩展评价函数。 ２５ 基于混合概率模型的重叠社团发现 前述很多算法均是先给出社团结构的定义或 量化特征，然后再设计相应的算法寻找社团。换 句话说，这些方法均需对社团结构作出假设。针 对此问题，Ｎｅｗｍａｎ等建立了社团结构的混合概率 模型，以概率方法对复杂网络的社团结构进行探 索，以求得期望最大的社团结构，从而避开社团定 义的问题［３０］ 。他们认为社团是由具有相似连接 的节点组成的，因此定义两个模型参数θｒｉ和πｒ用 来刻画社团 ｒ的特征，其中θｒｉ表示社团 ｒ中某节 点对节点 ｉ的连接概率，πｒ表示社团 ｒ的节点数 占整个网络节点数的比例。通过这两个参数，可 以将网络的邻接矩阵 Ａ看作是观察数据，并引入 缺失数据 ｇ＝｛ｇｉ｝，用来表示节点 ｉ所属社团，由 此将问题转换为典型的带缺失数据的最大似然估 计问题，其似然度计算如下： Ｌ＝ｌｎＰ（Ａ，ｇ｜π，θ） ＝ｌｎＰ（Ａ｜ｇ，π，θ）Ｐ（ｇ｜π，θ） · ５０· 国 防 科 技 大 学 学 报 ２０１１年
骆志刚等:复杂网络社团发现算法研究新进展 (1)建立统一的度量标准。由于复杂网络的 通过简单变形后可直接运用EM算法进行求类型众多,连接规律各有不同,很难以社团结构的 某种统一的模块度(如Q值)来刻画社团发现算 解。由于该算法未对社团结构作过多假设,具有 法的优劣。一种更为科学的方式是建立一套包含 较强的灵活性,能够发现不同结构类型的社团,如 多种复杂网络的统一标准测试集,以评判算法在 具有二分结构的社团,这是之前方法所不具备的。不同类型网络中的优劣,明确算法的适用范围。 同时所求得的参数中暗含了节点i到社团r的 隶属程度,因此,通过该算法能够识别出重叠社复杂网络的规模越来越大,对算法的计算复杂度 团,并得到隶属程度大小。然而,该方法基于EM提出了更高要求。虽然在不考虑重叠社团的情况 算法来估计未知参数,收敛速度较慢,计算复杂度 下,已出现一些接近于线性时间复杂度的算法,但 较高,一定程度上制约了算法的应用规模。 这些算法通常采用较为激进的贪婪策略,网络规 2.6基于边聚类的重叠社团发现 模变大且非稀疏时,其结果变得不可靠。在重叠 以往社团发现算法的研究均以节点为对象,社团发现算法中,很多算法需要通过多次计算来 考虑如何通过划分、聚类优化等技术将节点归为获得最佳的社团数,计算开销过大。因此,考虑复 重叠或不重叠的社团。最近,Eans等和Ah杂网络社团密度不均的特点,从局部社团出发研 等分别发表了以边为研究对象来划分社团。究网络的社团结构是未来的重要研究方向之一 虽然节点属于多重社团,但边通常只对应某一特此外,设计适合于大规模网络分析的高效并行算 定类型的交互(真实网络中的某种性质或功能)。法也是未来重要的研究方向之一。 因此,以边为对象使得划分的结果更能真实地反 (3)重叠社团与层次社团的结合。一般认为 映节点在复杂网络中的角色或功能。文献[31-社团之间共享部分边缘节点从而产生重叠社团 32]虽然都是对边进行聚类来提示重叠社团,但在然而重叠社团结构远比想象的要复杂。实际上 处理方式上有所不同。 除了重叠性,层次性也是社团结构的另一大特性。 文献[31]将原网络转换为加权线图,即原网例如,第i层中的中心节点,可能在第j层中就变 络中的边映射为线图中的节点,线图中的节点存成了边缘节点。可见,重叠性与层次性两者联系 在边当且仅当原网络中所对应的边存在共享节十分紧密,有必要将两者融和在一起来解构复杂 点,而边权值等于1/(k-1),其中k为共享节点网络。在目前的众多方法中,唯有边社团给出了 的度。通过网络的转换,最大的好处是可以直接社团重叠性和层次性普遍并存的合理解释,未来 应用非重叠社团发现算法来提示网络的重叠社以边为对象来研究网络社团结构将是一个值得深 入研究的方向。 文献[32]则着重解决社团的重叠性与层次性 之间的冲突,提出边社团的概念,即将社团看作是参考文献: 紧密相连的边集合。作者在定义边间相似度的基t1]GnmM, Newman M E J. Community Structure in Social and 础上,采用层次聚类建立聚类树状图。由于每个 Biological Networks [J]. P Natl Acad Sci USA, 2002, 99(12) 7821-7826 节点拥有一条到多条边,每条边存在于一个边社 [2]解诌,汪小帆复杂网络中的社团结构分析算法研究综述 团中,因此对该树状图不同层次的切割得到的社 [J].复杂系统与复杂性科学,2005,2(3):12 团结构对应着不同层次的重叠社团。 [3]李晓佳,张鹏,狄增如,等.复杂网络中的社团结构[ 杂系统与复杂性科学,2008,5(3):24 3总结与展望 [4] Newman M EJ. Fast Algorithm for Detecting Commmunity Structure 从异常复杂的网络解构出其中的社团结构, in Networks[J]. Phys Rev E, 2004, 69(6):0661 [5] Clauset A. Finding Local Commmunity Structure in Networks[J] 已成为当今复杂系统研究领域一项具有挑战性的 研究课题。虽然该课题近些年受到广泛关注,涌[6] Schuetz P. Caflisch A. Multistep greedly Algrithm Identifies Commi 现出一批新颖的算法,但目前相关研究仍未形成 Structure in Real-world and Commputer-gnerated Networks[J].Whys Rev 统一的框架和度量标准,尤其是重叠社团发现算 E,x8,78(2):026112. 法的研究,尚存许多问题丞待解决。我们认为,复 [7] Newman M J. Modularity and Community Structure in Networks [门]. Proc Natl Acad Sci usa,2006,103(23):8577-858 杂网络社团发现的进一步研究可从以下几个方面 [8] Duch J, Arenas A. Commnity Detection in Complex Networks 展开。 Using Extremal Optimization [J]. Phys Rev E, 2005, 72(2)
＝∑ｉ ｌｎπｇｉ ＋∑ ｊ Ａｉｊｌｎθｇｉ [ ，ｊ] 通过简单变形后可直接运用 ＥＭ算法进行求 解。由于该算法未对社团结构作过多假设，具有 较强的灵活性，能够发现不同结构类型的社团，如 具有二分结构的社团，这是之前方法所不具备的。 同时所求得的参数θｒｉ中暗含了节点 ｉ到社团 ｒ的 隶属程度，因此，通过该算法能够识别出重叠社 团，并得到隶属程度大小。然而，该方法基于 ＥＭ 算法来估计未知参数，收敛速度较慢，计算复杂度 较高，一定程度上制约了算法的应用规模。 ２６ 基于边聚类的重叠社团发现 以往社团发现算法的研究均以节点为对象， 考虑如何通过划分、聚类、优化等技术将节点归为 重叠或不重叠的社团。最近，Ｅｖａｎｓ等［３１］和 Ａｈｎ 等［３２］ 分别发表了以边为研究对象来划分社团。 虽然节点属于多重社团，但边通常只对应某一特 定类型的交互（真实网络中的某种性质或功能）。 因此，以边为对象使得划分的结果更能真实地反 映节点在复杂网络中的角色或功能。文献［３１－ ３２］虽然都是对边进行聚类来提示重叠社团，但在 处理方式上有所不同。 文献［３１］将原网络转换为加权线图，即原网 络中的边映射为线图中的节点，线图中的节点存 在边当且仅当原网络中所对应的边存在共享节 点，而边权值等于 １?（ｋ－１），其中 ｋ为共享节点 的度。通过网络的转换，最大的好处是可以直接 应用非重叠社团发现算法来提示网络的重叠社 团。 文献［３２］则着重解决社团的重叠性与层次性 之间的冲突，提出边社团的概念，即将社团看作是 紧密相连的边集合。作者在定义边间相似度的基 础上，采用层次聚类建立聚类树状图。由于每个 节点拥有一条到多条边，每条边存在于一个边社 团中，因此对该树状图不同层次的切割得到的社 团结构对应着不同层次的重叠社团。 ３ 总结与展望 从异常复杂的网络解构出其中的社团结构， 已成为当今复杂系统研究领域一项具有挑战性的 研究课题。虽然该课题近些年受到广泛关注，涌 现出一批新颖的算法，但目前相关研究仍未形成 统一的框架和度量标准，尤其是重叠社团发现算 法的研究，尚存许多问题丞待解决。我们认为，复 杂网络社团发现的进一步研究可从以下几个方面 展开。 （１）建立统一的度量标准。由于复杂网络的 类型众多，连接规律各有不同，很难以社团结构的 某种统一的模块度（如 Ｑ值）来刻画社团发现算 法的优劣。一种更为科学的方式是建立一套包含 多种复杂网络的统一标准测试集，以评判算法在 不同类型网络中的优劣，明确算法的适用范围。 （２）适用于大规模复杂网络的社团发现算法。 复杂网络的规模越来越大，对算法的计算复杂度 提出了更高要求。虽然在不考虑重叠社团的情况 下，已出现一些接近于线性时间复杂度的算法，但 这些算法通常采用较为激进的贪婪策略，网络规 模变大且非稀疏时，其结果变得不可靠。在重叠 社团发现算法中，很多算法需要通过多次计算来 获得最佳的社团数，计算开销过大。因此，考虑复 杂网络社团密度不均的特点，从局部社团出发研 究网络的社团结构是未来的重要研究方向之一。 此外，设计适合于大规模网络分析的高效并行算 法也是未来重要的研究方向之一。 （３）重叠社团与层次社团的结合。一般认为， 社团之间共享部分边缘节点从而产生重叠社团， 然而重叠社团结构远比想象的要复杂。实际上， 除了重叠性，层次性也是社团结构的另一大特性。 例如，第 ｉ层中的中心节点，可能在第 ｊ层中就变 成了边缘节点。可见，重叠性与层次性两者联系 十分紧密，有必要将两者融和在一起来解构复杂 网络。在目前的众多方法中，唯有边社团给出了 社团重叠性和层次性普遍并存的合理解释，未来 以边为对象来研究网络社团结构将是一个值得深 入研究的方向。 参 考 文 献： ［１］ ＧｉｒｖａｎＭ，ＮｅｗｍａｎＭ ＥＪ．ＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＳｏｃｉａｌａｎｄ ＢｉｏｌｏｇｉｃａｌＮｅｔｗｏｒｋｓ［Ｊ］．ＰＮａｔｌＡｃａｄＳｃｉＵＳＡ，２００２，９９（１２）： ７８２１－７８２６． ［２］ 解亻刍，汪小帆．复杂网络中的社团结构分析算法研究综述 ［Ｊ］．复杂系统与复杂性科学，２００５，２（３）：１２． ［３］ 李晓佳，张鹏，狄增如，等．复杂网络中的社团结构［Ｊ］．复 杂系统与复杂性科学，２００８，５（３）：２４． ［４］ ＮｅｗｍａｎＭＥＪ．ＦａｓｔＡｌｇｏｒｉｔｈｍｆｏｒＤｅｔｅｃｔｉｎｇＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅ ｉｎＮｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓＲｅｖＥ，２００４，６９（６）：０６６１３３． ［５］ ＣｌａｕｓｅｔＡ．ＦｉｎｄｉｎｇＬｏｃａｌＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＮｅｔｗｏｒｋｓ［Ｊ］． ＰｈｙｓＲｅｖＥ，２００５，７２（２）：０２６１３２． ［６］ ＳｃｈｕｅｔｚＰ，ＣａｆｌｉｓｃｈＡ．ＭｕｌｔｉｓｔｅｐＧｒｅｅｄｙＡｌｇｏｒｉｔｈｍＩｄｅｎｔｉｆｉｅｓＣｏｍｍｕｎｉｔｙ ＳｔｒｕｃｔｕｒｅｉｎＲｅａｌｗｏｒｌｄａｎｄＣｏｍｐｕｔｅｒｇｅｎｅｒａｔｅｄＮｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓＲｅｖ Ｅ，２００８，７８（２）：０２６１１２． ［７］ ＮｅｗｍａｎＭＥＪ．ＭｏｄｕｌａｒｉｔｙａｎｄＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＮｅｔｗｏｒｋｓ ［Ｊ］．ＰｒｏｃＮａｔｌＡｃａｄＳｃｉＵＳＡ，２００６，１０３（２３）：８５７７－８５８２． ［８］ ＤｕｃｈＪ，ＡｒｅｎａｓＡ．ＣｏｍｍｕｎｉｔｙＤｅｔｅｃｔｉｏｎｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ ＵｓｉｎｇＥｘｔｒｅｍａｌＯｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．ＰｈｙｓＲｅｖＥ，２００５，７２（２）： 第 １期 骆志刚，等：复杂网络社团发现算法研究新进展 · ５１·
国防科技大学学 011年 027104 (2):026109 [9] Agarwal G, Kempe D. Modularity-maximizing Graph Communities [22] Zhang S H, Ning X M, Zhang X S.Identification of Functional Via Mathematical Programming[ J]. The European Physical Joumal Modules in a PPI Network By Clique Percolation Clustering[J] B-Condensed Matter and Complex Systems, 2008, 66(3):409 Cm甲 out Biol Chem,2006,30(6):445-451 [10] Fortunato S, Barthelemy M. Resolution Limit in Communit Community Structure in Complex Networks Using Fuzzy C-means Detection [J]. P Natl Aead Sci USA, 2007, 104(1):36-41 uttering [J. Physica A: Statistical Mechanics and its [1 pplications,2007,374(1):483-490 for Resolving Community Structure in Complex Networks[J]. P [24] Ding F, Luo Z, Shi J, et al. Overlapping Commumity Detection Natl Acad sci usa,2007,104(18):7327-7331 By Kemel-based Furzy Affinity Propagation[ C ]/Proceedings of [12] Ruan J H, Zhang WX. Identifying Network Communities with a the 2nd International Workshop on Intelligent Systems and High Resolution[J]. Phys Rev E, 2008, 77 (1):0161 Applications( ISA 2010), Wuhan, China, 2010 [13] Li Z, Zhang S, S,et al. Quantitative Function for [25] Zhang S, Wang R S, Zhang X S. Uncovering Fuzzy Community Commmunity Detection [J]. Phys Rev E Stat Nonlin Soft Matter Structure in Complex Networks[J]. Phys Rev E, 2007, 76(4) 77(3):036109 [14 Donetti L, Munoz M. Detecting Network Communities: A New [26] Zarci M, Izadi D, Systematic and Efficient Algorithm[J]. Journal of Statistical Structure of Networks Based on Vertex-vertex Correlations[J] Mechanics, 2004. P10012 Joumal of Statistical Mechanics: Theory and Experiment, 2009 [15] Capocci A, Servedio V D P, Caldarelli G, et al. Detecting rge Networks [J]. Physica A: Statistical [27] Lancichinetti A, Fortunato S, Kertesz J. Detecting the Overlapping Mechanics and Its Applications, 2005, 352(2-4):669-676 and Hierarchical Commumity Structure in Complex Networks[J] [16] Rosvall M, Bergstrom C T. Maps of Random Walks on Complex New Joumal of Physics, 2009, 11: 033015 Networks Reveal Community Structure [J]. Proc Natl Acad Sci [28] Chen D, Shang M, Lv Z, et al. Detecting Overlapping Communities SA,2008,105(4):1118-1123 of Weighted Networks Via a Local Algprithm [J]. Physica A [17] Lancichinetti A, Fortunato S. Community Detection Algorithms Statistical Mechanics and its Applications, 2010, 389(19): 4177 A Comparative Analysis[J]. Physical Review E, 2009, 80(5) 056117 [29] Shang M S, et al. Detecting Overlapping Communities Based [18] Raghavan U N, Albert R, Kummara S. Near Linear Time Algorithm to Commumity Cores in Complex Networks[J]. Chinese Physics etect Commmunity Structures in Large-scale Networks[J]. Phys Rev 27( E,2007,76(3):036106 [30] Newman M E, Leicht E A. Mixture Models and Exploratory analysis [19] Leung I, Hui P, Lio P, et al. Towards Real-time Communit in Networks[J]. Proc Natl Acad Sci USA, 2007, 104(23):9564 Detection in Large Networks[J]. Physical Review E,2009,79 9569 [31] Exans T, Lanbiotte R. Line Graphs, Link Partitions, and Oerapping [20] Palla G, Derenyi l, Farkas I, et al. Uncovering the Overlapping mmmities[]. Physical Review E, 2009, 80(1):16105 Community Structure of Complex Networks in Nature and Society [32] Ahn YY, Bagrow J P, Lehmann S. Link Communities Reveal J. Nature,2005,435(7043):814-818. Multiscale Complexity in Networks[J]. Nature, 2010, 466: [21]Kumpula J M, Kivela M, Kaski K, et al. Sequential Algorithm for Fast Clique Percolation [J]. Physical Review E,2008,78
０２７１０４． ［９］ ＡｇａｒｗａｌＧ，ＫｅｍｐｅＤ．ＭｏｄｕｌａｒｉｔｙｍａｘｉｍｉｚｉｎｇＧｒａｐｈＣｏｍｍｕｎｉｔｉｅｓ ＶｉａＭａｔｈｅｍａｔｉｃａｌＰｒｏｇｒａｍｍｉｎｇ［Ｊ］．ＴｈｅＥｕｒｏｐｅａｎＰｈｙｓｉｃａｌＪｏｕｒｎａｌ ＢＣｏｎｄｅｎｓｅｄＭａｔｔｅｒａｎｄＣｏｍｐｌｅｘＳｙｓｔｅｍｓ，２００８，６６（３）：４０９－ ４１８． ［１０］ ＦｏｒｔｕｎａｔｏＳ，ＢａｒｔｈｅｌｅｍｙＭ．ＲｅｓｏｌｕｔｉｏｎＬｉｍｉｔｉｎＣｏｍｍｕｎｉｔｙ Ｄｅｔｅｃｔｉｏｎ［Ｊ］．ＰＮａｔｌＡｃａｄＳｃｉＵＳＡ，２００７，１０４（１）：３６－４１． ［１１］ ＲｏｓｖａｌｌＭ，ＢｅｒｇｓｔｒｏｍＣＴ．ＡｎＩｎｆｏｒｍａｔｉｏｎｔｈｅｏｒｅｔｉｃＦｒａｍｅｗｏｒｋ ｆｏｒＲｅｓｏｌｖｉｎｇＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ［Ｊ］．Ｐ ＮａｔｌＡｃａｄＳｃｉＵＳＡ，２００７，１０４（１８）：７３２７－７３３１． ［１２］ ＲｕａｎＪＨ，ＺｈａｎｇＷ Ｘ．ＩｄｅｎｔｉｆｙｉｎｇＮｅｔｗｏｒｋＣｏｍｍｕｎｉｔｉｅｓｗｉｔｈａ ＨｉｇｈＲｅｓｏｌｕｔｉｏｎ［Ｊ］．ＰｈｙｓＲｅｖＥ，２００８，７７（１）：０１６１０４． ［１３］ ＬｉＺ，ＺｈａｎｇＳ，ＷａｎｇＲＳ，ｅｔａｌ．ＱｕａｎｔｉｔａｔｉｖｅＦｕｎｃｔｉｏｎｆｏｒ ＣｏｍｍｕｎｉｔｙＤｅｔｅｃｔｉｏｎ［Ｊ］．ＰｈｙｓＲｅｖＥＳｔａｔＮｏｎｌｉｎＳｏｆｔＭａｔｔｅｒ Ｐｈｙｓ，２００８，７７（３）：０３６１０９． ［１４］ ＤｏｎｅｔｔｉＬ，ＭｕｎｏｚＭ．ＤｅｔｅｃｔｉｎｇＮｅｔｗｏｒｋＣｏｍｍｕｎｉｔｉｅｓ：ＡＮｅｗ ＳｙｓｔｅｍａｔｉｃａｎｄＥｆｆｉｃｉｅｎｔＡｌｇｏｒｉｔｈｍ［Ｊ］．ＪｏｕｒｎａｌｏｆＳｔａｔｉｓｔｉｃａｌ Ｍｅｃｈａｎｉｃｓ，２００４，Ｐ１００１２． ［１５］ ＣａｐｏｃｃｉＡ，ＳｅｒｖｅｄｉｏＶＤＰ，ＣａｌｄａｒｅｌｌｉＧ，ｅｔａｌ．Ｄｅｔｅｃｔｉｎｇ ＣｏｍｍｕｎｉｔｉｅｓｉｎＬａｒｇｅＮｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓｉｃａＡ： Ｓｔａｔｉｓｔｉｃａｌ ＭｅｃｈａｎｉｃｓａｎｄＩｔｓＡｐｐｌｉｃａｔｉｏｎｓ，２００５，３５２（２－４）：６６９－６７６． ［１６］ ＲｏｓｖａｌｌＭ，ＢｅｒｇｓｔｒｏｍＣＴ．ＭａｐｓｏｆＲａｎｄｏｍＷａｌｋｓｏｎＣｏｍｐｌｅｘ ＮｅｔｗｏｒｋｓＲｅｖｅａｌＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅ［Ｊ］．ＰｒｏｃＮａｔｌＡｃａｄＳｃｉ ＵＳＡ，２００８，１０５（４）：１１１８－１１２３． ［１７］ ＬａｎｃｉｃｈｉｎｅｔｔｉＡ，ＦｏｒｔｕｎａｔｏＳ．ＣｏｍｍｕｎｉｔｙＤｅｔｅｃｔｉｏｎＡｌｇｏｒｉｔｈｍｓ： ＡＣｏｍｐａｒａｔｉｖｅＡｎａｌｙｓｉｓ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００９，８０（５）： ０５６１１７． ［１８］ ＲａｇｈａｖａｎＵＮ，ＡｌｂｅｒｔＲ，ＫｕｍａｒａＳ．ＮｅａｒＬｉｎｅａｒＴｉｍｅＡｌｇｏｒｉｔｈｍｔｏ ＤｅｔｅｃｔＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｓｉｎＬａｒｇｅｓｃａｌｅＮｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓＲｅｖ Ｅ，２００７，７６（３）：０３６１０６． ［１９］ ＬｅｕｎｇＩ，ＨｕｉＰ，ＬｉｏＰ，ｅｔａｌ．ＴｏｗａｒｄｓＲｅａｌｔｉｍｅＣｏｍｍｕｎｉｔｙ ＤｅｔｅｃｔｉｏｎｉｎＬａｒｇｅＮｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００９，７９ （６）：６６１０７． ［２０］ ＰａｌｌａＧ，ＤｅｒｅｎｙｉＩ，ＦａｒｋａｓＩ，ｅｔａｌ．ＵｎｃｏｖｅｒｉｎｇｔｈｅＯｖｅｒｌａｐｐｉｎｇ ＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｏｆＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓｉｎＮａｔｕｒｅａｎｄＳｏｃｉｅｔｙ ［Ｊ］．Ｎａｔｕｒｅ，２００５，４３５（７０４３）：８１４－８１８． ［２１］ ＫｕｍｐｕｌａＪＭ，ＫｉｖｅｌＭ，ＫａｓｋｉＫ，ｅｔａｌ．ＳｅｑｕｅｎｔｉａｌＡｌｇｏｒｉｔｈｍ ｆｏｒＦａｓｔＣｌｉｑｕｅＰｅｒｃｏｌａｔｉｏｎ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００８，７８ （２）：０２６１０９． ［２２］ ＺｈａｎｇＳＨ，ＮｉｎｇＸＭ，ＺｈａｎｇＸＳ．ＩｄｅｎｔｉｆｉｃａｔｉｏｎｏｆＦｕｎｃｔｉｏｎａｌ ＭｏｄｕｌｅｓｉｎａＰＰＩＮｅｔｗｏｒｋＢｙＣｌｉｑｕｅＰｅｒｃｏｌａｔｉｏｎＣｌｕｓｔｅｒｉｎｇ［Ｊ］． ＣｏｍｐｕｔＢｉｏｌＣｈｅｍ，２００６，３０（６）：４４５－４５１． ［２３］ ＺｈａｎｇＳ，ＷａｎｇＲ，ＺｈａｎｇＸ．ＩｄｅｎｔｉｆｉｃａｔｉｏｎｏｆＯｖｅｒｌａｐｐｉｎｇ ＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓＵｓｉｎｇＦｕｚｚｙＣｍｅａｎｓ Ｃｌｕｓｔｅｒｉｎｇ［Ｊ］． Ｐｈｙｓｉｃａ Ａ： ＳｔａｔｉｓｔｉｃａｌＭｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，３７４（１）：４８３－４９０． ［２４］ ＤｉｎｇＦ，ＬｕｏＺ，ＳｈｉＪ，ｅｔａｌ．ＯｖｅｒｌａｐｐｉｎｇＣｏｍｍｕｎｉｔｙＤｅｔｅｃｔｉｏｎ ＢｙＫｅｒｎｅｌｂａｓｅｄＦｕｚｚｙＡｆｆｉｎｉｔｙＰｒｏｐａｇａｔｉｏｎ［Ｃ］??Ｐｒｏｃｅｅｄｉｎｇｓｏｆ ｔｈｅ２ｎｄ ＩｎｔｅｒｎａｔｉｏｎａｌＷｏｒｋｓｈｏｐ ｏｎ ＩｎｔｅｌｌｉｇｅｎｔＳｙｓｔｅｍｓａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ（ＩＳＡ’２０１０），Ｗｕｈａｎ，Ｃｈｉｎａ，２０１０． ［２５］ ＺｈａｎｇＳ，ＷａｎｇＲＳ，ＺｈａｎｇＸＳ．ＵｎｃｏｖｅｒｉｎｇＦｕｚｚｙＣｏｍｍｕｎｉｔｙ ＳｔｒｕｃｔｕｒｅｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓＲｅｖＥ，２００７，７６（４）： ０４６１０３． ［２６］ ＺａｒｅｉＭ，ＩｚａｄｉＤ，ＳａｍａｎｉＫＡ．ＤｅｔｅｃｔｉｎｇＯｖｅｒｌａｐｐｉｎｇＣｏｍｍｕｎｉｔｙ ＳｔｒｕｃｔｕｒｅｏｆＮｅｔｗｏｒｋｓＢａｓｅｄｏｎＶｅｒｔｅｘｖｅｒｔｅｘＣｏｒｒｅｌａｔｉｏｎｓ［Ｊ］． ＪｏｕｒｎａｌｏｆＳｔａｔｉｓｔｉｃａｌＭｅｃｈａｎｉｃｓ：ＴｈｅｏｒｙａｎｄＥｘｐｅｒｉｍｅｎｔ，２００９， Ｐ１１０１３． ［２７］ ＬａｎｃｉｃｈｉｎｅｔｔｉＡ，ＦｏｒｔｕｎａｔｏＳ，ＫｅｒｔｅｓｚＪ．ＤｅｔｅｃｔｉｎｇｔｈｅＯｖｅｒｌａｐｐｉｎｇ ａｎｄＨｉｅｒａｒｃｈｉｃａｌＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ［Ｊ］． ＮｅｗＪｏｕｒｎａｌｏｆＰｈｙｓｉｃｓ，２００９，１１：０３３０１５． ［２８］ ＣｈｅｎＤ，ＳｈａｎｇＭ，ＬｖＺ，ｅｔａｌ．ＤｅｔｅｃｔｉｎｇＯｖｅｒｌａｐｐｉｎｇＣｏｍｍｕｎｉｔｉｅｓ ｏｆＷｅｉｇｈｔｅｄＮｅｔｗｏｒｋｓＶｉａａＬｏｃａｌＡｌｇｏｒｉｔｈｍ［Ｊ］．ＰｈｙｓｉｃａＡ： ＳｔａｔｉｓｔｉｃａｌＭｅｃｈａｎｉｃｓａｎｄｉｔｓＡｐｐｌｉｃａｔｉｏｎｓ，２０１０，３８９（１９）：４１７７ －４１８７． ［２９］ ＳｈａｎｇＭＳ，ｅｔａｌ．ＤｅｔｅｃｔｉｎｇＯｖｅｒｌａｐｐｉｎｇＣｏｍｍｕｎｉｔｉｅｓＢａｓｅｄｏｎ ＣｏｍｍｕｎｉｔｙＣｏｒｅｓｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ［Ｊ］．ＣｈｉｎｅｓｅＰｈｙｓｉｃｓ Ｌｅｔｔｅｒｓ，２０１０，２７（５）：０５８９０１． ［３０］ ＮｅｗｍａｎＭＥ，ＬｅｉｃｈｔＥＡ．ＭｉｘｔｕｒｅＭｏｄｅｌｓａｎｄＥｘｐｌｏｒａｔｏｒｙＡｎａｌｙｓｉｓ ｉｎＮｅｔｗｏｒｋｓ［Ｊ］．ＰｒｏｃＮａｔｌＡｃａｄＳｃｉＵＳＡ，２００７，１０４（２３）：９５６４ －９５６９． ［３１］ ＥｖａｎｓＴ，ＬａｍｂｉｏｔｔｅＲ．ＬｉｎｅＧｒａｐｈｓ，ＬｉｎｋＰａｒｔｉｔｉｏｎｓ，ａｎｄＯｖｅｒｌａｐｐｉｎｇ Ｃｏｍｍｕｎｉｔｉｅｓ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００９，８０（１）：１６１０５． ［３２］ ＡｈｎＹＹ，ＢａｇｒｏｗＪＰ，ＬｅｈｍａｎｎＳ．ＬｉｎｋＣｏｍｍｕｎｉｔｉｅｓＲｅｖｅａｌ ＭｕｌｔｉｓｃａｌｅＣｏｍｐｌｅｘｉｔｙｉｎＮｅｔｗｏｒｋｓ［Ｊ］．Ｎａｔｕｒｅ，２０１０，４６６：７６１ －７６４． · ５２· 国 防 科 技 大 学 学 报 ２０１１年
