第3期 郑文萍，等：基于稠密子图的社区发现算法 ·427. 象。大量研究表明，复杂网络中存在着一种普遍特 面的性能表现。基于归属度的中心社区扩展策略也 征—社区结构。复杂网络中社区发现)不仅 将应用在CPM、k-dense等基于密度的图聚类算法 有助于深入研究整个网络的拓扑结构、功能模块以 中，对未聚类结点进一步处理，以提高聚类有效性。 及动力学特性，同时在生物蛋白质的性能与互作用 的分析6、社会组织结构的网络分析)、搜索引 1背景知识 擎[]及推荐系统[)等方面均有广泛的应用前景，因 通常，一个复杂网络可以表示为图G=(V,E), 此具有十分重要的理论意义和应用价值。 其中顶点集V={1,2,…,vn},n=V;边集E中每 目前，社区发现算法的研究主要分为基于图划 条边e,对应V中一对顶点(：，心)之间的连接关系， 分的聚类算法[1o)、基于谱分析的聚类算法[2]、基 m=IEI。顶点v的邻域Nc()={u|(v,u)∈E}, 于层次的聚类算法[)]和基于密度的聚类算法[) 表示图G中与顶点v相邻的顶点集合，简记为V,。 等。其中基于密度的聚类算法通过搜索网络中稠密 结点：的度记为k,。除非特别指明，以下仅考虑简 子图1能较好地发现网络中的功能模块，因此在社 区发现中得到了广泛应用。2005年，Palla等161提 单无向图，因此k.=NI。令UCV(G),用[U]G表 出派系过滤算法(clique percolation method,CPM), 示G的结点子集U的导出子图，在不发生混淆时， 首先挖掘网络中结点数大于k的所有派系（完全 记为[U]。记顶点子集[U]在G中的邻域为 图)，然后将重叠结点大于k-1的派系合并得到k Nc(U)={ulu∈Nc(x)Ax∈U}o 派系社区。2006年，Saito等[]提出k-dense子图结 在复杂网络中，图G的密度[20]记为De= 构，通过寻找网络中的k-dense结构进行社区检测。 m 2009年，Sun等18以CPM为基础，通过改进寻找派 n(n-1)2。可以看出，D。∈【0，]，当D。越趋近于 系的方法提高算法效率，提出迭代派系过滤算法 1,图G中的边数越多；当Dc=1时，图G为完全图。 iterative-clique percolation method,ICPM)2010 结点的点介数2B()可以用来度量结点 年，Liu等I]提出基于极大团的聚类算法(cluste- 在网络G中的重要性。如果一对结点(：，)间共 ring-based on maximal cliques,CMC),通过搜索网络 有L条不同的最短路径，其中有L()条经过 中的所有极大团，并依据相互连接度合并重叠率较 结点4，那么结点对结点对(：，)的贡献为 高的极大团得到网络的社区结构。由于这些算法要 搜索网络中的相对稠密子图来进行聚类，当网络中 L)/L0定义结点的点介数B(): 存在包含大量结点的稀疏子图时，这些结点可能最 B(u)= L两 (1)》 终成为未聚类结点，造成了聚类结果的不完全覆盖。 这些未聚类结点构成的稀疏子图可能具有某种功 通常一个结点的点介数越大，则该结点对网络 能，或者与某些稠密子图共同行使功能，因此需要对 结构的影响越大。点介数是网络中结点重要性度量 网络中的部分未聚类结点进行进一步分析，判断其 指标之一。 是否属于某一社区或形成新的社区。 针对基于密度算法中大量未聚类结点问题，提 2结点对社区的归属度定义 出一种基于稠密子图的社区发现算法(community 基于密度的图聚类算法中可能存在大量不属于 detection based on dense subgraphs,BDSG)。首先通 任何已有社区的未聚类结点，为了将这些结点聚类 过搜索网络中的相对稠密子图得到中心社区：对于 到合适的社区，需要定义未聚类结点和社区的关联 未聚类结点，定义了结点v对社区C的归属度b(, 强度，称为结点v对于社区C的归属度b(v,C)。归 C)来度量结点和社区的连接倾向程度：基于归属 属度的定义对聚类结果的影响至关重要，结点，对 度，给出一种中心社区扩展策略(core community ex- 于社区C的归属度越大，则结点属于社区C的可 tended strateg罗，CE),对未聚类结点进一步处理。 BDSG算法中，一个结点可能属于多个社区，是一种 能性越大。 软聚类方法。通过在空手道俱乐部、海豚社交网络、 Cui等2基于结点v与社区C关联边数定义了 大学生足球网络、电子邮件网络和合作网络5个真 结点对于社区C的归属度6，(，C)=N,nC,其 实网络上与CPM、k-dense算法进行比较，评估和分 k 析BDSG算法在未聚类结点分配和社区模块性等方 中N,∩C={ul(u,u)∈E,u∈C}表示结点v在社区象。 大量研究表明，复杂网络中存在着一种普遍特 征———社区结构［４］ 。 复杂网络中社区发现［５］ 不仅 有助于深入研究整个网络的拓扑结构、功能模块以 及动力学特性，同时在生物蛋白质的性能与互作用 的分析［６］ 、社会组织结构的网络分析［７］ 、 搜索引 擎［８］及推荐系统［９］等方面均有广泛的应用前景，因 此具有十分重要的理论意义和应用价值。 目前，社区发现算法的研究主要分为基于图划 分的聚类算法［１０⁃１１］ 、基于谱分析的聚类算法［１２］ 、基 于层次的聚类算法［１３］ 和基于密度的聚类算法［１４］ 等。 其中基于密度的聚类算法通过搜索网络中稠密 子图［１５］能较好地发现网络中的功能模块，因此在社 区发现中得到了广泛应用。 ２００５ 年，Ｐａｌｌａ 等［１６］ 提 出派系过滤算法（ ｃｌｉｑｕｅ ｐｅｒｃｏｌａｔｉｏｎ ｍｅｔｈｏｄ，ＣＰＭ）， 首先挖掘网络中结点数大于 ｋ 的所有派系（完全 图），然后将重叠结点大于 ｋ－１ 的派系合并得到 ｋ 派系社区。 ２００６ 年，Ｓａｉｔｏ 等［１７］ 提出 ｋ⁃ｄｅｎｓｅ 子图结 构，通过寻找网络中的 ｋ⁃ｄｅｎｓｅ 结构进行社区检测。 ２００９ 年，Ｓｕｎ 等［１８］以 ＣＰＭ 为基础，通过改进寻找派 系的方法提高算法效率，提出迭代派系过滤算法 （ ｉｔｅｒａｔｉｖｅ⁃ｃｌｉｑｕｅ ｐｅｒｃｏｌａｔｉｏｎ ｍｅｔｈｏｄ， ＩＣＰＭ ）。 ２０１０ 年，Ｌｉｕ 等［１９］ 提出基于极大团的聚类算法（ ｃｌｕｓｔｅ⁃ ｒｉｎｇ⁃ｂａｓｅｄ ｏｎ ｍａｘｉｍａｌ ｃｌｉｑｕｅｓ，ＣＭＣ），通过搜索网络 中的所有极大团，并依据相互连接度合并重叠率较 高的极大团得到网络的社区结构。 由于这些算法要 搜索网络中的相对稠密子图来进行聚类，当网络中 存在包含大量结点的稀疏子图时，这些结点可能最 终成为未聚类结点，造成了聚类结果的不完全覆盖。 这些未聚类结点构成的稀疏子图可能具有某种功 能，或者与某些稠密子图共同行使功能，因此需要对 网络中的部分未聚类结点进行进一步分析，判断其 是否属于某一社区或形成新的社区。 针对基于密度算法中大量未聚类结点问题，提 出一种基于稠密子图的社区发现算法（ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｄｅｎｓｅ ｓｕｂｇｒａｐｈｓ，ＢＤＳＧ）。 首先通 过搜索网络中的相对稠密子图得到中心社区；对于 未聚类结点，定义了结点 ｖ 对社区 Ｃ 的归属度 ｂ（ｖ， Ｃ）来度量结点和社区的连接倾向程度；基于归属 度，给出一种中心社区扩展策略（ｃｏｒｅ ｃｏｍｍｕｎｉｔｙ ｅｘ⁃ ｔｅｎｄｅｄ ｓｔｒａｔｅｇｙ， ＣＥ），对未聚类结点进一步处理。 ＢＤＳＧ 算法中，一个结点可能属于多个社区，是一种 软聚类方法。 通过在空手道俱乐部、海豚社交网络、 大学生足球网络、电子邮件网络和合作网络 ５ 个真 实网络上与 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 算法进行比较，评估和分 析 ＢＤＳＧ 算法在未聚类结点分配和社区模块性等方 面的性能表现。 基于归属度的中心社区扩展策略也 将应用在 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 等基于密度的图聚类算法 中，对未聚类结点进一步处理，以提高聚类有效性。 １ 背景知识 通常，一个复杂网络可以表示为图 Ｇ ＝ (Ｖ，Ｅ) ， 其中顶点集 Ｖ ＝ ｖ１ ，ｖ２ ，…，ｖｎ { } ，ｎ ＝ Ｖ ；边集 Ｅ 中每 条边 ｅｉ，ｊ对应 Ｖ 中一对顶点（ｖｉ，ｖｊ）之间的连接关系， ｍ ＝ ｜ Ｅ ｜ 。 顶点 ｖ 的邻域 ＮＧ (ｖ) ＝ {ｕ ｜ (ｖ，ｕ) ∈ Ｅ} ， 表示图 Ｇ 中与顶点 ｖ 相邻的顶点集合，简记为 Ｎｖ。 结点 ｖ 的度记为 ｋｖ。 除非特别指明，以下仅考虑简 单无向图，因此 ｋｖ ＝｜ Ｎｖ ｜ 。 令 Ｕ⊆Ｖ(Ｇ) ，用 [Ｕ] Ｇ 表 示 Ｇ 的结点子集 Ｕ 的导出子图，在不发生混淆时， 记为 [Ｕ] 。 记 顶 点 子 集 [Ｕ] 在 Ｇ 中 的 邻 域 为 ＮＧ（Ｕ）＝ ｛ｕ ｜ ｕ∈ＮＧ (ｘ) ∧ｘ∈Ｕ｝。 在复 杂 网 络 中， 图 Ｇ 的 密 度［２０］ 记 为 ＤＧ ＝ ｍ ｎ(ｎ－１) ／ ２ 。 可以看出，ＤＧ∈ [０，１] ，当 ＤＧ 越趋近于 １，图 Ｇ 中的边数越多；当 ＤＧ ＝ １ 时，图 Ｇ 为完全图。 结点 ｖｋ 的点介数［２１］Ｂ ｖｋ ( ) 可以用来度量结点 ｖｋ 在网络 Ｇ 中的重要性。 如果一对结点（ ｖｉ，ｖｊ ） 间共 有 Ｌｖｉ ，ｖｊ条不同的最短路径，其中有 Ｌｖｉ ，ｖｊ ｖｋ ( ) 条经过 结点 ｖｋ，那么结点 ｖｋ 对结点对 （ ｖｉ， ｖｊ ） 的贡献为 Ｌｖｉ ，ｖｊ ｖｋ ( ) ／ Ｌｖｉ ，ｖｊ 。 定义结点 ｖｋ 的点介数 Ｂ ｖｋ ( ) ： Ｂ ｖｋ ( ) ＝ ∑ ｎ ｉ ＝ １ ∑ ｎ ｊ ＝ ｉ＋１ Ｌｖｉ ，ｖｊ ｖｋ ( ) Ｌｖｉ ，ｖｊ （１） 通常一个结点的点介数越大，则该结点对网络 结构的影响越大。 点介数是网络中结点重要性度量 指标之一。 ２ 结点对社区的归属度定义 基于密度的图聚类算法中可能存在大量不属于 任何已有社区的未聚类结点，为了将这些结点聚类 到合适的社区，需要定义未聚类结点和社区的关联 强度，称为结点 ｖ 对于社区 Ｃ 的归属度 ｂ（ｖ，Ｃ）。 归 属度的定义对聚类结果的影响至关重要，结点 ｖ 对 于社区 Ｃ 的归属度越大，则结点 ｖ 属于社区 Ｃ 的可 能性越大。 Ｃｕｉ 等［２２］基于结点 ｖ 与社区 Ｃ 关联边数定义了 结点 ｖ 对于社区 Ｃ 的归属度 ｂｐ（ｖ，Ｃ）＝ Ｎｖ∩Ｃ ｋｖ ，其 中 Ｎｖ∩Ｃ ＝ {ｕ ｜ (ｖ，ｕ) ∈Ｅ，ｕ∈Ｃ} 表示结点 ｖ 在社区 第 ３ 期 郑文萍，等：基于稠密子图的社区发现算法 ·４２７·