聂世民 杜彦辉 芦天亮

摘 要：社区发现能帮助人们了解社交网络的结构特性及隐藏信息。局部社区发现算法不需要网络的整体信息，以局部结构信息为基础，可以快速找到目标节点所在的局部社区，提高了效率，因而受到学者们的青睐。按算法基本思想，现有局部社区发现算法可分为标签传播类算法、局部扩张算法等。对部分局部社区发现领域的研究成果进行总结，分析它们的优缺点，并提出未来局部社区发现算法研究方向。

关键词：社交网络;局部社区发现;评价指标;移动互联网

DOI：10. 11907/rjdk. 191832 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2020）005-0271-05

0 引言

随着互联网和计算机科学的发展，越来越多的人加入社交网络。人们在社交媒体上相互交流，表达自己的观点，形成了复杂的网络关系。社区发现对于揭示社交网络结构、挖掘人们观点、分析信息传播、把握和监测公众情绪具有重要意义[1]。近年来，随着社区发现成为社会网络分析的一个重要领域，科研人员和学者提出了多种多样的社区发现方法。因此，不论从其研究价值还是实用价值角度讲，研究社区发现问题都具有重要意义。

1 相关定义

1.1 社交网络

现实世界中有很多种网络，社交网络作为一种典型的网络，发展迅速。Wang[2]将网络定义为：“网络是一组具有特定内容和实体间关系的实体”;WOLFE[3]将社交网络定义为一种由实体和实体之间关系构成的网络，实体之间可以相互作用。社交网络是虚拟世界中真实世界的延伸，有许多典型的社交网络，如Facebook、Twitter、QQ、微信、微博、贴吧等，其特征、变化和社区结构反映了现实世界的运作方式，越来越多的专家学者致力于社交网络研究。

1.2 社区

社区是社会网络的重要结构[4-6]。关于社区的定义，学界尚没有形成一个精确的统一概念，不同学者从不同角度给出了社区的定义[7-12]。例如，从图的角度出发，Newman[7]将群内连接密集、群间连接稀疏的顶点群称为社区;Santo Fortunato[9]认为社区内的边必须比将社区顶点与图的其余部分连接起来的边更多，社区是一组具有相似性的顶点;Filippo Radicchi[12]等基于节点出度和入度提出了强社区和弱社区的概念。虽然定义各式各样，但可以提取一些相同点：社区通常被认为是复杂网络中一些满足特定条件的节点，该条件就是社区内节点与节点之间连接更加紧密，不同社区内的节点与节点之间连接相比较而言则较为稀少。

1.3 社区发现

通常，社区发现是指通过某种方法找出复杂网络中的某个或者多个社区。学者对社区结构定义的理解不同，在进行社区划分时遵循的标准也各不相同，大致可以总结为两种：全局社区发现算法和局部社区发现算法[1]。全局社区发现算法是在整个目标网络范围内划分社区，从整体角度出发进行社区发现，目的是找出目标网络中所有可能存在的社区，使用这类算法必须拥有目标网络的全局信息[13]。

当下，移动互联网用户不断发展壮大，各类社交网络规模与日俱增，Facebook、微信等社交网络都拥有10亿以上的节点，网络的全局信息逐渐变得难以获得，如此规模庞大的社交网络使用全局社区发现算法进行社区发现存在诸多困难且社区发现效果不尽人意。为解决这些困难，有学者提出了局部社区发现算法。局部社区发现算法不需要提前获得目标网络的整体信息，而是以目标网络的局部结构信息为基础，进而发现局部或整个网络社区。与全局社区算法相比，局部社区发现算法在运行时间、应用范围、算法灵活性等方面存在更大优势，已成为当前研究热点。

1.4 社区发现算法评价指标

社区发现算法多种多样，评价社区质量的标准也有很多，如模块度、标准互信息（Normalized Mutual Information，NMI）、Jaccard系数、ARI标准、芮氏指标、F-measure[14-15]值等，它们从不同角度对发现的社区进行评价。本文总结几种使用频率较高的评价指标：模块度、标准互信息、Jaccard系数。

（1）模块度。Newman等[16]首先提出了模块度的概念。模块度即Q函数，取值范围在0～1，一般情况下，Q值越大说明算法越精确，而在真实情况下，Q值在0.3～0.7时社区划分效果较好。然而，这种模块度计算方法还有其不足之处，其中一点就是无法在加权网络中使用。为了解决该不足，在原有模块度函数基础上，Xu等[17]提出了新的模块度函数[QW]。除了不适用于加权网络，Q函数不能评价重叠社区的发现结果[18-19]，为了更好地适应重叠网络情况，陈俊宇[20]、肖觅[21]等对Q函数进行了修改以评价重叠社区的发现结果。

（2）标准互信息度量。标准互信息度量是信息论中的概念，最初并没有用在社区发现的评价指标上。在社区发现领域，Leon Danon[22]等最早使用标准互信息度量进行社区发现算法评价。NMI可以衡量社区发现结果的精度[23-24]，NMI值越大，说明社区发现结果越准确，當NMI值为1时，说明发现的社区与真实社区结构一致。NMI也存在其局限性，如不能用于评价重叠社区的发现结果。在重叠网络中，一个节点一般不会只存在于单一的社区之中，往往属于不同的社区。为了能够适用于重叠网络，Lancichinetti等[25]对NMI的计算方法进行了修改。

（3）Jaccard系数。Jaccard系数的基本思想与标准互信息度量相同，也是将找到的社区结构与真实社区进行比较，通过计算二者的相似程度评价社区发现算法的准确性[26]。使用Jaccard系数作为评价指标，社区发现的结果越准确，Jaccard值越大。当Jaccard值为1时，说明二者的社区结构完全相同;当发现的社区和真实社区完全不同时，Jaccard值为0。

本文提到的3个评价指标适用范围并不相同，如表 1所示。由于实验数据中往往不包括社区结构方面的信息，因此实际应用时，模块度的使用频率最高。

2 局部社区发现算法

近年来，互联网和移动互联网取得了长足进展，社交网络也借此机会发展壮大，社交网络的内部结构持续变化，呈现出日趋复杂的趋势。这些因素都加大了社交网络分析难度，获取网络的全局信息越来越艰难。但是在很多业务场景中，并不一定要获取到网络的全局信息，只需发现某个节点所在的局部社区就能解决真实存在的问题。举例而言，因案件需要，公安机关需要知道某个犯罪嫌疑人在社交网络上的活跃社区从而寻找可能存在的犯罪同伙，这时就不需要社交网络的全局信息，只需要发现犯罪嫌疑人经常活跃的社区即可。

局部社区发现算法的基本思想不尽相同，现有的局部社区发现算法按照算法基本思想可以分为标签传播类算法[27-30]、局部扩张算法[31-40]和派系过滤算法[41-42]等。本文总结了一些经典的局部社区发现算法，其中局部扩张类算法中的Clauset算法是最早提出用来解决局部社区发现问题的算法，标签传播类算法、局部扩张类算法是使用频率较高的算法，这些算法不需要社交网络的全局信息，可以避免过高的时空开销。

2.1 Clauset算法

局部社区发现的概念由Clauset等[43]最早提出，在這之前，学者们都是从全局的角度研究社区发现问题。Clauset等不仅提出了局部社区发现的概念，也提出了解决办法，包括局部社区模块度R，该算法效率较高，能够快速找到局部社区。

Clauset算法首先初始化局部社区D，其邻居集合用S表示。最初从一个初始节点v开始，将v加入到D中，并将v的所有邻居节点加入到S中，然后按如下步骤进行运算：①对于邻居集合S中的所有节点计算模块度增量，也即设想将原本属于集合S中的节点j加入到初始化社区D中所带来的模块度增量;②选取具有最大模块度增量的节点j加入到D中;③将j的所有邻居节点加入到S中，然后更新R和B。

在局部社区规模达到预估设定值之前，Clauset算法会不断挑选能产生最大局部模块度增量的邻居节点划入社区D中。可以得知，使用这种算法进行局部社区发现会受预先设定参数的影响，局部社区发现的结果受初始节点影响较大。

2.2 标签传播类方法

Zhu等[27]最早提出标签传播算法（Label Propagation Algorithm，LPA），该算法用网络中已经具有标签信息的节点预测那些没有标签信息的节点，其本质是一种基于图的半监督学习方法。由于这种标签传播算法没有复杂的目标函数，实现难度较低，算法效率较高，因此受到了众多学术研究人员的关注。在社区发现这一领域，Raghavan等[28]第一次应用标签传播方法研究局部社区发现问题，提出的LPA算法只使用局部网络结构进行社区发现。

该算法具体过程为：①赋予一个原始标签给网络中每个节点;②在所有节点标签不再变化之前，根据传播规则，节点的标签在局部网络中传播;③相同标签的节点归属同一个社区。

LPA算法需要多次迭代，传播规则是在每次迭代后，节点标签受其邻居节点影响，邻居节点使用最多的标签会变为该节点的新标签。局部网络中每个节点最终归属的社区受其邻居节点影响，其邻居节点中大多数节点属于的社区就是该节点属于的社区。

虽然LPA算法有较低的时间复杂度，实现过程也不算困难，但也有其不足之处，比如它的不确定性。因为某些标签会在迭代传播过程中逐渐受到其它标签的控制而消失，结果是局部社区数量越来越少，出现少数几个规模较大的局部社区。为了改进LPA算法的不确定性，Leung等[29]在LPA算法的基础上，提出了HANP（Hop Attenuation and Node Preference）算法。除算法不确定性之外，标签的传播距离没有在算法中得到明确限制，这就会导致某个社区中的标签可以传播很远而侵入其它社区。在HANP算法中，在每个节点拥有一个标签的基础上新增一个分数参数，在标签传播过程中，传播距离越大，该分数值越小。HANP算法的基本思路就是通过该分数参数控制标签在传播过程中的影响力，分数参数变小则会降低该标签的影响力，从而避免标签传播过远而侵入其它社区的现象。

LPA算法还有一个问题就是它只能用于非重叠网络。因为该算法基于单个标签传播，最终每个节点都会归属到某个社区中，而现实情况中，存在节点属于多个社区的情况。为了解决LPA算法在重叠网络中的应用问题，Gregory等[30]基于LPA算法提出了多标签传播算法（Community Overlap Propagation Algorithm，COPRA）。在COPRA算法中，节点拥有多个标签，这样能够标示出节点的多个社区，社区间的重叠程度通过一个参数控制，算法每运行一次就会重新计算节点对于不同社区的隶属程度。不同于LPA算法，在标签传播时，因为节点拥有多个标签，COPRA算法先更新节点的邻居标签集合到该节点上，再删除不符合预设条件的标签。有些节点可能拥有多个最大隶属标签，一旦出现这种情况就随机选择一个，这也导致了结果的不确定性。

2.3 局部扩张算法

局部社区发现算法中有一大类算法是基于局部扩展优化思想的。局部扩张算法根据定义的局部度量，首先选择初始节点，再逐步合并邻居节点，从而进行局部扩展优化[38]。主要包括两个步骤：选择种子节点和将种子节点扩展为局部社区[44]。

Lancichinetti等[25]提出了局部适应度算法（Local Fitness Method，LFM）。在LFM算法中，种子节点的选择方法是采取随机原则，算法通过最大化局部适应度函数拓展社区。步骤如下：①计算种子边缘节点适应度，若适应度为正值，则将该节点划分到对应社区;②计算该社区内每个节点的适应度;③若某节点适应度为负，则移除该节点;④如果发生③，则执行②，否则执行①。

该算法实现简单，计算时间复杂度小，但受其种子节点选取随机性的影响，局部社区发现结果不确定。

Huang等[33]提出了局部紧密度扩展算法（Local Tightness Expansion，LTE）。在LTE算法中，种子节点的选择方法和LFM算法相同，也是随机选取某个节点作为种子节点，算法通过最大化可调密度增益扩展社区。方法如下：①计算社区邻居集合中每个节点与社区的相似度;②根据①中的结果，计算最大相似度节点的可调密度增益，若大于零，则将该节点划分到社区，否则就删除该节点。按照相似度的降序依次分析其余节点;③重复上述过程，直到所有节点均加入相应社区。

该算法实现简单，计算时间复杂度小，但受其种子节点选取随机性的影响，局部社区发现结果不确定。

陈琼等[34]为解决部分局部社区发现算法受初始节点位置影响的问题，提出了一种基于局部最大度节点的算法（Local Maximum Degree，LMD）。LMD算法将初始节点的局部最大度节点作为种子节点，通过优化局部社区度量扩展社区。

LMD算法采用Clauset算法[43]进行局部社区拓展，时间复杂度为[O（k2d）]，节点个数用k代表，节点平均度用d代表。以不同的局部最大度节点作为种子节点进行局部社区拓展得到的社区可能比较接近，因此需要将较近的社区合并成一个社区。对于社区[Ci]和[Cj]，其中，[Ci={vi1，vi2，][vi3，？vip}]，[Cj={vj1，vj2，vj3，？vjp}]，如果[Ci]和[Cj]滿足式（4），则[Ci]和[Cj]可以进行合并。

吴建等[35]提出了一种基于图遍历的局部社区发现算法，该算法扩张速度较快，可以用于大规模网络。该算法首先找出网络中度数最低的节点，以该节点为起点通过影响力函数将网络中的节点分为社区节点和边界节点，形成初步社区划分，然后通过适应度函数确定边界节点的社区从而得到最终划分结果。

算法步骤如下：①计算网络中所有节点的度数，选取度数最小的节点作为起始节点，如果多个节点的度数相同则从中随机选择一个作为起始节点，由于此时网络中的节点都未被标记，因此该节点被标记为边界节点;②由起始节点开始，计算该节点周围所有邻居节点受到的影响力，并根据节点标记规则对邻居节点进行标记;③判断当前已标记节点是否还有未被标记的邻居节点，若存在，计算所有未标记邻居节点受到的影响力，根据规则给予相应标记，再次执行步骤③，若不存在，则跳转至步骤④;④选择网络中的边界节点与邻居社区进行合并，计算每次合并前后的适应度函数F[24]，若合并后新社区的F大于合并前的社区F，则按照规则对合并后的节点标记进行更新;⑤当网络所有边界节点均合并完毕时去掉所有边界节点标记，将拥有相同标记的节点划分到统一社区中。

该算法时间复杂度较低，可以适用于大型网络，但社区发现结果受提前设置的参数影响，不能用于加权网络。

3 挑战及展望

学者们从不同角度提出了各种局部社区发现算法，取得了丰硕成果，让人们对局部网络结构有了更加清晰的认识。随着研究的深入，社交网络也在不断衍变，呈现出大规模、日益复杂的特征，因此需要更快处理速度和更高准确性的社区发现算法，但存在一些问题有待进一步研究。

（1）社区初步划分。社交网络往往规模巨大、节点众多，在进行局部社区发现时可以采取一定办法缩小网络规模从而降低算法时间复杂度。不同的网络具有不同特点，要根据网络特点设计符合实际的规则。

（2）社区发现领域快速性需求。社交网络规模在持续增长，有些社交网络的节点数能达到十亿以上，用户间的联系也千丝万缕，如何快速处理如此大规模的网络数据，是社区发现领域研究人员共同面临的一大难题。

（3）社区发现领域精确性需求。大多数局部社区发现算法结果受初始节点影响较大，导致结果不够准确。当然也有不少算法改善了这一问题，但在精确性上还有待提高。社区发现算法是为了找到真实的社区结构，但存在这样一个问题：社区结构是人为定义出来的，不同的学者根据不同场景提出过多种社区描述和定义，直到目前都没有一个统一标准，当前社区发现算法往往只能在其定义的社区结构场景中取得较高准确率，换一个场景就不一定能够保持高准确率。

4 结语

随着移动互联网的蓬勃发展，越来越多的人加入到各种社交网络中，社区发现研究的现实意义和应用价值日益凸显，受到了学者们的广泛关注。本文总结了部分局部社区发现领域的研究成果，提出了未来研究方向。希望更多学者能够投入社区发现及其相关研究，为社区发现理论与实践作出更大贡献。

参考文献：

[1] LI J H， WANG X F， WU P. Review on community detection methods based on local optimization[J]. Bulletin of Chinese Academy of Sciences，2015（2）：238-247.

[2] WANG， FAN X. Complex networks： topology， dynamics and synchronization[J]. International Journal of Bifurcation and Chaos，2002，12（5）：885-916.

[3] WASSERMAN S，FAUST K. Social network analysis： methods and applications[J]. Contemporary Sociology，1995，91（435）：219-220.

[4] ZHANG X， WANG C， SU Y， et al. A fast overlapping community detection algorithm based on weak cliques for large-scale networks[J]. IEEE Transactions on Computational Social Systems，2017，4（4）：218-230.

[5] VESPIGNANI A. Complex networks： the fragility of interdependency[J].  Nature， 2010， 464（7291）：984-5.

[6] WANG Q，WEN Z P. Multidimensional genetic algorithm for overlapping community detection[J]. Application Research of Computers，2016，33（12）：3543-3546.

[7] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proc. Natl. Acad. Sci. USA，2001，99：7821- 7826.

[8] PAPADOPOULOS S， KOMPATSIARIS Y， VAKALI A， et al. Community detection in social media[J]. Data Mining and Knowledge Discovery，2011，24（3）：515-54.

[9] FORTUNATO S. Community detection in graphs[J]. Physics Reports， 2009.

[10] EVERETT M G，BORGATTI S P.Analyzing clique overlap[J]. Connection，1998， 21（21）：49-61.

[11] PORTER M A， ONNELA J P， MUCHA P J. Communities in networks[J]. Notices of the AMS，2009，56（9）：1082-1097.

[12] RADICCHI F， CASTELLANO C， CECCONI F， et al. Defining and identifying communities in networks[J].  Proceedings of the National Academy of Sciences of the United States of America， 2004，101（9）：2658-2663.

[13] LIU L H， FANG Z X， XIAO S L， et al.Fast communities detection algorithm with source nodes[J]. Computer Engineering and Applications， 2016，52（23）：75-80.

[14] ZENG J P， YU H F. A study of graph partitioning schemes for parallel graph community detection[J]. Parallel Computing，2016，58（C）：131-139.

[15] SU Y S， WANG B J， ZHANG X Y. A seed-expanding method based on random walks for community detection in networks with ambiguous community structures[J]. Scientific Reports，2017（7）：1-10.

[16] Newman M E J.Finding and evaluating community structure in networks[J].  Physical Review E，2004，69（2）：026113.

[17] XU J M， LI T F， WU S F. A micro-blogging community discovery method based on users interactions[J].  Journal of Heibei University（Natural Science Edition）， 2016，36（2）：189-196.

[18] WANG X F， LIU G S， LI J H， et al. Locating structural centers： a density-based clustering method for community detection[J].  Plos One，2017，12（1）：1-23.

[19] SHANG M S， CHEN D B， ZHOU T. Detecting overlapping communities based on community cores in complex networks[J]. Chinese Physics Letters， 2010，27（5）：1-4.

[20] CHEN J Y，ZHOU G，NAN Y，et al. Semi-supervised local expansion method for overlapping community detection[J]. Journal of Computer Research and Development， 2016，53（6）：1376-1388.

[21] XIAO M，MENG X W，SHI Y C. A circuits merging community discovery algorithm based on mobile user behaviors[J]. Journal of Electronics & Information Technology， 2012， 34（10）：2369-2374.

[22] DANON L，DUCH J，DIAZ-GUILERA A，et al. Comparing community structure identification[J]. Journal of Statistical Mechanics，2005（9）：09008.

[23] LI L，FAN K，ZHANG Z，et al. Community detection algorithm based on local expansion k-means[J]. Neural Network World，2016，26（6）：589-605.

[24] WEN X Y，CHEN W N，LIN Y， et al. A maximal clique based multiobjective evolutionary algorithm for overlapping community detection[J]. IEEE Transactions on Evolutionary Computation， 2017，21（3）：363-377.

[25] LANCICHINETTI A， FORTUNATO S， KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics， 2009，11（3）：1-20.

[26] JEUB L G S， MAHONEY M W， MUCHA P J， et al. A local perspective on community structure in multilayer networks[J].  Network Science， 2017，5（2）：144-163.

[27] ZHU X， GHANRAMANI Z. Learning from labeled and unlabeled data with label propagation[R]. Carnegie Mellon University， Technical Report CMU-CALD-02， 2002.

[28] RAGHAVAN U N， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J].  Physical Review E， 2007，76（3）：036106.

[29] LEUNG I X Y， HUI P， LIO' P， et al. Towards real-time community detection in large networks[J].  Physical Review E Statistical Nonlinear & Soft Matter Physics， 2008，79（2）：066107.

[30] GREGORY，STEVE. Finding overlapping communities in networks by label propagation[J].  New Journal of Physics， 2010，12（10）：103018.

[31] CHEN J， ZAIANE O AND GOEBEL R. Local community identification in social networks[J]. In Proc. the 2009 Int. Conf. Advances in Social Network Analysis and Mining，2009：237-242.

[32] WU Y J，HUANG H， HAO Z F，et al. Local community detection using link similarity[J].  Journal of Computer Science and Technology，2012，27（6）：1261-1268.

[33] HUANG J B， SUN H L， LIU Y G， et al. Towards online multiresolution community detection in large-scale networks[J]. Plos One，2011，6（8）：1-11.

[34] CHEN， QIONG， WU， et al. Detecting local community structures in complex networks based on local;degree central nodes[J]. Physica A Statistical Mechanics & Its Applications，2013，392（3）：529-537.

[35] 吳建，王梓权，易亿，等. 基于图遍历的局部社区发现算法[J]. 计算机应用研究， 2019（9）：1-6.

[36] ANDREA L， FILIPPO R， RAMASCO JOSé J， et al. Finding statistically significant communities in networks[J].  Plos One，2011，6（4）：e18961.

[37] SHANGFU GONG， WANLU CHEN， PENGTAO JIA. Survey on algorithms of community detection[J]. Application Research of Computers.2013，30（11）：3216-3215.

[38] JARUKASEMRATANA S，MURATA T， LIU X. Community detection algorithm based on centrality and node distance in scale-free networks[J]. IMT，2013，9（1）：162-172.

[39] KLOUMANN I M， KLEINBERG J M. Community membership identification from small seed sets. KDD'14. 2014（2）：1366-1375.

[40] WHANG J J， GLEICH D F， DHILLON I S. Overlapping community detection using seed set expansion[C]. ACM International Conference on Information and Knowledge Management，2013：2099-2108.

[41] PALLA G， DERENYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature，2005， 435（7043）：814-822.

[42] KUMPULA J M，KIVELA M，KASKI K.A sequential algorithm for fast clique percolation[J].  Physical Review E Statistical Nonlinear & Soft Matter Physics， 2008， 78（2）：026109.

[43] CLAUSET A. Finding local community structure in networks[J]. Physical Review E， 2005，72（2）：254-271.

[44] SHANG C X，FENG S Z，ZHAO Z Y，et al. Efficiently detecting overlapping communities using seeding and semi-supervised learning[J]. International Journal of Machine Learning and Cybernetics，2017，8（2）：455-468.

（責任编辑：孙 娟）