近年来，社区发现不仅成为计算机领域中最具挑战性的基础性研究课题之一，同时也吸引了来自数学、生物、社会学和复杂性科学等其他众多领域的研究者，掀起了一股研究热潮.很多现实社会网络中，不同社区间往往不是相互独立的，而是彼此重叠、相互关联，每个成员可以同时属于多个社区.一般称这样的社区结构为“重叠社区”.重叠社区是对网络的一种覆盖，它反映了更加真实的网络结构，发现重叠社区对研究真实网络的拓扑结构具有更重要的指导意义^{[1, 2, 3, 4, 5, 6]}.

Palla等于2005年提出了首个重叠社区发现算法，即基于k-clique派系过滤的CPM算法^[3].Shen等^[7]提出的基于合并相似极大派系的层次重叠社区发现算法；Lee等^[8]提出的通过对派系进行贪心扩展来获得重叠社区结构的算法.除了“基于派系”的方法外，Evans等^[9]提出了基于边图转换的方法.即将原始图转换成边图(line graph)，然后在边图上对结点进行聚类，再将聚类结果还原到原始图上.这种方法在对结点进行聚类时，结点间的相似度是在边图上计算的，这样会因为过度依赖所对应原始图中的两条边的公共结点的度数而导致计算出的相似度值偏高.Lim等^[3]对该方法在聚类上进行了改进，提出了LinkSCAN算法.综上，虽然在一定程度上可以发现社区，然而，算法存在参数敏感或准确度不高等情况.另一方面，在网络中寻找派系是费时的过程，因此目前的主流重叠社区发现算法在面对大规模稠密网络时，计算复杂度太高，效率偏低.本文主要研究这样一种算法，在针对大规模复杂网络时，在保证准确度的情况下，提高单机处理的网络规模.

本文设计了一种基于压缩社区模型(压缩社区图)CCG；提出了一个可以在压缩社区上直接进行重叠社区发现的算法CLEAR；算法在真实数据集和人工数据集的比较分析，证明了提出算法的有效性和高效性.

与传统图一样，压缩社区图(compression community gragh,CCG)也有结点和边，但分别是压缩结点和压缩边.简单而言，可以通过对原始图中的结点进行聚类来得到压缩结点，一个类即是一个压缩结点，然后再通过给压缩结点之间增加压缩边，最终得到能够表示原始图的压缩图.压缩图可以大大降低网络的复杂程度，而且能更直观地观察到网络中存在的一些特殊结构.

定义1 给定图G=(V,E)，其中V是结点的集合；E⊆V×V是边的集合.图G对应的压缩图表示为G′=(V′,E′)，其中V′={v′₁,…,v′_n}是压缩结点的集合，满足∪_v′∈V′v′=V；E′⊆V′×V′是压缩边的集合.并且，如果两个压缩结点v′_i，v′_j∈V′(其中i∈[1,n],j∈[1,n])之间有一条压缩边e′∈E′相连，则这两个压缩结点要么v′_i∩v′_j=Φ，要么v′_i=v′_j.

根据定义1得到的压缩图具有3种基本结构：“二分派系”结构、“星形”结构和“派系”结构，本节分别加以详细介绍.

1) “二分派系”结构.该结构中，两个压缩结点由一条压缩边连接，对应原始图中一个压缩结点中的所有结点与另一个压缩结点中的所有结点均两两相连，但各自内部的所有结点互不相连.

2) “星形”结构.该结构是“二分派系”结构的一种特殊情况，即其中的一个压缩结点是一个单点集.网络中存在“星形”结构，通常意味着该单点集极有可能是连接若干个不同区域的枢纽.

3) “派系”结构.如果一个压缩结点与自身通过一条压缩边相连，该结构便是“派系”结构.对应到原始图，该压缩结点内的所有结点两两互连，即在原始图中这些结点构成了一个完全子图.

压缩图的生成分为两个阶段：生成压缩结点和压缩边.以下分别加以描述.

本文根据结点的邻居相似度来选择哪些结点可以构成同一个压缩结点.具体来说，给定原始图中的一组结点，如果这些结点有着共同的邻居结点，则它们构成一个压缩结点.基于该度量函数，采用层次聚类，即可生成最终的压缩结点.

定义2 给定无权图G= (V,E)，结点u,v∈V的邻居结点集合分别记为N(u)和N(v).结点u,v的邻居相似度N_s(u,v)可通过公式(1)来计算：

定义3 给定带权图G= (V,E,W)，W为权重集合，每条边e∈E被赋予权值w∈W.此时，结点u,v∈V的邻居相似度N_s(u,v)由公式(2)来计算：

N_s(u,v)的取值范围在^{[0, 1]}之间.当N_s(u,v)为0时，说明结点u和v没有公共邻居结点；当N_s(u,v)为1时，说明结点u和v的邻居结点完全相同.

上述生成压缩结点的过程可能会导致结果集C中存在单点集和较小压缩结点被较大压缩结点包含的情况.若记U_i和W_i为层次聚类中第i层的两个压缩结点，则生成压缩边的过程描述如下.

首先，对压缩结点自身填加压缩边.此过程针对“派系”结构进行.添边过程从最外层压缩结点开始，层层递进由外向内贪婪搜索压缩边.大致过程为：首先判断最外层U₀在原图中的导出子图是否是一个完全子图，如果是，则对U₀自身添一条边；否则，判断U₀的下一层U1在原图中的导出子图是否为完全子图，是则添边，否则继续向里一层判断，重复此过程，直至判断到U₀最里层.

其次，为不同的压缩结点添加压缩边.此过程针对“二分派系”结构和“星形”结构进行.大致过程为：先判断U₀与W₀所构成的图是否是原图的一个子图，如果是，则在U₀与W₀之间添边.当最外层的U₀和W₀之间有边时，就停止向内搜索，因为这条压缩边就代表了U₀和W₀内所有结点之间所有的边.如果最外层的U₀和W₀之间没有边，再向里一层搜索，先看U₀与W₁之间是否有边，如果有就添边，并且不再向W₁的内层继续搜索.当U₀和W₀的各层都搜索之后，再看U₁与W₀之间是否有边，如果有就添边，并且不再向W₀的里层继续搜索，如果没有边，则再看U₁与W₁之间是否有边.如果有就添边，并且不再向W₁的里层继续搜索，依此类推，直到U₀各层与W₀各层都搜索完毕.

由于采用贪婪式搜索，可能出现不满足1.1节压缩图所需条件(1)的情况.接下来，需要对压缩边进行修正.如果存在集合S⊂V，使得 U₀∩S≠Φ，U₀S，SU₀并且W₀∩S≠Φ，W₀S，SW₀，则这种结构最容易产生相交的压缩边.对这种结构，需要判断当前生成的压缩边集合L中是否同时出现边(U₀,W₀∩S)和(W₀,U₀∩S).如果出现，就不符合压缩图所需满足的条件(1)，需要对边进行修正.也就是，把原来的边更新成(U₀＼S,W₀∩S)和(U₀∩S,W₀)(或者(U₀∩S,W₀＼S)和(U₀,W₀∩S))，同时把原来的压缩结点U₀和W₀分解成U₀＼S,U₀∩S,W₀(或者W₀＼S,U₀,W₀∩S).

从压缩图生成过程可见，压缩结点的生成基于原始图的拓扑结构，保留了原始图中结点的信息；同时压缩边能够表示原始图的所有边，同样没有丢失任何信息.因此压缩图是对原始图的无损压缩.

给定压缩图G′=(V′,E′)，CLEAR算法无需解压缩，可以直接在压缩图上发现重叠社区.算法由3个主要步骤构成：①选取若干压缩结点作为“种子”；② 不断优化社区适应度函数将“种子”扩展为社区；③将相似度很高的社区进行合并，得到最终的重叠社区结果.以下，分别对这3个步骤加以详细描述.

社会网络中的社区大多是以一个或几个点为中心的.因此，一个最直观的想法是选取一个或几个结点作为初始社区，以其作为“种子”不断扩充.

首先，涉及的是选取谁作为“种子”的问题.“派系”是一个完全子图.如1.2节所述，“派系”结构代表定义最严格的一种社区结构.“极大派系”是指不被网络中任何其他派系所包含的派系，与压缩图中的“派系”结构对应.因此，CLEAR算法选取“极大派系”作为“种子”，大大节省了寻找“种子”的时间.

另外，选取的“种子”大小也是一个需要考虑的问题.也就是说，“极大派系”中包含的结点个数，也应满足一定要求.设“种子”的大小至少为k，则k既不能太大，也不能太小.如果k太大，有些中小规模的社区结构不能被发现，因为这些社区结构中并不包含大小为k的种子，这种情况被称为“漏报”；反之，如果k太小，则有些种子所在的网络区域即使根本不存在社区结构，算法却仍然会对其进行扩展，这种情况称为“误报”.通过实验发现，参数k选择默认值为4时比较适宜.

“种子”扩展涉及一个非常重要的概念，即社区适应度函数.

定义4 给定函数F:S→R，函数F将原始图G中的某个子图S映射到实数域R上的某个值.该值反映了S成为社区的程度.值越大，说明S越符合社区的结构.称函数F为社区适应度函数.

社区适应度函数对扩展“种子”成为社区非常重要.记G的某子图S中所有结点构成的集合为C.如果集合C中去掉任何一个元素都不会使S的社区适应度函数F变大，且将S的任一邻居结点添到集合C中也不会使S的社区适应度函数F变大，则S是一个社区.具体来说，本文采用Lancichinetti等^[10]提出的社区适应度函数，如公式(3)所示.

以图 1为例，“种子”扩展的具体步骤可描述为：①对S的每个邻居结点v(图 1中的阴影结点)，计算v对S的贡献值，也就是，加入v后,S的社区适应度改变量；②选择对S贡献最大的结点v_max；③ 如果v_max对S的贡献值为正，将其加入S并返回①,否则停止扩展并返回S.

图 1(Figure 1)

Fig. 1

图 1 种子扩展的过程 Fig. 1 The process of seeds expanding

扩展过程类似雨滴落水，是一种从中心向周围慢慢扩散的动态场景.对每一个“种子”都用这种方式进行扩展，当两个种子相互外扩至重叠时，就找到了两个社区的重叠结点.扩展中，社区适应度函数和种子的选取不是固定的，可以根据情况采用不同的社区适应度函数以及不同的种子选取方法.

在将“种子”扩展为社区的过程中，可能会出现社区间重叠度过高，甚至相互包含的情况.考虑这两种情况，可以将重叠度过高或者完全重合的社区进行合并.一种最简单的重叠度度量方法是计算两个社区重叠结点的个数与两个社区总结点个数的比值，如公式(4)所示：

进一步，为了避免两个社区中结点个数的悬殊差异对重叠度的影响，公式(4)可以调整为

合并过程中，通过定义阈值е，当社区S和S′的重叠度δ(S,S)≥e时，将社区S和S′进行合并.合并所有重叠度大于阈值e的社区后，即可得到网络中的最终社区结果.其中，被多个社区包含的结点为重叠结点，包含重叠结点的社区即为重叠社区.

为验证CLEAR算法的有效性和效率，对CLEAR算法进行分析，算法由C++编写，所有实验均在惠普主频2.33GHz，4GB内存的PC上运行完成，操作系统为Windows 7.对比算法为三个经典的社区发现算法LFM，LinkSCAN和CPM.

表 1总结了本文所用的两个真实数据集的信息.其中，#nodes代表数据中的结点数量，#links代表数据中的边数量，是平均集聚系数.这两个真实数据集均可从文献^[11]下载.

表 1

Table 1

表 1(Table 1)

表 1 真实数据集 Table 1 The real datasets 真实数据集 #nodes #links Facebook 4 039 88 234 0.605 5 Amazon 334 863 925 872 0.396 7

表 1 真实数据集 Table 1 The real datasets

本节基于的指标是重叠社区模块度M^ov[12].它是在不知道真实社区结构的前提下，衡量社区划分效果的一种评价标准.M^ov取值在^{[-1, 1]}之间.值越大，社区划分效果越好.

在“Facebook”和“Amazon”这两个真实数据集上的M^ov值比较结果如图 2所示.可以看出，通过CLEAR算法得到的社区结构的模块度最高，也就是说，对于不同规模的真实网络CLEAR算法都有效.由于CPM算法对于社区结构的定义过于严格，导致算法准确度不是很高.而LinkSCAN算法容易产生过多没有必要的小规模社区，使得重叠社区数量过多.

图 2(Figure 2)

Fig. 2

图 2 有效性的比较 Fig. 2 The comparison of effectiveness

重叠社区发现对研究真实网络的拓扑结构具有重要指导意义，是社区发现中一个新兴的热点.大多数现有的重叠社区发现算法计算效率偏低，只能作用于规模较小的网络.针对这种情况，本文提出了一种基于图压缩的重叠社区发现方法CLEAR，能在保证准确度的情况下，大大提高单机上处理的网络规模，使有效解决大规模网络上的重叠社区发现问题成为可能.实验对算法性能进行了验证.结果表明，CLEAR算法的性能优于另3个作为对比的经典社区发现算法.