论文部分内容阅读
摘 要：社区发现是在线社交网络研究领域中的重要内容，基于种子扩张的社区发现算法具有时间复杂度低、识别精度高以及不受社区形态限制等特点，近年来在网络局部社区发现任务中得到了广泛的应用。然而，该方法在种子选取时没有考虑种子之间的关联性，因此识别出的社区结构个数较多、结构松散。针对这一问题，提出一种基于多点种子预划分的二阶段社区发现算法。首先识别网络中的高影响力节点，利用K-means算法将高影响力节点加以聚合，得到高影响力社区簇。然后提出一种吸引力度量函数，选择性的将网络中的剩余节点合并到社区簇以完成社区识别任务。实验结果表明，二阶段社区发现方法能够发现尺寸较大，个数较少的社区结构，进而在中观层面捕捉群组之间的关联性。
关键词：复杂网络;局部社区发现;种子扩张;节点影响力;K-means算法
DOI：10.15938/j.jhust.2021.04.011
中图分类号：TP391.4
文献标志码：A
文章编号：1007-2683（2021）04-0078-09
Abstract：Community detection is an important content in the field of online social networks research. The community detection algorithm based on seed expansion has the characteristics of low time complexity， high recognition accuracy， and is not restricted by the shape of the community. In recent years， it has been widely used in local community discovery of complex networks. However， this method does not consider the correlation between seeds when selecting seeds， so the number of identified community structures is large and the structure is loose. Aiming at this problem， a two-stage community discovery algorithm for multi-point seed prepartition was proposed. First， high-impact nodes in the network are identified， and high-impact nodes are aggregated using the k-means algorithm to obtain high-impact community clusters. Next， an attractiveness measurement function is proposed to selectively merge the remaining nodes in the network into the community cluster to complete the community identification task. The experimental results show that the two-stage community discovery method can find community structures with larger sizes and fewer numbers， and then capture the association between groups at the meso level.
Keywords：complex network; local community detection; seed expansion; node influence; K-means algorithm
0 引 言
现实世界的复杂网络通常可以抽象为图模型，图中节点代表现实世界的实体，两个节点之间的链接代表实体之间的关系。社区[1]是复杂网络中的稠密子图，保证了社区内部节点之间的链接较为紧密，社区之间节点的链接较为稀疏[2-5]。探索社区结构有助于人们理解复杂网络的自组织以及群聚特性，是复杂网络中观层次最重要的属性之一。
从社区的层次化角度来看，已有的社区识别算法可分为全局优化算法和局部优化算法两种。前者在宏观角度寻找社区结构，描述了宏观层面网络节点的自组织特性，适合以数理统计为目的的网络特征分析[1-2]。后者从微观层面刻画节点的局部倾向性，更适合发现社区的演化规律及形成过程。基于种子节点扩张的社区发现算法[6]，就是局部優化算法的典型代表。
2009年，Lancichinetti等[7]提出重叠社区发现算法LFM，根据定义的自适应函数Fitness进行基于种子扩张的社区识别。Coscia等[8]提出的DEMON算法以整个网络节点为起始种子，利用标签传播算法识别网络中的局部社区结构。Baumes等[9]提出一种链接聚合方法。先按照递增或递减原则对节点进行排序，作为初始社区，如果节点的添加不能提高任何社区的密度，则该节点将作为新的种子节点，并生成新社区。李婕等[10]采用基于派系过滤的算法选择种子节点进行社区识别。Su等[11]基于随机游走算法，使用紧密连接子图作为社区识别的初始种子社区。
提高基于种子扩张的社区识别性能的关键在于种子节点的选取，近年来有研究者提出借助影响力分析方法，增加初始种子节点位于社区内核的概率。Clauset等[12]依次探索网络节点，推断给定节点所在社区。Luo等[13]将度的概念从单节点扩展到子图，在此基础上给出了网络模块化的定义，以此进行社区识别。Chen等[14]提出一种新的局部社区测度，先提取所有可能的候选社区，然后对社区层次进行优化。吴英俊等[15]提出LS算法，通过分析社区与节点之间的链接相似性来寻找局部社区结构。Fanrong等[16]提出一种基于最大团扩展的局部社区检测算法LCDMC，首先找到包含源节点的最大派系集合，然后利用贪婪优化方法扩展社区。Yao等[17]分析了高影响节点在社区检测中的作用。齐金山等[18]提出了一种结合Jaccard系数的节点影响力计算公式，提高了算法对星形社区的匹配性。 上述社区识别方法虽然在特定领域具有一定的性能优势，但普遍存在以下两方面问题。首先，上述方法在种子选取时没有考虑种子之间的关联性，导致识别出社区结构个数较多、稳定性较差，不利于在中观层面上挖掘群组之间的关联性。其次，由于社会网络结构的多样性，上述方法在影响力识别时忽略了网络的结构特性，导致网络中的高影响力节点呈现出较低的影响力评分的假象，这使得识别出的社区结构较为松散，内聚性较差。
为了解决上述问题，提出一种多点种子预划分的二阶段社区发现算法（two-stage community detection algorithm，TSCDA），其创新之处主要体现在以下三方面。首先，在節点的影响力计算时融入边介数属性，增强节点影响力的结构因素;其次，通过预划分高影响力节点生成骨干网络，增强种子的结构密度;最后，以稠密子图代替节点作为种子进行扩张，增加了社区结构的稳定性。仿真结果表明，TSCDA能够挖掘出数量较少、规模较大的社区结构，并在模块度以及F-Score等指标上表现出一定的性能优势。
1 基于节点影响力识别的种子节点选取方法
用无向图G=（V，E）表示社交网络，其中V代表网络中个数为n的节点集合，E代表网络中个数为m的链接关系集合。图1给出了一种具有强聚合特性的社交网络结构（社区网络）。
社会网络中，节点u的邻居集合定义为：
这里u和v代表网络节点，V代表网络中的节点集，如果u和v之间存在边（u，v），则（u，v）属于边集E。节点u的节点度D（u）定义为与u直接相连的边的个数（或邻居元素的个数），满足D（u）=|N（u）|。
为了在影响力计算中引入结构的相似属性，提出从节点相似性以及链接相似性双重角度构造影响力评价函数。
Jaccard系数Juv用于比较社会网络中节点之间的结构相似性。其定义为：
N（u）和N（v）分别代表节点u和节点v的邻居节点。JuvJuv取值范围为[0，1]，其值越大，节点u和节点v的共有邻居节点就越多，邻域结构也就相对越稠密。
边介数用来度量社会网络中所有节点间的最短路径中经过该边的路径的数目占最短路径总数的比例。边介数值越大，该边越有可能成为连接社区内部节点的重要途径。其定义为：
其中guvst表示网络中任意节点s与任意节点t之间的最短路径同时经过节点u和v（即边euv）的条数。根据式（3），可以计算出图1各边的边介数指数，例如节点8和节点10，即（e8，10）之间边强度为EBET（e8，9）=11;节点9和节点10，即（e9，10）之间边强度为EBET（e9，10）=11。边介数反映了社区内部链接的稠密程度，是增加社区稳定性的关键参数。
受牛顿万有引力定律的启发，提出一种基于Jaccard系数以及边介数的影响力计算方法。社会网络节点u对节点v的影响力评分定义为：
这里D（u）和D（v）分别表示节点u和节点v的度。由于节点度在局部环境反映了节点链接能力，因此在本文中被用来衡量社会网络节点的质量。节点之间的距离d（u，v）用节点间的相异程度加以衡量，满足d（u，v）=1-Juv。其中Juv代表节点u和节点v的Jaccard相似度。G是影响力常量，在实验中通常取值为1。
节点在局部社区的影响力评分Iscore（u）定义为该节点对其所有邻居的节点影响力评分之和。进而有：
式（5）中，v∈N（u）表明节点v是节点u的邻居节点。Iscore（u）的值越大，说明节点u在局部环境的影响强度越大，表明越有可能成为种子节点。根据式（5），可以计算出图1各节点的影响力分数。例如节点10的影响力分数：
因此节点10在网络中影响力分数Iscore（u10）=275。
下面给出基于节点影响力识别的种子节点选取过程。算法通过式（5）计算社会网络每个节点的影响力评分。其伪代码如下：
算法1 具有高影响力的初始种子选取算法
输入：社会网络G=（V，E）
输出：高质量节点集合S
1）初始化集合S为空集;
2）遍历社会网络的所有节点，根据公式（5）计算社会网络所有节点的节点影响力评分;
3）对于任意节点，如果它的影响力评分大于其任一邻居的影响力评分，则为高影响力种子节点，将其存储到集合S;
4）输出集合S。
根据算法1，计算图1中节点1到节点10的影响力评分，具体如表1所示。在本文中，如果一个节点的影响力分数大于其任一邻居的影响力评分，则为高影响种子节点。例如，节点8的邻居节点为6，7，9，10。通过表1可知，节点8的影响力评分大于节点6，7，9，10的影响力评分，因此节点8为高影响力节点。
2 多点种子预划分的二阶段社区发现算法
本节给出多点种子预划分的二阶段社区发现算法。首先，根据算法1选取网络中的高影响力种子节点，对这些节点利用K-means聚类算法进行初始划分，识别出由高质量节点组成的种子社区即骨干社区;然后提出一种基于吸引力度量的社区识别算法将社会网络中其余节点按特定规则有选择性的加入骨干社区中，从而完成社区划分。该方法的优势在于充分考虑了种子节点之间稠密性以及关联性，有助于提高社区的稳定程度。
2.1 基于K-means聚类的骨干社区识别
本文采用K-means算法作为骨干社区的初始化算法，其距离度量公式在式（7）给出。
式中：minDis（A，B）为在社会网络中节点A，B间最短路径长度;comNeighbor（A，B）为节点A，B间共同邻居数量;C为迭代中心，初始值为0;Dis（A，B）为A、B两点的距离，该值与A、B两点的最短路径长度呈正相关，与A、B两点的共同邻居数量呈负相关。 K-means算法在迭代时依靠簇内所有节点的平均坐标设定新中心。然而社区不存在坐标，因此需要重新定义中心选取方式。本文选取到簇内其他节点的距离之和最小的节点作为新的中心节点，具体如式（8）所示。
式中：N（i）表示第i个社区内的节点集合。K-means算法的最终输出1棵骨干社区层次化树，采用模块度函数在层次化树上进行分割，获取质量最高的社区划分。模块度函数Q是Newman[19]在2004年提出的概念，用以评价社区划分的质量，其定义为：
式中：eii代表社区i中边的期望;ai代表链接到社区i中的边数的期望。模块度的形式化定义是社区内的边数减去随机产生的边的期望，因此模块度越高，社区内外边比例就越大，社區划分结果就越好。
我们发现，算法在层次聚类时模块度函数Q的取值并不是单调递增或单调递减的，因此每当有社区进行合并操作，就需要重新计算Q值，能对产生最大Q值的两个社区合并。为简化计算，每次仅计
算Q的变化部分，即向Q值增大最多或者减少最小的方向进行社区合并。Q函数的变化量计算公式如下所示。
对能产生最大Q值的两社区进行合并，直到所有节点合并至同一社区。算法的伪代码如下：
算法2 利用K-means聚类算法实现种子节点初始划分
输入：3个种子节点集合，社会网络G
输出：骨干社区集合BC={BC1，BC2，…BCn}
1）选取这3个种子节点进行初始聚类;
2）根据距离度量式（7）计算任意两节点之间的距离;
3）比较任意两点间的距离，将节点划分至距离最近的节点簇内;
4）对于每个簇内，分别计算簇内每个节点与簇内的其他节点距离之和，取和最小的节点作为新的中心节点;
5）迭代步骤4）、5），直到中心节点不发生改变;
6）对K-means算法产生的社区按照式（10）计算两两之间合并产生的ΔQ，将使ΔQ增加或减少的两个社区进行合并，并按照式（9）计算当前Q值，保存Q值及当前社区划分;
7）对步骤7）进行迭代，直到所有节点都包含在一个社区或不能进行社区合并;
8）比较每次合并的Q值大小，取Q值最大的社区作为最终的结果。
2.2 基于吸引力度量的社区识别过程
算法2结束后，会对社会网络中影响力较高的前3个节点进行预划分，识别出由高影响力节点组成的种子社区即为骨干社区。而网络中影响力较低的n-3个零散节点可能处于孤立状态，因此需要将其合并到骨干社区之中。提出一种基于影响力分析的吸引力度量函数，将网络中零散节点添加到对其吸引力较高的骨干社区。对于任意骨干社区BC和节点u，BC对u的吸引力度量函数attract（BC，u）的定义为：
式中：∑v∈BC∧v∈N（u）NG（u，v）表示节点u对当前所在骨干社区的所有邻居节点的影响力评分数之和;Iscore（u）表示节点u的影响力评分。attract（BC，u）的值越大，节点u受骨干社区BC吸引而加入社区BC的可能性就越大，反之节点u成为骨干社区BC内部节点的概率较低。
设定了吸引力阈值β，对于节点u以及任意社区BC，若attract（BC，u）>β，则节点u属于骨干社区BC。节点u可能同时加入多个社区结构，因此社区具有重叠性。在图1中，假设骨干社区BC1包含的节点集合为{1，2，3，4，5}，骨干社区BC1对节点6的吸引力函数为：
假设BC2的骨干社区包含节点集合为{7，8，9，10}，骨干社区BC2对节点6的吸引力为：
若β=0.4，则节点6不属于骨干社区BC1，属于骨干社区BC2。
下面给出基于种子扩张的社区发现算法，算法的伪代码如下：
算法3 基于种子扩张的社区发现算法
输入：高影响力节点构成的社区集合BC，社区网络G
输出：社区划分结构
1）将网络中高影响力节点标记为true，其余n-3个节点标记为false;
2）将网络中标记为false的节点按照式（11）依次对骨干社区集合BC={BC1，BC2…BCn}进行计算;
3）对每个标记为false的节点按照不同的骨干社区的计算，选取attract（BC，u）最大的值并将该节点加入到对应的骨干网络;
4）将加入骨干社区网络的节点标记为true;
5）重复执行步骤2），步骤3）和步骤4），直到社区网络中所有节点都标记为true;
6）输出社区划分结构。
为了挖掘网络的社区结构，首先将网络除3个高影响力节点外的节点都标记为false，若节点划分到一个社区中，则该节点标记为ture。
在基于吸引力度量的种子扩张过程的伪代码中，第一步为遍历n个高影响力评分节点社区集合。第二步以及第三步为计算集合BCi中对n-3吸引度量函数值attract（BCi，v）不小于给定的阈值β的节点。若节点attract（BCi，v）值大于或等于阈值，将该节点合并到当前的社区中，若一个节点属于多个社区，则称该节点为重叠节点。将该节点加入到attract（BCi，v）值最大的骨干社区中。最后将加入骨干社区的节点标记为true，得到最终的社区结构划分结果。社区合并本质上是一种贪心策略，然而由于网络本身存在稀疏性，在实际的种子扩张中零散节点邻接社区要远小于其邻接的社区数，这有效的控制了算法的时间开销。
2.3 算法的时间复杂度分析
假设社会网络G包含有n个节点和m条边，算法1在求解节点的影响力强度时，时间复杂度为O（n）。在算法2中基于K-means聚类算法将O（l）个节点进行合并得出骨干网络，其时间复杂度为O（kl），最坏的情况下将O（n）个节点进行合并，故算法2的时间复杂度为O（kn）。在算法3中，在社区扩展阶段将O（n）个节点加入到O（k）个骨干社区中，该过程重复执行O（n）次，所以找到所有的最终社区的时间复杂度为O（kn2），若k<<n，则时间复杂度为O（n2），在最坏的情况下有O（n）个骨干网络，则找到所有的最终社区的时间复杂度为n3。经过以上分析，本算法最差情况下时间复杂度为O（n+kn+n3）=O（n3）。 3 实验结果与分析
本节给出算法在人工合成网络以及真实数据集上的运行结果。实验的运行环境为Intel Core i5-7300HQ 2.5GHz处理器，8GB内存，Windows 10操作系统，算法采用Python与Matlab R2016a混合编程。
3.1 NMI指数
Danon等[20]提出归一化互信息（normalized mutual information，NMI），度量社区集合之间的相似性。NMI基于混淆矩阵N，其中行表示真实的社区结构，列表示算法生成的社区。Ni表示矩阵N第i行所有元素的总和，Nj表示矩阵N第j列所有元素的总和。Nij是矩阵N的元素，表示同时属于真实社区i和算法生成社区j的节点数量。NMI公式定义为：
式中：CA代表网络中真实社区的数量;CB代表由算法生成社区的数量。如果探测出的社区结构和真实网络的社区结构相同则NMI=1;反之，如果所探测的社区结构和真实网络完全不同，则NMI=0。传统意义上的归一化互信息被用来量化两个分布之间的差异性，为了使之适用于社区差异性量化，实验中采用的了NMI的简化版本[21]。
3.2 F-SCORE
F-Score也是常用的社区发现算法度量指标。首先定义算法生成社区在全部社区中的比例。
式中，CR代表高质量节点所在的真实社区，CF代表高质量节点所在的探测社区。
Precision是正确划分节点的数量除以节点在CF中的数量，其定义为：
结合式（15）以及式（16），F-Score定义为：
3.3 人工合成网络社区识别结果
利用LFR-Benchmark提供的MATLAB数据生成器生成网络，网络中的部分重要参数设置如下。首先，生成网络规模为N=1 000的复杂网络，其中最小社区尺寸为10、最大社区尺寸为100。接下来设置网络的平均度为5、最大节点度为25、混合参数u的取值范围为0.1～0.8。在LFR Benchmark中，混合参数是一个独立参数，其值越大社区越难以发现，因此通常用来刻画算法的鲁棒性。
首先验证了不同混合参数下K-means聚类算法中的k取值不同时NMI指标变化情况，实验结果如图2所示。可以看出，初始时社区质量会随种子社区的不断增多而不断上升，但达到某一极值时，社区质量开始下降。这是因为初始种子过多会导致社区个数增加，进而降低社区内部的紧密程度。另一个发现是，社区结构较为模糊的网络中（u=0.8），需要更多的种子社区才能达到较好的发现效果。
接下来，验证TSCDA算法的性能。与Clauset[12]、LWP[13]、Chen[14]、LS[15]、LCDMC[16]以及VI[17]6种社区识别算法在人工合成网络社区进行比较，为了保证算法结果的客觀性，将相关参数按原有文献加以设定，算法的NMI指标以及F-Score在图3以及图4给出。
如图2及图3所示，当混合参数u等于0.1时，TSCDA在NMI以及F-Score的性能指标明显优于其它算法，具有一定的性能优势。随着混合参数u的不断增加，TSCDA算法和其他6种算法的NMI指标以及F-Score均呈现明显的下降趋势，当混合参数u等于0.5以及0.6时，TSCDA算法略优于VI算法和LCDMC算法，优于LWP以及LS算法;当混合参数u等于0.7以及0.8时，各算法性能较为接近，但总体来看，TSCDA算法仍然要优于其他6种社区识别方法，这表明TSCDA算法在结构指标上更贴近于内嵌社区。
3.4 真实网络社区识别结果
为了验证TSCDA算法在真实网络社区识别的性能，本节选取了在5种真实网络上，对比TSCDA算法与前文6种社区识别算法的性能差异。表2列出了所选择的真实网络的网络特征，其中Node代表节点个数、Link代表链接条数、d—表示网络的平均度、|C—|表示真实社区的平均大小、Community表示社区个数。我们从Amazon社区中移除了前5 000个子社区，保留了它的不同的社区。
还在DBLP计算机学科文献数据网络上测试了TSCDA算法与Clauset算法、LWP算法、Chen算法、LS算法、LCDMC算法以及VI算法的NMI指标以及F-Score指标。DBLP文献网络的特性如表3所示。|C|代表社区规模的范围，例如，（0，10]代表样本网络包含的社区大小大于0，小于等于10。我们同样移除了DBLP网络前5 000个社区中的子社区，并保留了它们不同的社区结构。
表4给出了各算法在真实网络上的NMI指标以及F-Score指标。相比其它6种方法，TSCDA具有一定的性能优势。一方面，TSCDA基于节点影响力扩展社区，因此在识别社区成员时准确度更高。另一方面，本文在节点影响力计算中加入了边介数属性，不仅考虑了节点自身的重要程度，还考虑了链接在局部区域中的重要程度。LWP和LS算法在个别网络中显示出比TSCDA更好的性能，例如在Football网络中LWP算法的NMI指标高于TSCDA约0.09、在Amazon网络中LS算法的F-Score高于TSCDA约0.02。一个可能的原因是Football网络的平均节点度较高，使得各算法在社区识别时更容易发现结构较为紧凑的局部结构。TSCDA算法在Dolpins网的准确性有所下降，这是由于Dolpins网络中的链接关系依靠于节点之间的接触历史，因此影响力识别时准确度一般。但是相比其它6种算法TSCDA算法仍然表现出一定的稳定性，进一步说明了TSCDA算法具有较高的鲁棒性。
图5和图6给出了各算法在DBLP引文网络上的性能指标。实验结果显示，当社区规模在0到10时（Label 0），TSCDA在社区识别性能上略低于其他6种算法表现的差。然而当社区规模大于10时（Label 1～10），TSCDA的表现性能明显优于Clauset、LWP、Chen、LS、LCDMC和VI算法，这表明TSCDA善于挖掘个数较多的社区结果，社区粒度更加细致。 4 结 论
为了解决传统社区识别方法社区稳定性较差这一问题，从节点相似性以及链接相似性两个角度入手，提出一种多点种子预划分的社区发现算法TSCDA。首先，在种子扩张算法的基础上，提出利用高质量节点构建骨干社区进行社区识别，提高社区结构的致密性;其次，将边介数属性加入到节点影响力的计算中，提高影响力计算中的结构相关性。人工合成网络和真实网络数据集上的仿真结果验证了TSCDA算法的效率和识别性能。
参 考 文 献：
[1] SANTO Fortunato. Community Detection in Graphs[J]. Physics Reports，2009，486（3）：26.
[2] JAVED M A， YOUNIS M S， LATIF S， et al. Community Detection in Networks：A Multidisciplinary Review[J]. Journal of Network and Computer Applications，2018， 108：87.
[3] AMOR B， VUIK S， CALLAHAN R， et al. Community Detection and Role Identification in Directed Networks： Understanding the Twitter Network of the Caredata Debate[J]. Dynamic Networks and Cyber-security， 2015， 25（2）：19.
[4] BAZZI M， PORTER M A， WILLIAMS S， et al. Community Detection in Temporal Multilayer Networks， with an Application to Correlation Networks[J]. Multiscale Modeling & Simulation， 2016， 14（1）：1.
[5] SHARMA S， SINGH A. An Efficient Method for Link Prediction in Complex Multiplex Networks[C]// 2015 11th International Conference on Signal-Image Technology & Internet-Based Systems（SITIS）. IEEE， 2015：452.
[6] DING X， ZHANG J， YANG J. A Robust Two-stage Algorithm for Local Community Detection[J]. Knowledge Based Systems， 2018， 14（7）：62.
[7] LANCICHINETTI A， FORTUNATO S， KERTSZ， JNOS. Detecting the Overlapping and Hierarchical Community Structure in Complex Networks[J]. New Journal of Physics， 2009， 11（3）：15.
[8] COSCIA M， ROSSETTI G， GIANNOTTI F， et al. DEMON：a Local-First Discovery Method for Overlapping Communities[C]// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2012：19.
[9] BAUMES J， GOLDBERG M， MAGDON-ISMAIL M. Efficient Identification of Overlapping Communities[C]// International Conference on Intelligence and Security Informatics， 2005：11.
[10]李婕， 王興伟， 郭静， 等. 面向移动通信网络的局部扩张群组构造方法[J]. 东北大学学报（自然科学版），2017，38（12）：1691.
LI Jie， WANG Xingwei， GUO Jing， et al. Clique Percolation Based Local Fitness Method for User Clustering in Telecommunication Network[J]. Journal of Northeastern University Natural（Science）， 2017，38（12）：1691.
[11]SU Y， WANG B， CHENG F， et al. An Algorithm Based on Positive and Negative Links for Community Detection in Signed Networks[J]. Scientific Reports， 2017， 7（1）：10874.
[12]CLAUSET， ARON. Finding Local Community Structure in Networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2005， 72（2）：26. [13]LUO F ， WANG J Z ， PROMISLOW E. Exploring Local Community Structures in Large Networks[J]. Web Intelligence & Agent Systems， 2008， 6（4）：387.
[14]JIYANG Chen， OSMAR Zaane， RANDY Goebel. Local Community Identification in Social Networks[C]// International Conference on Advances in Social Network Analysis & Mining. IEEE Computer Society， 2009：79.
[15]YING JUN， WU， HAN， et al. Local Community Detection Using Link Similarity[J]. Journal of Computer Science & Technology， 2012， 23（3）：69.
[16]FANRONG M ， MU Z ， YONG Z ， et al. Local Community Detection in Complex Networks Based on Maximum Cliques Extension[J]. Mathematical Problems in Engineering， 2014， 36（6）：1.
[17]YAOY ， WU W ， LEI M ， et al. Community Detection Based on Variable Vertex Influence[C]// IEEE International Conference on Data Science in Cyberspace. IEEE， 2016：145.
[18]齊金山， 梁循， 王怡. 基于种子节点选择的重叠社区发现算法[J]. 计算机应用研究，2017（12）：20.
QI Jinshan， LIANG Xun， WANG Yi. Overlapping Community Detection Algorithm Based on Selection of Seed Nodes[J]. Application Research of Computers，2017（12）：20.
[19]NEWMANM E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E， 2004， 69（6）：133.
[20]DANON， LEON， DUCH， et al. Comparing Community Structure Identification[J]. Journal of Statistical Mechanics， 2005， 206（9）：69.
[21]BAGROW， JAMES P. Evaluating Local Community Methods in Networks[J]. Journal of Statistical Mechanics：Theory and Experiment， 2008， 8（5）：26.
（编辑：温泽宇）
关键词：复杂网络;局部社区发现;种子扩张;节点影响力;K-means算法
DOI：10.15938/j.jhust.2021.04.011
中图分类号：TP391.4
文献标志码：A
文章编号：1007-2683（2021）04-0078-09
Abstract：Community detection is an important content in the field of online social networks research. The community detection algorithm based on seed expansion has the characteristics of low time complexity， high recognition accuracy， and is not restricted by the shape of the community. In recent years， it has been widely used in local community discovery of complex networks. However， this method does not consider the correlation between seeds when selecting seeds， so the number of identified community structures is large and the structure is loose. Aiming at this problem， a two-stage community discovery algorithm for multi-point seed prepartition was proposed. First， high-impact nodes in the network are identified， and high-impact nodes are aggregated using the k-means algorithm to obtain high-impact community clusters. Next， an attractiveness measurement function is proposed to selectively merge the remaining nodes in the network into the community cluster to complete the community identification task. The experimental results show that the two-stage community discovery method can find community structures with larger sizes and fewer numbers， and then capture the association between groups at the meso level.
Keywords：complex network; local community detection; seed expansion; node influence; K-means algorithm
0 引 言
现实世界的复杂网络通常可以抽象为图模型，图中节点代表现实世界的实体，两个节点之间的链接代表实体之间的关系。社区[1]是复杂网络中的稠密子图，保证了社区内部节点之间的链接较为紧密，社区之间节点的链接较为稀疏[2-5]。探索社区结构有助于人们理解复杂网络的自组织以及群聚特性，是复杂网络中观层次最重要的属性之一。
从社区的层次化角度来看，已有的社区识别算法可分为全局优化算法和局部优化算法两种。前者在宏观角度寻找社区结构，描述了宏观层面网络节点的自组织特性，适合以数理统计为目的的网络特征分析[1-2]。后者从微观层面刻画节点的局部倾向性，更适合发现社区的演化规律及形成过程。基于种子节点扩张的社区发现算法[6]，就是局部優化算法的典型代表。
2009年，Lancichinetti等[7]提出重叠社区发现算法LFM，根据定义的自适应函数Fitness进行基于种子扩张的社区识别。Coscia等[8]提出的DEMON算法以整个网络节点为起始种子，利用标签传播算法识别网络中的局部社区结构。Baumes等[9]提出一种链接聚合方法。先按照递增或递减原则对节点进行排序，作为初始社区，如果节点的添加不能提高任何社区的密度，则该节点将作为新的种子节点，并生成新社区。李婕等[10]采用基于派系过滤的算法选择种子节点进行社区识别。Su等[11]基于随机游走算法，使用紧密连接子图作为社区识别的初始种子社区。
提高基于种子扩张的社区识别性能的关键在于种子节点的选取，近年来有研究者提出借助影响力分析方法，增加初始种子节点位于社区内核的概率。Clauset等[12]依次探索网络节点，推断给定节点所在社区。Luo等[13]将度的概念从单节点扩展到子图，在此基础上给出了网络模块化的定义，以此进行社区识别。Chen等[14]提出一种新的局部社区测度，先提取所有可能的候选社区，然后对社区层次进行优化。吴英俊等[15]提出LS算法，通过分析社区与节点之间的链接相似性来寻找局部社区结构。Fanrong等[16]提出一种基于最大团扩展的局部社区检测算法LCDMC，首先找到包含源节点的最大派系集合，然后利用贪婪优化方法扩展社区。Yao等[17]分析了高影响节点在社区检测中的作用。齐金山等[18]提出了一种结合Jaccard系数的节点影响力计算公式，提高了算法对星形社区的匹配性。 上述社区识别方法虽然在特定领域具有一定的性能优势，但普遍存在以下两方面问题。首先，上述方法在种子选取时没有考虑种子之间的关联性，导致识别出社区结构个数较多、稳定性较差，不利于在中观层面上挖掘群组之间的关联性。其次，由于社会网络结构的多样性，上述方法在影响力识别时忽略了网络的结构特性，导致网络中的高影响力节点呈现出较低的影响力评分的假象，这使得识别出的社区结构较为松散，内聚性较差。
为了解决上述问题，提出一种多点种子预划分的二阶段社区发现算法（two-stage community detection algorithm，TSCDA），其创新之处主要体现在以下三方面。首先，在節点的影响力计算时融入边介数属性，增强节点影响力的结构因素;其次，通过预划分高影响力节点生成骨干网络，增强种子的结构密度;最后，以稠密子图代替节点作为种子进行扩张，增加了社区结构的稳定性。仿真结果表明，TSCDA能够挖掘出数量较少、规模较大的社区结构，并在模块度以及F-Score等指标上表现出一定的性能优势。
1 基于节点影响力识别的种子节点选取方法
用无向图G=（V，E）表示社交网络，其中V代表网络中个数为n的节点集合，E代表网络中个数为m的链接关系集合。图1给出了一种具有强聚合特性的社交网络结构（社区网络）。
社会网络中，节点u的邻居集合定义为：
这里u和v代表网络节点，V代表网络中的节点集，如果u和v之间存在边（u，v），则（u，v）属于边集E。节点u的节点度D（u）定义为与u直接相连的边的个数（或邻居元素的个数），满足D（u）=|N（u）|。
为了在影响力计算中引入结构的相似属性，提出从节点相似性以及链接相似性双重角度构造影响力评价函数。
Jaccard系数Juv用于比较社会网络中节点之间的结构相似性。其定义为：
N（u）和N（v）分别代表节点u和节点v的邻居节点。JuvJuv取值范围为[0，1]，其值越大，节点u和节点v的共有邻居节点就越多，邻域结构也就相对越稠密。
边介数用来度量社会网络中所有节点间的最短路径中经过该边的路径的数目占最短路径总数的比例。边介数值越大，该边越有可能成为连接社区内部节点的重要途径。其定义为：
其中guvst表示网络中任意节点s与任意节点t之间的最短路径同时经过节点u和v（即边euv）的条数。根据式（3），可以计算出图1各边的边介数指数，例如节点8和节点10，即（e8，10）之间边强度为EBET（e8，9）=11;节点9和节点10，即（e9，10）之间边强度为EBET（e9，10）=11。边介数反映了社区内部链接的稠密程度，是增加社区稳定性的关键参数。
受牛顿万有引力定律的启发，提出一种基于Jaccard系数以及边介数的影响力计算方法。社会网络节点u对节点v的影响力评分定义为：
这里D（u）和D（v）分别表示节点u和节点v的度。由于节点度在局部环境反映了节点链接能力，因此在本文中被用来衡量社会网络节点的质量。节点之间的距离d（u，v）用节点间的相异程度加以衡量，满足d（u，v）=1-Juv。其中Juv代表节点u和节点v的Jaccard相似度。G是影响力常量，在实验中通常取值为1。
节点在局部社区的影响力评分Iscore（u）定义为该节点对其所有邻居的节点影响力评分之和。进而有：
式（5）中，v∈N（u）表明节点v是节点u的邻居节点。Iscore（u）的值越大，说明节点u在局部环境的影响强度越大，表明越有可能成为种子节点。根据式（5），可以计算出图1各节点的影响力分数。例如节点10的影响力分数：
因此节点10在网络中影响力分数Iscore（u10）=275。
下面给出基于节点影响力识别的种子节点选取过程。算法通过式（5）计算社会网络每个节点的影响力评分。其伪代码如下：
算法1 具有高影响力的初始种子选取算法
输入：社会网络G=（V，E）
输出：高质量节点集合S
1）初始化集合S为空集;
2）遍历社会网络的所有节点，根据公式（5）计算社会网络所有节点的节点影响力评分;
3）对于任意节点，如果它的影响力评分大于其任一邻居的影响力评分，则为高影响力种子节点，将其存储到集合S;
4）输出集合S。
根据算法1，计算图1中节点1到节点10的影响力评分，具体如表1所示。在本文中，如果一个节点的影响力分数大于其任一邻居的影响力评分，则为高影响种子节点。例如，节点8的邻居节点为6，7，9，10。通过表1可知，节点8的影响力评分大于节点6，7，9，10的影响力评分，因此节点8为高影响力节点。
2 多点种子预划分的二阶段社区发现算法
本节给出多点种子预划分的二阶段社区发现算法。首先，根据算法1选取网络中的高影响力种子节点，对这些节点利用K-means聚类算法进行初始划分，识别出由高质量节点组成的种子社区即骨干社区;然后提出一种基于吸引力度量的社区识别算法将社会网络中其余节点按特定规则有选择性的加入骨干社区中，从而完成社区划分。该方法的优势在于充分考虑了种子节点之间稠密性以及关联性，有助于提高社区的稳定程度。
2.1 基于K-means聚类的骨干社区识别
本文采用K-means算法作为骨干社区的初始化算法，其距离度量公式在式（7）给出。
式中：minDis（A，B）为在社会网络中节点A，B间最短路径长度;comNeighbor（A，B）为节点A，B间共同邻居数量;C为迭代中心，初始值为0;Dis（A，B）为A、B两点的距离，该值与A、B两点的最短路径长度呈正相关，与A、B两点的共同邻居数量呈负相关。 K-means算法在迭代时依靠簇内所有节点的平均坐标设定新中心。然而社区不存在坐标，因此需要重新定义中心选取方式。本文选取到簇内其他节点的距离之和最小的节点作为新的中心节点，具体如式（8）所示。
式中：N（i）表示第i个社区内的节点集合。K-means算法的最终输出1棵骨干社区层次化树，采用模块度函数在层次化树上进行分割，获取质量最高的社区划分。模块度函数Q是Newman[19]在2004年提出的概念，用以评价社区划分的质量，其定义为：
式中：eii代表社区i中边的期望;ai代表链接到社区i中的边数的期望。模块度的形式化定义是社区内的边数减去随机产生的边的期望，因此模块度越高，社区内外边比例就越大，社區划分结果就越好。
我们发现，算法在层次聚类时模块度函数Q的取值并不是单调递增或单调递减的，因此每当有社区进行合并操作，就需要重新计算Q值，能对产生最大Q值的两个社区合并。为简化计算，每次仅计
算Q的变化部分，即向Q值增大最多或者减少最小的方向进行社区合并。Q函数的变化量计算公式如下所示。
对能产生最大Q值的两社区进行合并，直到所有节点合并至同一社区。算法的伪代码如下：
算法2 利用K-means聚类算法实现种子节点初始划分
输入：3个种子节点集合，社会网络G
输出：骨干社区集合BC={BC1，BC2，…BCn}
1）选取这3个种子节点进行初始聚类;
2）根据距离度量式（7）计算任意两节点之间的距离;
3）比较任意两点间的距离，将节点划分至距离最近的节点簇内;
4）对于每个簇内，分别计算簇内每个节点与簇内的其他节点距离之和，取和最小的节点作为新的中心节点;
5）迭代步骤4）、5），直到中心节点不发生改变;
6）对K-means算法产生的社区按照式（10）计算两两之间合并产生的ΔQ，将使ΔQ增加或减少的两个社区进行合并，并按照式（9）计算当前Q值，保存Q值及当前社区划分;
7）对步骤7）进行迭代，直到所有节点都包含在一个社区或不能进行社区合并;
8）比较每次合并的Q值大小，取Q值最大的社区作为最终的结果。
2.2 基于吸引力度量的社区识别过程
算法2结束后，会对社会网络中影响力较高的前3个节点进行预划分，识别出由高影响力节点组成的种子社区即为骨干社区。而网络中影响力较低的n-3个零散节点可能处于孤立状态，因此需要将其合并到骨干社区之中。提出一种基于影响力分析的吸引力度量函数，将网络中零散节点添加到对其吸引力较高的骨干社区。对于任意骨干社区BC和节点u，BC对u的吸引力度量函数attract（BC，u）的定义为：
式中：∑v∈BC∧v∈N（u）NG（u，v）表示节点u对当前所在骨干社区的所有邻居节点的影响力评分数之和;Iscore（u）表示节点u的影响力评分。attract（BC，u）的值越大，节点u受骨干社区BC吸引而加入社区BC的可能性就越大，反之节点u成为骨干社区BC内部节点的概率较低。
设定了吸引力阈值β，对于节点u以及任意社区BC，若attract（BC，u）>β，则节点u属于骨干社区BC。节点u可能同时加入多个社区结构，因此社区具有重叠性。在图1中，假设骨干社区BC1包含的节点集合为{1，2，3，4，5}，骨干社区BC1对节点6的吸引力函数为：
假设BC2的骨干社区包含节点集合为{7，8，9，10}，骨干社区BC2对节点6的吸引力为：
若β=0.4，则节点6不属于骨干社区BC1，属于骨干社区BC2。
下面给出基于种子扩张的社区发现算法，算法的伪代码如下：
算法3 基于种子扩张的社区发现算法
输入：高影响力节点构成的社区集合BC，社区网络G
输出：社区划分结构
1）将网络中高影响力节点标记为true，其余n-3个节点标记为false;
2）将网络中标记为false的节点按照式（11）依次对骨干社区集合BC={BC1，BC2…BCn}进行计算;
3）对每个标记为false的节点按照不同的骨干社区的计算，选取attract（BC，u）最大的值并将该节点加入到对应的骨干网络;
4）将加入骨干社区网络的节点标记为true;
5）重复执行步骤2），步骤3）和步骤4），直到社区网络中所有节点都标记为true;
6）输出社区划分结构。
为了挖掘网络的社区结构，首先将网络除3个高影响力节点外的节点都标记为false，若节点划分到一个社区中，则该节点标记为ture。
在基于吸引力度量的种子扩张过程的伪代码中，第一步为遍历n个高影响力评分节点社区集合。第二步以及第三步为计算集合BCi中对n-3吸引度量函数值attract（BCi，v）不小于给定的阈值β的节点。若节点attract（BCi，v）值大于或等于阈值，将该节点合并到当前的社区中，若一个节点属于多个社区，则称该节点为重叠节点。将该节点加入到attract（BCi，v）值最大的骨干社区中。最后将加入骨干社区的节点标记为true，得到最终的社区结构划分结果。社区合并本质上是一种贪心策略，然而由于网络本身存在稀疏性，在实际的种子扩张中零散节点邻接社区要远小于其邻接的社区数，这有效的控制了算法的时间开销。
2.3 算法的时间复杂度分析
假设社会网络G包含有n个节点和m条边，算法1在求解节点的影响力强度时，时间复杂度为O（n）。在算法2中基于K-means聚类算法将O（l）个节点进行合并得出骨干网络，其时间复杂度为O（kl），最坏的情况下将O（n）个节点进行合并，故算法2的时间复杂度为O（kn）。在算法3中，在社区扩展阶段将O（n）个节点加入到O（k）个骨干社区中，该过程重复执行O（n）次，所以找到所有的最终社区的时间复杂度为O（kn2），若k<<n，则时间复杂度为O（n2），在最坏的情况下有O（n）个骨干网络，则找到所有的最终社区的时间复杂度为n3。经过以上分析，本算法最差情况下时间复杂度为O（n+kn+n3）=O（n3）。 3 实验结果与分析
本节给出算法在人工合成网络以及真实数据集上的运行结果。实验的运行环境为Intel Core i5-7300HQ 2.5GHz处理器，8GB内存，Windows 10操作系统，算法采用Python与Matlab R2016a混合编程。
3.1 NMI指数
Danon等[20]提出归一化互信息（normalized mutual information，NMI），度量社区集合之间的相似性。NMI基于混淆矩阵N，其中行表示真实的社区结构，列表示算法生成的社区。Ni表示矩阵N第i行所有元素的总和，Nj表示矩阵N第j列所有元素的总和。Nij是矩阵N的元素，表示同时属于真实社区i和算法生成社区j的节点数量。NMI公式定义为：
式中：CA代表网络中真实社区的数量;CB代表由算法生成社区的数量。如果探测出的社区结构和真实网络的社区结构相同则NMI=1;反之，如果所探测的社区结构和真实网络完全不同，则NMI=0。传统意义上的归一化互信息被用来量化两个分布之间的差异性，为了使之适用于社区差异性量化，实验中采用的了NMI的简化版本[21]。
3.2 F-SCORE
F-Score也是常用的社区发现算法度量指标。首先定义算法生成社区在全部社区中的比例。
式中，CR代表高质量节点所在的真实社区，CF代表高质量节点所在的探测社区。
Precision是正确划分节点的数量除以节点在CF中的数量，其定义为：
结合式（15）以及式（16），F-Score定义为：
3.3 人工合成网络社区识别结果
利用LFR-Benchmark提供的MATLAB数据生成器生成网络，网络中的部分重要参数设置如下。首先，生成网络规模为N=1 000的复杂网络，其中最小社区尺寸为10、最大社区尺寸为100。接下来设置网络的平均度为5、最大节点度为25、混合参数u的取值范围为0.1～0.8。在LFR Benchmark中，混合参数是一个独立参数，其值越大社区越难以发现，因此通常用来刻画算法的鲁棒性。
首先验证了不同混合参数下K-means聚类算法中的k取值不同时NMI指标变化情况，实验结果如图2所示。可以看出，初始时社区质量会随种子社区的不断增多而不断上升，但达到某一极值时，社区质量开始下降。这是因为初始种子过多会导致社区个数增加，进而降低社区内部的紧密程度。另一个发现是，社区结构较为模糊的网络中（u=0.8），需要更多的种子社区才能达到较好的发现效果。
接下来，验证TSCDA算法的性能。与Clauset[12]、LWP[13]、Chen[14]、LS[15]、LCDMC[16]以及VI[17]6种社区识别算法在人工合成网络社区进行比较，为了保证算法结果的客觀性，将相关参数按原有文献加以设定，算法的NMI指标以及F-Score在图3以及图4给出。
如图2及图3所示，当混合参数u等于0.1时，TSCDA在NMI以及F-Score的性能指标明显优于其它算法，具有一定的性能优势。随着混合参数u的不断增加，TSCDA算法和其他6种算法的NMI指标以及F-Score均呈现明显的下降趋势，当混合参数u等于0.5以及0.6时，TSCDA算法略优于VI算法和LCDMC算法，优于LWP以及LS算法;当混合参数u等于0.7以及0.8时，各算法性能较为接近，但总体来看，TSCDA算法仍然要优于其他6种社区识别方法，这表明TSCDA算法在结构指标上更贴近于内嵌社区。
3.4 真实网络社区识别结果
为了验证TSCDA算法在真实网络社区识别的性能，本节选取了在5种真实网络上，对比TSCDA算法与前文6种社区识别算法的性能差异。表2列出了所选择的真实网络的网络特征，其中Node代表节点个数、Link代表链接条数、d—表示网络的平均度、|C—|表示真实社区的平均大小、Community表示社区个数。我们从Amazon社区中移除了前5 000个子社区，保留了它的不同的社区。
还在DBLP计算机学科文献数据网络上测试了TSCDA算法与Clauset算法、LWP算法、Chen算法、LS算法、LCDMC算法以及VI算法的NMI指标以及F-Score指标。DBLP文献网络的特性如表3所示。|C|代表社区规模的范围，例如，（0，10]代表样本网络包含的社区大小大于0，小于等于10。我们同样移除了DBLP网络前5 000个社区中的子社区，并保留了它们不同的社区结构。
表4给出了各算法在真实网络上的NMI指标以及F-Score指标。相比其它6种方法，TSCDA具有一定的性能优势。一方面，TSCDA基于节点影响力扩展社区，因此在识别社区成员时准确度更高。另一方面，本文在节点影响力计算中加入了边介数属性，不仅考虑了节点自身的重要程度，还考虑了链接在局部区域中的重要程度。LWP和LS算法在个别网络中显示出比TSCDA更好的性能，例如在Football网络中LWP算法的NMI指标高于TSCDA约0.09、在Amazon网络中LS算法的F-Score高于TSCDA约0.02。一个可能的原因是Football网络的平均节点度较高，使得各算法在社区识别时更容易发现结构较为紧凑的局部结构。TSCDA算法在Dolpins网的准确性有所下降，这是由于Dolpins网络中的链接关系依靠于节点之间的接触历史，因此影响力识别时准确度一般。但是相比其它6种算法TSCDA算法仍然表现出一定的稳定性，进一步说明了TSCDA算法具有较高的鲁棒性。
图5和图6给出了各算法在DBLP引文网络上的性能指标。实验结果显示，当社区规模在0到10时（Label 0），TSCDA在社区识别性能上略低于其他6种算法表现的差。然而当社区规模大于10时（Label 1～10），TSCDA的表现性能明显优于Clauset、LWP、Chen、LS、LCDMC和VI算法，这表明TSCDA善于挖掘个数较多的社区结果，社区粒度更加细致。 4 结 论
为了解决传统社区识别方法社区稳定性较差这一问题，从节点相似性以及链接相似性两个角度入手，提出一种多点种子预划分的社区发现算法TSCDA。首先，在种子扩张算法的基础上，提出利用高质量节点构建骨干社区进行社区识别，提高社区结构的致密性;其次，将边介数属性加入到节点影响力的计算中，提高影响力计算中的结构相关性。人工合成网络和真实网络数据集上的仿真结果验证了TSCDA算法的效率和识别性能。
参 考 文 献：
[1] SANTO Fortunato. Community Detection in Graphs[J]. Physics Reports，2009，486（3）：26.
[2] JAVED M A， YOUNIS M S， LATIF S， et al. Community Detection in Networks：A Multidisciplinary Review[J]. Journal of Network and Computer Applications，2018， 108：87.
[3] AMOR B， VUIK S， CALLAHAN R， et al. Community Detection and Role Identification in Directed Networks： Understanding the Twitter Network of the Caredata Debate[J]. Dynamic Networks and Cyber-security， 2015， 25（2）：19.
[4] BAZZI M， PORTER M A， WILLIAMS S， et al. Community Detection in Temporal Multilayer Networks， with an Application to Correlation Networks[J]. Multiscale Modeling & Simulation， 2016， 14（1）：1.
[5] SHARMA S， SINGH A. An Efficient Method for Link Prediction in Complex Multiplex Networks[C]// 2015 11th International Conference on Signal-Image Technology & Internet-Based Systems（SITIS）. IEEE， 2015：452.
[6] DING X， ZHANG J， YANG J. A Robust Two-stage Algorithm for Local Community Detection[J]. Knowledge Based Systems， 2018， 14（7）：62.
[7] LANCICHINETTI A， FORTUNATO S， KERTSZ， JNOS. Detecting the Overlapping and Hierarchical Community Structure in Complex Networks[J]. New Journal of Physics， 2009， 11（3）：15.
[8] COSCIA M， ROSSETTI G， GIANNOTTI F， et al. DEMON：a Local-First Discovery Method for Overlapping Communities[C]// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2012：19.
[9] BAUMES J， GOLDBERG M， MAGDON-ISMAIL M. Efficient Identification of Overlapping Communities[C]// International Conference on Intelligence and Security Informatics， 2005：11.
[10]李婕， 王興伟， 郭静， 等. 面向移动通信网络的局部扩张群组构造方法[J]. 东北大学学报（自然科学版），2017，38（12）：1691.
LI Jie， WANG Xingwei， GUO Jing， et al. Clique Percolation Based Local Fitness Method for User Clustering in Telecommunication Network[J]. Journal of Northeastern University Natural（Science）， 2017，38（12）：1691.
[11]SU Y， WANG B， CHENG F， et al. An Algorithm Based on Positive and Negative Links for Community Detection in Signed Networks[J]. Scientific Reports， 2017， 7（1）：10874.
[12]CLAUSET， ARON. Finding Local Community Structure in Networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2005， 72（2）：26. [13]LUO F ， WANG J Z ， PROMISLOW E. Exploring Local Community Structures in Large Networks[J]. Web Intelligence & Agent Systems， 2008， 6（4）：387.
[14]JIYANG Chen， OSMAR Zaane， RANDY Goebel. Local Community Identification in Social Networks[C]// International Conference on Advances in Social Network Analysis & Mining. IEEE Computer Society， 2009：79.
[15]YING JUN， WU， HAN， et al. Local Community Detection Using Link Similarity[J]. Journal of Computer Science & Technology， 2012， 23（3）：69.
[16]FANRONG M ， MU Z ， YONG Z ， et al. Local Community Detection in Complex Networks Based on Maximum Cliques Extension[J]. Mathematical Problems in Engineering， 2014， 36（6）：1.
[17]YAOY ， WU W ， LEI M ， et al. Community Detection Based on Variable Vertex Influence[C]// IEEE International Conference on Data Science in Cyberspace. IEEE， 2016：145.
[18]齊金山， 梁循， 王怡. 基于种子节点选择的重叠社区发现算法[J]. 计算机应用研究，2017（12）：20.
QI Jinshan， LIANG Xun， WANG Yi. Overlapping Community Detection Algorithm Based on Selection of Seed Nodes[J]. Application Research of Computers，2017（12）：20.
[19]NEWMANM E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E， 2004， 69（6）：133.
[20]DANON， LEON， DUCH， et al. Comparing Community Structure Identification[J]. Journal of Statistical Mechanics， 2005， 206（9）：69.
[21]BAGROW， JAMES P. Evaluating Local Community Methods in Networks[J]. Journal of Statistical Mechanics：Theory and Experiment， 2008， 8（5）：26.
（编辑：温泽宇）