骆志刚等:复杂网络社团发现算法研究新进展 (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)＝∑ｉ ｌｎπｇｉ ＋∑ ｊ Ａｉｊｌｎθｇｉ [ ，ｊ] 通过简单变形后可直接运用 ＥＭ算法进行求 解。由于该算法未对社团结构作过多假设，具有 较强的灵活性，能够发现不同结构类型的社团，如 具有二分结构的社团，这是之前方法所不具备的。 同时所求得的参数θｒｉ中暗含了节点 ｉ到社团 ｒ的 隶属程度，因此，通过该算法能够识别出重叠社 团，并得到隶属程度大小。然而，该方法基于 ＥＭ 算法来估计未知参数，收敛速度较慢，计算复杂度 较高，一定程度上制约了算法的应用规模。 ２６ 基于边聚类的重叠社团发现 以往社团发现算法的研究均以节点为对象， 考虑如何通过划分、聚类、优化等技术将节点归为 重叠或不重叠的社团。最近，Ｅｖａｎｓ等［３１］和 Ａｈｎ 等［３２］ 分别发表了以边为研究对象来划分社团。 虽然节点属于多重社团，但边通常只对应某一特 定类型的交互（真实网络中的某种性质或功能）。 因此，以边为对象使得划分的结果更能真实地反 映节点在复杂网络中的角色或功能。文献［３１－ ３２］虽然都是对边进行聚类来提示重叠社团，但在 处理方式上有所不同。 文献［３１］将原网络转换为加权线图，即原网 络中的边映射为线图中的节点，线图中的节点存 在边当且仅当原网络中所对应的边存在共享节 点，而边权值等于 １?（ｋ－１），其中 ｋ为共享节点 的度。通过网络的转换，最大的好处是可以直接 应用非重叠社团发现算法来提示网络的重叠社 团。 文献［３２］则着重解决社团的重叠性与层次性 之间的冲突，提出边社团的概念，即将社团看作是 紧密相连的边集合。作者在定义边间相似度的基 础上，采用层次聚类建立聚类树状图。由于每个 节点拥有一条到多条边，每条边存在于一个边社 团中，因此对该树状图不同层次的切割得到的社 团结构对应着不同层次的重叠社团。 ３ 总结与展望 从异常复杂的网络解构出其中的社团结构， 已成为当今复杂系统研究领域一项具有挑战性的 研究课题。虽然该课题近些年受到广泛关注，涌 现出一批新颖的算法，但目前相关研究仍未形成 统一的框架和度量标准，尤其是重叠社团发现算 法的研究，尚存许多问题丞待解决。我们认为，复 杂网络社团发现的进一步研究可从以下几个方面 展开。 （１）建立统一的度量标准。由于复杂网络的 类型众多，连接规律各有不同，很难以社团结构的 某种统一的模块度（如 Ｑ值）来刻画社团发现算 法的优劣。一种更为科学的方式是建立一套包含 多种复杂网络的统一标准测试集，以评判算法在 不同类型网络中的优劣，明确算法的适用范围。 （２）适用于大规模复杂网络的社团发现算法。 复杂网络的规模越来越大，对算法的计算复杂度 提出了更高要求。虽然在不考虑重叠社团的情况 下，已出现一些接近于线性时间复杂度的算法，但 这些算法通常采用较为激进的贪婪策略，网络规 模变大且非稀疏时，其结果变得不可靠。在重叠 社团发现算法中，很多算法需要通过多次计算来 获得最佳的社团数，计算开销过大。因此，考虑复 杂网络社团密度不均的特点，从局部社团出发研 究网络的社团结构是未来的重要研究方向之一。 此外，设计适合于大规模网络分析的高效并行算 法也是未来重要的研究方向之一。 （３）重叠社团与层次社团的结合。一般认为， 社团之间共享部分边缘节点从而产生重叠社团， 然而重叠社团结构远比想象的要复杂。实际上， 除了重叠性，层次性也是社团结构的另一大特性。 例如，第 ｉ层中的中心节点，可能在第 ｊ层中就变 成了边缘节点。可见，重叠性与层次性两者联系 十分紧密，有必要将两者融和在一起来解构复杂 网络。在目前的众多方法中，唯有边社团给出了 社团重叠性和层次性普遍并存的合理解释，未来 以边为对象来研究网络社团结构将是一个值得深 入研究的方向。 参 考 文 献： ［１］ ＧｉｒｖａｎＭ，ＮｅｗｍａｎＭ ＥＪ．ＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＳｏｃｉａｌａｎｄ ＢｉｏｌｏｇｉｃａｌＮｅｔｗｏｒｋｓ［Ｊ］．ＰＮａｔｌＡｃａｄＳｃｉＵＳＡ，２００２，９９（１２）： ７８２１－７８２６． ［２］ 解亻刍，汪小帆．复杂网络中的社团结构分析算法研究综述 ［Ｊ］．复杂系统与复杂性科学，２００５，２（３）：１２． ［３］ 李晓佳，张鹏，狄增如，等．复杂网络中的社团结构［Ｊ］．复 杂系统与复杂性科学，２００８，５（３）：２４． ［４］ ＮｅｗｍａｎＭＥＪ．ＦａｓｔＡｌｇｏｒｉｔｈｍｆｏｒＤｅｔｅｃｔｉｎｇＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅ ｉｎＮｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓＲｅｖＥ，２００４，６９（６）：０６６１３３． ［５］ ＣｌａｕｓｅｔＡ．ＦｉｎｄｉｎｇＬｏｃａｌＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＮｅｔｗｏｒｋｓ［Ｊ］． ＰｈｙｓＲｅｖＥ，２００５，７２（２）：０２６１３２． ［６］ ＳｃｈｕｅｔｚＰ，ＣａｆｌｉｓｃｈＡ．ＭｕｌｔｉｓｔｅｐＧｒｅｅｄｙＡｌｇｏｒｉｔｈｍＩｄｅｎｔｉｆｉｅｓＣｏｍｍｕｎｉｔｙ ＳｔｒｕｃｔｕｒｅｉｎＲｅａｌｗｏｒｌｄａｎｄＣｏｍｐｕｔｅｒｇｅｎｅｒａｔｅｄＮｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓＲｅｖ Ｅ，２００８，７８（２）：０２６１１２． ［７］ ＮｅｗｍａｎＭＥＪ．ＭｏｄｕｌａｒｉｔｙａｎｄＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｉｎＮｅｔｗｏｒｋｓ ［Ｊ］．ＰｒｏｃＮａｔｌＡｃａｄＳｃｉＵＳＡ，２００６，１０３（２３）：８５７７－８５８２． ［８］ ＤｕｃｈＪ，ＡｒｅｎａｓＡ．ＣｏｍｍｕｎｉｔｙＤｅｔｅｃｔｉｏｎｉｎＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ ＵｓｉｎｇＥｘｔｒｅｍａｌＯｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．ＰｈｙｓＲｅｖＥ，２００５，７２（２）： 第 １期 骆志刚，等：复杂网络社团发现算法研究新进展 · ５１·