骆志刚等:复杂网络社团发现算法研究新进展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值最大的最大等价于求条件信息 Ｈ（Ｘ｜Ｙ）最小，Ｒｏｓｖａｌｌ等 给出了条件信息的量化表示并运用模拟退火优化 算法进行求解，可实现上千个节点的网络社团发 现。测试表明，对于社团大小及边密度不一的社 团发现问题，该发现算法要明显优于基于模块度 优化的社团发现算法。后来，Ｒｏｓｖａｌｌ等进一步以 描述图中信息的扩散过程为目标［１６］ ，将问题转换 为寻找描述网络上随机游走的有效编码方式，使 该方法更适合于捕捉社团内部节点之间的长程相 关性，已有文献测试表明该方法是目前非重叠社 团发现算法里准确度最高的一类方法［１７］ 。 图 １ 从信息论的角度看社团发现［１１］ Ｆｉｇ．１ Ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｆｒｏｍｔｈｅｖｉｅｗｏｆ ｉｎｆｏｒｍａｔｉｏｎｔｈｅｏｒｙ ［１１］ １４ 基于标号传播的社团发现算法 很多情况下，复杂网络的边表示的是个体之 间的信息传播，其传播的结果通常是使得社团内 部节点之间共享相同的信息。Ｒａｇｈａｖａｎ等［１８］基 于该思想提出一种快速的标号传播算法（简称为 ＬＰＡ算法）。如图 ２所示，ＬＰＡ算法首先为每个节 点指派唯一标号，在每一步迭代中，每个节点将自 身标号更新为其邻节点出现次数最多的标号，如 果存在多个相同的最多标号，则随机选择一个作 为更新值，若干次迭代后密集相连的节点会收敛 于同一标号，最终，具有相同标号的节点归为一个 社团。 图 ２ 标号传播过程示意［１８］ Ｆｉｇ．２ Ｔｈｅｐｒｏｃｅｓｓｏｆｌａｂｅｌｐｒｏｐａｇａｔｉｏｎ ［１８］ ＬＰＡ算法最大的优点在于不需要任何参数输 入，比如社团的数目、大小等，而且算法具有线性 的时间复杂度为 Ｏ（ｍ），ｍ为网络的边数，收敛速 度非常快，可适用于规模较大的复杂网络。随后， Ｌｅｕｎｇ等对标号更新规则进行了改进［１９］ 。在 ＬＰＡ 迭代过程中引入衷减因子，每次迭代由衷减因子、 边权重、偏好特征决定更新的标号，同时增加标号 更新的选择性，比如共享最大标号的邻居少于某 个比例时才进行更新，降低了计算开销。 ２ 重叠社团发现算法 前面所介绍的非重叠社团发现方法把每个节 点严格地划分到某个社团中，而真实世界中这种 硬划分并不能真正反应节点和社团的实际关系， 例如蛋白质相互作用网络中由于蛋白质功能的多 样性，单个蛋白质在不同的时空条件下参与不同 的功能模块中。同样的现象普遍存在于各种真实 网络之中，如社会网络中的人属于多个集体、网络 中的网页属于多个主题等。因此，重叠社团发现 更符合真实世界的社团组织规律，成为近几年社 团发现研究的新热点，涌现出许多新颖算法。 ２１ 基于团渗透改进的重叠社团发现算法 由 Ｐａｌｌａ等［２０］ 提出的团渗透算法是首个能够 发现重叠社团的算法，文献［２］中已对其进行详细 介绍。该类算法认为社团是由一系列相互可达的 ｋ－团（即大小为 ｋ的完全子图）组成的，即 ｋ－社 团。算法通过合并相邻的 ｋ－团来实现社团发 现，而那些处于多个 ｋ－社团中的节点即是社团 的“重叠”部分。 Ｋｕｍｐｕｌａ等在前人工作基础上进一步提出一 种快速团渗透算法（ＳＣＰ算法）［２１］ 。该算法分两阶 段进行，第一阶段将网络的边按顺序（如加权网络 按权值大小顺序）插入到网络中，并同时检测出现 的 ｋ－团；第二阶段将检测的 ｋ－团，根据是否与 已有 ｋ－社团相邻，并入 ｋ－社团或形成新的 ｋ－ 社团。由于边插入的顺序性，在第二阶段检测时 ＳＣＰ算法只需依次对 ｋ－团进行局部判断；而且 ＳＣＰ算法能够在一遍运行中检测不同权重阈值下 的 ｋ－社团，较大地提高了团渗透算法的计算速 度。 基于团渗透思想的算法需要以团为基本单元 来发现重叠，这对于很多真实网络尤其是稀疏网 络而言，限制条件过于严格，只能发现少量的重叠 社团［２２］ 。 ２２ 基于模糊聚类的重叠社团发现算法 另一观点认为可将重叠社团发现归于传统模 糊聚类问题加以解决，以计算节点到社团的模糊 隶属度来揭示节点的社团关系。这类算法通常从 构建节点距离出发，再结合传统模糊聚类求解隶 属度矩阵。 张世华等首先应用这一思想［２３］ ，他们结合谱 分析方法将网络中的节点近似映射到欧拉空间中 的数据点，进而利用 ＦＣＭ算法对空间中的数据点 进行聚类，从而得到节点与社团之间的隶属度矩 阵。由于模糊聚类算法 ＦＣＭ本身要求预先知道 社团数，该算法在模块度 Ｑ值的基础上引入新的 模块度指标模糊模块度珟Ｑ，选取使得珟Ｑ值最大的 第 １期 骆志刚，等：复杂网络社团发现算法研究新进展 · ４９·