国防科技大学学报 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)型代表算法有 Ｎｅｗｍａｎ快速算法［４］ 、ＣＮＭ算法［５］ 和 ＭＳＧＭＶ算法［６］等。Ｎｅｗｍａｎ快速算法将每个 节点看作是一个社团，每次迭代选择产生最大 Ｑ 值的两个社团合并，直至整个网络融合成一个社 团。整个过程可表示成一个树状图，从中选择 Ｑ 值最大的层次划分得到最终的社团结构。该算法 的总体时间复杂度为 Ｏ（ｍ（ｍ＋ｎ））。在 Ｎｅｗｍａｎ 快速算法的基础上，ＣＮＭ算法采用堆数据结构来 计算和更新网络的模块度，大大提高了计算速度； ＭＳＧＭＶ算法则引入多步扩展，迭代过程中每次 可合并多对社团以避免过早地收缩到少数较大的 社团。 第二类算法主要采用分裂的思想，自顶向下 进行。例如，Ｎｅｗｍａｎ最早提出的 ＧＮ算法就属于 这类算法［１］ ，算法通过依次删去网络中边介数（即 网络中经过每条边的最短路径数）最大的边，直至 每个节点单独退化为社团，然后从整个删边过程 中选取对应最大 Ｑ值时的结果。该算法复杂度 较高，为 Ｏ（ｎ３）。随后，Ｎｅｗｍａｎ等人通过定义模 块度矩阵，将模块度用矩阵的特征向量表示，提出 一种用于划分网络社团结构的谱方法［７］ 。该算法 通过求解模块度矩阵的最大正特征值以及对应的 特征向量，依据特征向量中元素的符号将网络不 断递归二分，直至子网络再细分已不能增大 Ｑ 值。整个算法的平均时间复杂度为，较 ＧＮ算法 在计算速度和准确度上均有较大提高。 第三类算法则是直接寻优法，如 Ｄｕｃｈ等提出 的 ＥＯ算法［８］以及 Ａｇａｒｗａｌ等提出的整数规划方 法［９］ 。ＥＯ算法的思想是将每个节点对模块度 Ｑ 值的贡献大小定义为局部变量，然后在随机初始 划分的基础上，通过贪婪策略调整局部变量（具有 最小贡献度的变量）来提高全局目标函数 Ｑ值。 整数规划方法则通过求解对应的松弛线性规划问 题能够给出最大模块度的一个上界，这是以前方 法所不具备的。此外，还有一些基于遗传算法、蚁 群算法等智能算法的社团发现算法也可归为此 类。 近年来越来越多的研究发现：模块度优化方 法无法发现小于一定粒度的社团［１０－１１］ 。在实际 网络中，尤其是大规模网络中，社团的大小不一， 该问题尤为突出。为此，研究者们提出一些局部 调整策略。如 Ｒｕａｎ等［１２］ 结合谱平分法和局部搜 索方法提出的 ＨＱｃｕｔ算法，在分裂网络前增加统 计测试来判断是否需进一步细分。此外，部分研 究者提出新的模块度来避免 Ｑ值存在的粒度问 题。如李珍萍等［１３］ 提出的模块度 Ｄ值，在衡量社 团内外连接度的差异时，引入了社团大小作为分 母进行平均，从理论和数值试验上证明了作为模 块度 Ｄ值要优于 Ｑ值。 总的来说，模块度优化算法是目前应用最为 广泛的一类算法，但是在具体分析中，很难确定一 种合理的优化目标，使得分析结果难以反应真实 的社团结构，尤其是分析大规模复杂网络时，搜索 空间非常大，使得许多模块度近似优化算法的结 果变得更不可靠。 １２ 基于谱分析的社团发现算法 谱分析法建立在谱图理论基础上，其主要思 想是根据特定图矩阵的特征向量导出对象的特 征，利用导出特征来推断对象之间的结构关系。 通常选用的特定图矩阵有拉普拉斯矩阵和随机矩 阵两类。图的拉普拉斯矩阵定义为 Ｌ＝Ｄ－Ｗ， 其中 Ｄ为以每个节点的度为对角元的对角矩阵， Ｗ 为图的邻接矩阵；随机矩阵则是根据邻接矩阵 导出的概率转移矩阵 Ｐ＝Ｄ－１Ｗ。这两类矩阵有 一个共同性质，同一社团节点对应的特征分量近 似相等，这成为目前谱分析方法实现社团发现的 理论基础。 基于谱分析的社团发现算法普遍做法是将节 点对应的矩阵特征分量看作空间坐标，将网络节 点映射到多维特征向量空间中，运用传统的聚类 方法将节点聚成社团。例如，Ｄｏｎｅｔｔｉ等［１４］基于节 点之间的距离度量，在不同维度的特征空间中建 立聚类树图，从中选择全局模块度最大的划分作 为社团发现结果。Ｃａｐｏｃｃｉ等［１５］则基于同一社团 的节点对应的随机矩阵特征分量强相关这一性质 提出计算特征向量的 Ｐｅａｒｓｏｎ相关系数来度量节 点之间的相似度。 应用谱分析法不可避免地要计算矩阵特征 值，计算开销大，但由于能够通过特征谱将节点映 射至欧拉空间，并能够直接应用传统向量聚类的 众多研究成果，灵活性较大。 １３ 基于信息论的社团发现算法 从信息论的角度出发，Ｒｏｓｖａｌｌ等［１１］把网络的 模块化描述看作对网络拓扑结构的一种有损压 缩，从而将社团发现问题转换为信息论中的一个 基础问题：寻找拓扑结构的有效压缩方式。如图 １所示，原拓扑结构 Ｘ通过编码器产生模块描述 Ｙ，解码器对 Ｙ进行解码，推测出原结构 Ｚ，那么 何种模块描述 Ｙ是最优的？以信息论的观点来 看，互信息 Ｉ（Ｘ，Ｙ）最大时，即最能反应原始结构 Ｘ的 Ｙ是最优的。在该框架下，互信息 Ｉ（Ｘ，Ｙ） · ４８· 国 防 科 技 大 学 学 报 ２０１１年