近年来，对各种复杂网络的研究是许多领域的研究热点之一^[1,2,3]，如生物网络、社交网络、电子邮件网络、引文网络等已成为众多学者的主要研究对象。大量研究表明，复杂网络中存在着一种普遍特征——社区结构^[4]。复杂网络中社区发现^[5]不仅有助于深入研究整个网络的拓扑结构、功能模块以及动力学特性，同时在生物蛋白质的性能与互作用的分析^[6]、社会组织结构的网络分析^[7]、搜索引擎^[8]及推荐系统^[9]等方面均有广泛的应用前景，因此具有十分重要的理论意义和应用价值。

目前，社区发现算法的研究主要分为基于图划分的聚类算法^{[10, 11]}、基于谱分析的聚类算法^[12]、基于层次的聚类算法^[13]和基于密度的聚类算法^[14]等。其中基于密度的聚类算法通过搜索网络中稠密子图^[15]能较好地发现网络中的功能模块，因此在社区发现中得到了广泛应用。2005年，Palla等^[16]提出派系过滤算法(clique percolation method，CPM)，首先挖掘网络中结点数大于k的所有派系(完全图)，然后将重叠结点大于k-1的派系合并得到k派系社区。2006年，Saito等^[17]提出k-dense子图结构，通过寻找网络中的k-dense结构进行社区检测。2009年，Sun等^[18]以CPM为基础，通过改进寻找派系的方法提高算法效率，提出迭代派系过滤算法(iterative-clique percolation method，ICPM)。2010年，Liu等^[19]提出基于极大团的聚类算法(clustering-based on maximal cliques，CMC)，通过搜索网络中的所有极大团，并依据相互连接度合并重叠率较高的极大团得到网络的社区结构。由于这些算法要搜索网络中的相对稠密子图来进行聚类，当网络中存在包含大量结点的稀疏子图时，这些结点可能最终成为未聚类结点，造成了聚类结果的不完全覆盖。这些未聚类结点构成的稀疏子图可能具有某种功能，或者与某些稠密子图共同行使功能，因此需要对网络中的部分未聚类结点进行进一步分析，判断其是否属于某一社区或形成新的社区。

针对基于密度算法中大量未聚类结点问题，提出一种基于稠密子图的社区发现算法(community detection based on dense subgraphs，BDSG)。首先通过搜索网络中的相对稠密子图得到中心社区；对于未聚类结点，定义了结点 v对社区C的归属度b(v,C)来度量结点和社区的连接倾向程度；基于归属度，给出一种中心社区扩展策略 (core community extended strategy,CE)，对未聚类结点进一步处理。BDSG算法中，一个结点可能属于多个社区，是一种软聚类方法。通过在空手道俱乐部、海豚社交网络、大学生足球网络、电子邮件网络和合作网络 5个真实网络上与CPM、k-dense算法进行比较，评估和分析BDSG算法在未聚类结点分配和社区模块性等方面的性能表现。基于归属度的中心社区扩展策略也将应用在CPM、k-dense等基于密度的图聚类算法中，对未聚类结点进一步处理，以提高聚类有效性。

通常，一个复杂网络可以表示为图G=V,E，其中顶点集V=v₁,v₂,…,v_n，n=V；边集E中每条边e_i,j对应V中一对顶点(v_i,v_j)之间的连接关系，m=|E|。顶点v的邻域N_Gv=u|v,u∈E，表示图G中与顶点v相邻的顶点集合，简记为N_v。结点v的度记为k_v。除非特别指明，以下仅考虑简单无向图，因此k_v=|N_v|。令UVG，用UG表示G的结点子集U的导出子图，在不发生混淆时，记为U。记顶点子集U在G中的邻域为N_G(U)={u|u∈N_Gx∧x∈U}。

在复杂网络中，图G的密度^[20]记为 ${{D}_{G}}\in \frac{m}{n(n-1)/2}$。可以看出，D_G∈0,1，当D_G越趋近于1，图G中的边数越多；当D_G=1时，图G为完全图。

结点v_k的点介数^[21]Bv_k可以用来度量结点v_k在网络G中的重要性。如果一对结点(v_i,v_j)间共有L_vi,v_j条不同的最短路径，其中有L_vi,v_jv_k条经过结点v_k，那么结点v_k对结点对(v_i,v_j)的贡献为L_vi,v_jv_k/L_vi,v_j。定义结点v_k的点介数Bv_k：

通常一个结点的点介数越大，则该结点对网络结构的影响越大。点介数是网络中结点重要性度量指标之一。

基于密度的图聚类算法中可能存在大量不属于任何已有社区的未聚类结点，为了将这些结点聚类到合适的社区，需要定义未聚类结点和社区的关联强度，称为结点 v对于社区C的 归属度b(v,C)。归属度的定义对聚类结果的影响至关重要，结点v对于社区C的归属度越大，则结点v属于社区C的可能性越大。

Cui等^[22]基于结点v与社区C关联边数定义了结点v对于社区C的归属度${{b}_{p}}\left( v,C \right)=\frac{\left| {{N}_{v}}\cap c \right|}{{{k}_{v}}}$，其中N_v∩C=u|v,u∈E，u∈C表示结点v在社区C中相邻点的集合，k_v是结点v的度。然而结点v与社区C的关联强度不仅与关联边数有关，也和社区C中v的相邻点在C中的重要性关系密切。

如图 1所示，当前聚类结果得到两个社区C₁(▲)和C₂(■)，其余结点为未聚类结点。考虑结点v₉，可得b_p(v₉,C₁)=b_p(v₉,C₂)，N_v9∩C₁=v₃₃,v₃₄，且N_v9∩C₂=v₁,v₃。此时，社区C₁中与结点v₉相邻结点的点介数比例为$\frac{\sum\nolimits_{u\in \left\{ {{v}_{33}},{{v}_{34}} \right\}}{B\left( u \right)}}{\sum\nolimits_{w\in {{c}_{1}}}{B\left( w \right)}}=0.95$，而社区C₂中与结点v₉相邻结点的点介数比例为$\frac{\sum\nolimits_{u\in \left\{ {{v}_{1}},{{v}_{3}} \right\}}{B\left( u \right)}}{\sum\nolimits_{w\in {{c}_{2}}}{B\left( w \right)}}=0.83$。由于结点v₉在C₁中的相邻点在网络中重要性更高，可以认为v₉更倾向归属于社区C₁。

图 1 空手道俱乐部中未聚类结点分析 Fig. 1 The analysis of subordinate vertices in zacharys karate club

图选项

因此，度量未聚类结点和已有社区的归属度，需要综合考虑该结点与一个社区关联边数以及社区内该结点的相邻结点的重要性。为了更准确地表示未聚类结点和社区的关系，首先给出结点v对社区C的归属度定义：

基于稠密子图的社区发现算法(BDSG)主要由2部分构成：首先通过搜索网络中大于指定密度阈值d的稠密子图得到网络中心社区，确定聚类个数k，不属于任何一个中心社区的结点为未聚类结点；根据式(2)计算未聚类结点与已有社区的归属度，将一些未聚类结点划分到归属度大于指定阈值的社区中，对当前中心社区进行扩展；更新剩余未聚类结点的归属度，若网络中所有未聚类结点对任意社区的归属度都小于设定阈值，则算法结束。

首先，寻找网络中的子图密度大于指定阈值 d的所有稠密子图。图 2给出了d=0.9时，算法得到的4个稠密子图，分别记为U₁、U₂、U₃和U₄。

图 2 BDSG算法在空手道俱乐部中得到的稠密子图 Fig. 2 The dense subgraphs in zacharys karate club obtained by BDSG

图选项

然后，建立子图重叠矩阵 M，其中元素M_i,i=|V(U_i)|表示子图U_i中的顶点个数。元素M_i,i=VU_i∩VU_j，i≠j，表示子图U_i和U_j的公共顶点数。对2个不同稠密子图，若M_i,i> $\frac{\min \left( \left| {{U}_{i}} \right|,\left| {{U}_{j}} \right| \right)}{2} $，则合并2个子图为一个新社区U′=[V(U_i)∪VU_j]_G，此过程迭代进行，直到不产生新的社区。得到的社区称为初始中心社区，社区个数k为算法的聚类个数。图 2中4个稠密子图的重叠矩阵表示为

算法确定了聚类个数和初始中心社区数之后，不属于任何中心社区的结点就是未聚类结点。由于初始中心社区寻找过程中关注于网络中相对稠密的子图，网络中存在大量未聚类结点，需要设计合理的中心社区扩展策略，对未聚类结点进一步处理。

设聚类个数为k，当前中心社区分别为C₁,C₂,…,C_k，则当前未聚类结点集合$T=V\left( G \right)-U_{i=1}^{k}V\left( {{C}_{i}} \right)$。根据式(2)给出的结点对社区的归属度定义，计算T中结点与中心社区C_i的归属度，并对相关中心社区进行扩展，具体过程如算法1。

算法1 中心社区扩展算法 (core community extended strategy，CE)

输入 图G=V,E，聚类个数k，初始中心社区集合C⁰=C₁⁰,C₂⁰,…,C_k⁰，其中C_i⁰V。

输出 社区集合C=C₁,C₂,…,C_k。

1)令集合T⁰=VG－∪_i=1^kVC_i⁰，β₀=0.7，t=0。

2)令t=t+1，对每个社区C>₁^(t－1),C₂(^t－1),…,C_k(^t－1)，执行下列操作：

①C_i^t=C_i(^t－1)(1≤i≤k)，N_Gi(C^t－1)={u|u∈N_G(x)∧x∈C_i(^t－1)}。

②对任意元素v∈T∩N_GC_i(^t－1)1≤i≤k，如果b(v,C _i(^t－1))≥β_t－1，则C_i^t=C_i^t∪v。

③令β_t=β_t－1－0.1，T^t=VG－∪_i=1^kVC_i^t，若β_t≥0.3，且T^t≠，返回步骤2)。

3) 结束，输出社区集合C=C₁^t,C₂^t,…,C_k^t。

图 3给出了BDSG算法在空手道俱乐部数据集上的聚类结果，共得到2个社区，空白结点表示未聚类结点。

为了分析研究BDSG算法在真实网络中社区发现的有效性，将BDSG算法分别应用于空手道俱乐部(Karate)^[23]、海豚社交网络(Dolphin)^[24]、大学生足球网络(Football)^[25]、电子邮件网络(Email)^[26]和合作网络(NetScience)^[27] 等5个数据集。实验所用计算机配置为Inter Core i5 CPU 2.5 GHz，6 GB内存，Windows 7操作系统。程序采用java编程语言并在Eclipse环境下运行。依经验选择密度阈值 d=0.9，调节参数α=0.8。

图 3~5分别给出了本文BDSG算法在空手道俱乐部、海豚社交网络和大学生足球网络的聚类结果。表 2给出了BDSG算法与CPM、k-dense算法分别在聚类个数、未聚类结点数、社区模块性(Q)^[28]以及运行时间等方面的比较结果。

图 3 BDSG算法在空手道俱乐部得到的聚类结果 Fig. 3 Clustering results on zacharys karate club obtained by BDSG

图选项

图 4 BDSG算法在海豚社交网络上得到的聚类结果 Fig. 4 Clustering results on dolphins social network obtained by BDSG

图选项

图 5 BDSG算法在大学生足球网络上得到的聚类结果 Fig. 5 Clustering results on college football network obtained by BDSG

图选项

实验结果表明BDSG算法在这些网络数据上均具有较好的性能表现。BDSG算法在空手道俱乐部和大学生足球网络上所得到社区个数与网络实际的社区个数相同，而电子邮件网络和合作网络缺乏原始社区个数信息，无法进行比较；海豚社交网络和大学生足球网络中，BDSG算法所用时间明显少于CPM与k-dense算法；在电子邮件网络和合作网络中，BDSG运行时间比k-dense算法慢，但最终未聚类结点数少于k-dense算法；在这些实验数据集上，本算法所产生的未聚类结点个数明显较少、社区模块性较高。

此外，本文给出的中心社区扩展算法也可应用于CPM、k-dense等算法以处理未聚类节点，提高聚类性能。实验结果(见表 2)表明CPM与k-dense算法的聚类有效性均显著提高。在空手道俱乐部、海豚社交网络、电子邮件网络和合作网络中，在CPM与k-dense算法运行时间略有增大的情况下，CE算法的加入使得其未聚类结点个数降幅较大，社区模块性具有较为明显的提高。同时CPM与k-dense算法在加入扩展策略CE之后与BDSG算法相比，BDSG算法在未聚类结点数以及社区模块性方面优势依然较为明显。

综上所述，BDSG算法在空手道俱乐部、海豚社交网络、大学生足球网络、电子邮件网络和合作网络等数据集上，与CPM、k-dense算法相比运行时间较短、未聚类结点个数较少、社区模块性较高，具有良好的聚类性能。同时，中心社区扩展算法可以有效地提高CPM、k-dense算法的聚类性能，该算法也可用于其他非结点完全覆盖算法。

本文提出一种基于稠密子图的图聚类算法BDSG，解决了基于密度算法中大量未聚类结点问题。通过搜索网络中的相对稠密子图得到中心社区；通过定义结点对社区的归属度来度量结点和社区连接倾向性，进而给出一种中心社区扩展策略对中心社区外结点进行聚类。通过与CPM、k-dense算法在 5个真实网络数据集上进行分析比较，结果表明 ，BDSG算法在未聚类结点个数、模块性及运行时间方面均表现出较好的性能。同时中心社区扩展策略与其他算法相结合，对提高CPM、k-dense等算法的聚类性能具有一定的适用性。