面向属性网络的重叠社区发现算法

杜航原 裴希亚 王文剑

摘 要：针对现实世界的网络节点中包含大量属性信息并且社区之间呈现出重叠特性的问题，提出了一种面向属性网络的重叠社区发现算法。融合网络的拓扑结构和节点属性定义了节点的密集度和间隔度，分别用于描述社区内部连接紧密和外部连接松散的特点。基于密度峰值聚类的思想搜索局部密度中心作为社区中心，在此基础上给出了非中心节点关于各个社区的隶属度的迭代计算方法，实现了重叠社区的划分。在真实数据集上进行了仿真实验，实验结果表明所提算法相对于LINK、COPRA和DPSCD能获得更好的社区划分结果。

关键词：属性网络;重叠社区发现;密度峰值聚类;社区中心;节点隶属度

中图分类号： TP391

文献标志码：A

Overlapping community detection algorithm for attributed networks

DU Hangyuan1， PEI Xiya1， WANG Wenjian2*

1.College of Computer and Information Technology， Shanxi University， Taiyuan Shanxi 030006， China;

2.Key Laboratory of Computational Intelligence and Chinese Information Processing of

Ministry of Education（Shanxi University）， Taiyuan Shanxi 030006， China

Abstract：

Realworld network nodes contain a large number of attribute information and there is an overlapping characteristic between communities. Aiming at the problems， an overlapping community detection algorithm for attributed networks was proposed. The network topology structure and node attributes were fused to define the intensity degree and interval degree of network nodes， which were designed to describe the characteristics of community — the dense interior connection and the sparse exterior connection respectively. Based on the idea of density peak clustering， the local density centers were selected as community centers. On this basis， an iteration calculating method for the membership of noncentral nodes about each community was proposed， and the division of overlapping communities was realized. The simulation experiments were carried out on real datasets. The experimental results show that the proposed algorithm has better performance in community detection than LINK algorithm， COPRA algorithm and DPSCD （Density Peaksbased Clustering Method）.

Key words：

attribute network; overlapping community detection; density peak clustering; community center; node membership

0 引言

社區结构作为一种数据组织形式广泛存在于各种复杂网络中[1]，如：引文网络中针对同一主题的相关论文往往形成同一社区[2]。社区内部的节点之间连接相对紧密，但是各社区之间的连接相对稀疏。社区结构是现实世界实体关系的一种映射，对于理解网络的拓扑结构和复杂系统的内部规律有着重要的作用[3]， 如：万维网中的社区是讨论相关主题的若干网站;电子电路网络中的社区可能是具有某一类特定功能的单元， 发现这些网络中的社区有助于研究人员有效地理解和开发这些网络[2]。近年来一些学者围绕这个问题展开了深入研究，形成了大量的研究成果，其中具有代表性的方法包括以下几类：基于模块性优化的社区挖掘方法、基于标签传播的社区挖掘方法、基于划分的社区挖掘方法和基于动力学的社区挖掘方法[4]。

早期的研究认为每个节点只能属于一个社区，即社区之间是相互独立的。随着研究的深入，人们发现现实世界中往往存在一些节点同时属于多个社区的情况，即社区结构表现出重叠特性[5]，例如：在学术合作网络中，一个学者可能同时参与多个学术团体;在蛋白质互作用网络中，一个蛋白质可以根据功能的不同被划分到不同的社区。在这些场景中，经典的面向独立社区的硬划分社区发现算法不再适用。重叠社区发现问题逐渐引起人们的关注，目前，面向重叠社区的社区发现方法大体上可以分为以下5类：1）基于派系过滤的算法（Clique Percolation Method， CPM）[6]，该方法是最早开始研究重叠社区结构的算法，由Palla等[7]提出，通过寻找网络中各个由互相连通的k完全子图组成的k派系社区来进行重叠社区发现。随后，Farkas等[8]把CPM算法扩展到了加权网络，提出了CPMw算法，规定只有内部密度超过给定阈值的k派系才可以成为一个社区。2）基于局部扩展的算法，此类方法一般通过一个局部适应度函数来对所选取的种子节点进行扩展，代表算法是LFM（Local Fitness Method）[9]。在LFM中，适应度函数的概念被提出，重叠社区发现的标准是适应度函数最大化。由于LFM的种子节点是随机选取的，导致算法稳定性较差。3）基于模糊检测的算法，不直接给出节点的社区划分结果，而是用隶属度表示节点属于每个社区的概率，代表算法是模糊C均值（Fuzzy CMeans， FCM）算法[10]，该算法利用模糊C均值方法对网络节点进行改进分析，可以挖掘网络中的k个重叠社区。4）基于链接密度的算法，将边链接密度作为重点，代表算法为LINK算法[11]，该算法对网络中的边进行层次聚类分析，以此完成重叠社区发现。5）由独立社区发现扩展而来的算法，将独立社区发现算法进行改进[12]，使其具有重叠社区发现的能力。如COPRA算法[13]就是由经典的标签传播算法（Label Propagation Algorithm， LPA）扩展而来，COPRA算法在执行时会使用隶属度来帮助节点决定归属哪个社区，如果节点对于邻居节点所在社区的隶属度都低于阈值，那么节点就随机选择一个社区。

上述方法仅依赖拓扑关系进行社区结构的发现，但社区的形成除了与节点间拓扑结构相关外，还受到另外一类重要信息的影响，即节点的属性信息[14]。在现实世界中，这种影响表现为：在社交网络中，有相似背景信息和个人爱好的用户往往构成同一社区;在蛋白质互作用网络中，有相同功能的蛋白质容易形成同一社区。为此，一些研究人员开始尝试利用节点属性信息发掘网络中的社区结构，如：kSNAP（Summarization by Grouping Nodes on Attributes and Pairwise Relationships）是一种先根据节点属性值是否相同把节点分成不同的簇结构，然后把簇结构作为输入来实现社区发现聚类算法[15];类似地，AP（Affinity Propagation）算法把节点间的属性相似度作为输入，迭代执行算法，直到出现一个高质量的样例集和相应的簇[16]。还有一些学者利用拓扑结构信息和节点属性信息进行社区发现研究，如：文献[17]先利用属性信息计算出节点间的属性相似度，再通过拓扑结构关系计算出结构相似度，最后将二者的加权和作为节点之间的距离度量进行社区的划分;MISAGA（Mining Interesting Subgraphs in Attributed Graph Algorithm）[18]通过使用一种统计度量的方式来发现社区，该统计度量方法首先根据属性信息标识出具有一定关联强度的属性值，如果一对顶点的属性值满足一定关联强度，再通过拓扑结构信息计算出一个称为关联度的度量，在此基础上发现社区。这些算法在社区发现过程中，利用拓扑结构或属性信息从某一方面对节点间的相似性关系进行度量，忽略了两类信息在网络社区形成过程中的共同作用，导致社区发现结果可靠性不高。

网络社区结构具有“内部联系紧密、外部联系松散”的本质特征， 探求拓扑关系和节点属性对这一本质特征形成的共同作用机制，以及有效描述和度量，是网络社区发现中的关键问题。此外，在社区发现过程中对社区结构呈现出的重叠特性进行切实表达，也非常重要。针对上述问题，本文提出了一种面向属性网络的重叠社区发现方法，主要工作如下：

1） 融合网络拓扑结构信息和节点属性信息，提出网络社区本质特征的描述和度量方法;

2） 基于密度峰值聚类思想设计了网络社区中心的快速搜索算法;

3） 给出了非中心节点关于各社区隶属度的迭代计算方法，以实现重叠社区划分;

4） 在真实网络上的实验结果表明，本文提出的社区发现算法能有效发现网络中的重叠社区。

1 密度峰值聚类

密度峰值聚类[19]基于一个假设：簇中心被一些具有较低局部密度的节点包围，并且与具有更高局部密度的节点距离较远。如果将网络社区视为复杂网络中的簇结构，那么社区中心的特性将与这一假设保持一致，即社区中心作为密度中心被一些具有较低局部密度的节点包围，且与具有更高局部密度的节点（其他社区中心）距离较远。因此，密度峰值聚类思想很适合用来反映社区结构“内部联系紧密、外部联系松散”的特性。

在密度峰值聚类算法中，对于每个节点i，计算它的局部密度ρi和它距離更高密度的节点的距离δi，这两个值的计算都只依赖于数据节点之间的距离dij。节点i的局部密度ρi定义如式（1）：

ρi=∑jX（dij-dc）（1）

式中： 如果x<0，则X（x）=1;否则X（x）=0，dc是一个截断距离。节点i的密度ρi等于与该节点的距离小于截断距离dc的节点个数。节点i到更高密度节点的距离δi是节点i与所有比它密度高的节点之间距离的最小值，定义如式（2）：

δi=minj：ρj>ρi（dij） （2）

对于有最高密度的节点，定义为δi=maxj（dij），因此，将δi值异常大的节点作为簇中心。在确定簇中心之后，将剩余的节点分配到比其密度高并且距离它最近的簇中心所在的簇。

2 一种面向属性网路的重叠社区发现算法

密度峰值聚类基于几何空间中的欧氏距离定义了节点的局部密度和到更高密度节点间的距离，很适合用来描述社区结构的特性。网络数据由两类信息构成：一种是拓扑空间中的拓扑结构; 另一种是特征空间中的节点属性，这使得无法直接基于几何空间为网络数据定义密度和距离，必须探求新的适合于表达网络数据本质特征的度量手段。为此，本文提出了密集度和间隔度分别用来反映社区内部联系紧密、外部联系松散的特性。

2.1 节点密集度

对于给定的属性网络G=〈V，E，F〉，其中V={v1，v2，…，vn}表示由网络中的n个节点组成的集合，E={e1，e2，…，em}表示由网络中的m条边组成的集合，F={f1， f2，…， fd}表示由节点的d个属性向量组成的集合。

网络社区是由拓扑结构和属性信息共同作用形成的，本文算法在社区发现过程中为了充分利用两者的融合信息，通过计算满足一定拓扑结构的网络子图（模体[20]）的属性同质值，进而求得该子图中任意两个节点间的属性结构连接强度[21]，属性结构连接强度越大，两个节点的属性同质强度越大且结构联系越紧密（如图1所示，用Mmn表示由n个节点、m条边组成的网络子图（模体））。

节点间的属性同质值表示两个节点的属性同质强度，其值越大，节点间的属性同质强度越大。节点vi和节点vj间的属性同质值HG（i， j）定义如式（3）：

HG（i， j）=∑αiαjS（αi，αj）‖fi‖‖fj‖ （3）

其中：fi和fj分别表示节点vi和节点vj的属性向量，αi和αj分别表示属性向量fi和fj中非零元素的下标。S（αi，αj）为节点vi的第αi个属性与节点vj的第αj个属性的联系强度，表示两个节点的属性相似程度。若fd（i）=1且fd（j）=1，则S（αi，αj）=1。

在得到两个节点间属性同质值的基础上，进一步对模体的属性同质值定义如式（4）：

Ht=1m∑mw=1HG（uw，vw） （4）

其中：Ht表示第t个模体的属性同质值，m表示第t个模体中边的总数，uw和vw表示模体中第w条边的两个端点。在此基础上，对于包含在模体中的任意两个节点之间的属性结构连接强度定义如式（5）：

aij=∑{i， j}∈ItHt （5）

其中：It表示第t个模体，{i， j}∈It表示节点vi和节点vj同时被包含在It中。

社区结构具有内部联系紧密的特点，因此社区内的节点之间不仅有较高的属性同质强度，还存在较为密切的拓扑连接关系。基于以上认识，将网络节点的密集度定义如式（6）：

Mi=∑n-1j=0aij （6）

其中：Mi为节点vi的密集度，n为网络中的节点数量。节点vi的密集度定义为该节点与社区内其他节点间的属性结构连接强度之和，其值越大，表示该节点与社区内其他节点的属性同质程度越大，结构联系越紧密。

2.2 节点间隔度

社区结构外部联系松散，即不同社区之间的属性同质强度降低，拓扑连接关系也较为松散。为了反映这种特性，首先将节点的属性信息和结构信息进行融合求得每条边的边适应度[22]，在此基础上定义节点间隔度，用来度量节点与更高密集度的节点间的距离。

若两个节点相邻，则对其直接相似度定义如式（7）：

d_t（i， j）=l（i， j）l（i）+∑t∈N（i）∩N（j）1I（t） （7）

其中：d_t（i， j）为节点vi与节点vj之间的直接相似度;l（i， j）为节点vi和节点vj之间的属性相似度，表示两个节点的属性相似程度;l（i）为节点vi与所有邻居节点的属性相似度总和;I（t）为节点vt的度。在此基础上对不相邻的两个节点间的间接相似度定义如式（8）：

i_t（i， j）=mdmax-di， j+1dmax （8）

其中：i_t（i， j）为节点vi与节点vj间的间接相似度，m=min（d_t（i，i1），d_t（i1，i2），…，d_t（in， j）），dmax为设定的阈值，di， j为节点vi与节点vj之间的路径长度。

基于以上两个定义，可求得网络中任意两个节点vi和vj间的相似度t（i， j），定义如式（9）：

t（i， j）=d_t（i， j），iandjare adjacent

i_t（i， j），其他（9）

在求得节点间相似度的基础上，对网络中每条边的边适应度定义如式（10），其值越大，表示两个节点联系越紧密。

Sij=SFjij+SFiij （10）

其中：Sij表示边ei， j的边适应度，SFjij和SFiij分别表示边ei， j相对于邻居社区Fi和Fj的边适应度，Fi=N（i）+{i}-{j}和Fj=N（j）+{j}-{i}表示边ei， j的邻居社区，N（i）和N（j）分别表示节点vi和节点vj的邻居节点。以图2为例，N（1）={2，4，5}，N（5）={1，6，7}，边e1，5的邻居社区为F1={1，2，4}，F5={5，6，7}。

SFjij=a+ca+b+d-aa+b （11）

其中：t（p，q）表示节点vp和节点vq之间的相似度，a=∑p，q∈Fj，p>qt（p，q）表示社区Fj内节点间相似度总和，b=∑p∈Fi，q∈Fjt（p，q）表示社区Fj内节点与其邻居社区Fi内节点间相似度总和，c=∑p∈Fjt（i，p）示节点vi与邻居社区Fj内节点间相似度总和，d=∑q∈（Fi-{i}）t（i，q）表示节点vi与社区Fi内节点间相似度总和。

为了刻画不同社区之间联系松散的特性，将节点的间隔度定义为节点vi与所有比它密集度大的节点之间边适应度的最大值的倒数，其值越大表明节点vi与有更高密集度的节点之间联系越松散。间隔度定义如式（12）：

Di=1maxvj∈V：Mj>Mi（Sij） （12）

其中：Di为节点vi的间隔度，节点vj是比节点vi的密集度大的点，Mi和Mj分别表示节点vi和节点vj的密集度。

2.3 搜索社区中心

社区内的节点间具有较强的属性同质强度和较为密切的结构联系，社区间的节点具有较弱的属性同质强度和较为松散的结构联系，本文利用密集度和间隔度描述社区的这一结构特性。中心节点作为社区的核心，对于这一特性的表现最为显著，因此相比社区内的一般节点应具有较大的密集度和间隔度。基于这一认识，本文选择密集度和间隔度乘积最大的K个节点作为网络中各个社区的中心。

算法1 社区中心选择算法。

输入 网络G=〈V，E，F〉，邻接矩阵Bn×n，节点属性值;

输出 社区中心节点集合C={ck}Kk=1。

程序前

1）

for each node vi∈V

2）

通过式（3）計算模体中每条边的两个端点间的属性同质值HG（i， j）;

3）

通过式（4）计算模体的属性同质值Ht;

4）

if （i， j）∈Mmn

5）

通过式（5）计算节点vi与vj间的属性结构连接强度aij;

6）

else

7）

aij=0;

8）

end if

9）

通过式（6）计算节点vi的密集度Mi;

10）

if Bij=1

11）

通过式（7）计算节点间的直接相似度d_t（i， j）;

12）

else

13）

通过式（8）计算节点间的间接相似度i_t（i， j）;

14）

end if

15）

通过式（9）计算节点间的相似度t（i， j）;

16）

通过式（11）计算边ei， j相对于邻居社区Fi的边适应度SFjij;

17）

通过式（10）计算边ei， j的边适应度Sij;

18）

通过式（12）计算节点的间隔度Di;

19）

end for

20）

将节点的密集度Mi与间隔度Di的乘积计作γ，选取γ>α（α为给定阈值）的节点作为社区中心ck;

21）

return C={ck}Kk=1

程序后

2.4 节点的社区划分

在具有重叠特性的网络中，某些节点可能同时归属于多个社区，本文使用隶属度表达节点归属于不同社区的概率。假设网络中有r个社区，则节点vi关于不同社区的隶属度向量为pi={pi1，pi2，…，pir}，pik表示節点vi关于第k个社区的隶属度。 假定一个社区中心只能属于一个社区，设第k个社区中心的节点编号为ck，则pcju=1（u=j），pcju=0（u≠j）。

对于非中心节点，其关于不同社区的隶属度受到所有密集度比它大的社区中心的影响，即若非中心节点vi的密集度大于社区中心vk的密集度，则节点vi关于社区k的隶属度pik=0。为便于计算，将网络中的所有节点按照密集度大小降序排列，从非中心节点中密集度最大的节点开始计算。节点vi关于社区k的隶属度pik定义如式（13）：

pik=Sik∑u∈NiSiu（13）

其中：Sik为边ei，k的边适应度，其值越大表示两个节点联系越紧密; Ni表示比节点vi的密集度大的社区中心节点的集合。

通过上述方法计算得到所有非中心节点关于不同社区的隶属度。接着，将非中心节点分配到隶属度最大的社区，例如对于节点vi，如果k=argmaxu{piu，u=1，2，…，r}，那么就将节点vi分配到社区k。同时，若节点vi关于社区k的隶属度与关于社区r的隶属度满足pir/pik>θ（0<θ<1），θ为阈值，则认为节点vi是社区k和r的重叠节点。

算法2 节点社区分配算法。

输入 社区中心节点集合C，网络中所有节点集合V，节点密集度M，节点间隔度D，阈值θ;

输出 节点的社区分配结果集合。

程序前

1）

for each community center ci∈C

2）

for each community k=1，2，…，K

3）

if ci为第k个社区的中心;

4）

pik=1;

5）

else

6）

pik=0;

7）

end if

8）

end for

9）

end for

10）

for each noncommunity center vi∈V-C

11）

for each community k=1，2，…，K

12）

if Mi

13）

通过式（13）计算pik;

14）

else

15）

pik=0;

16）

end if

17）

end for

18）

if k=argmaxu {piu，u=1，2，…，r}

19）

将节点vi分配到社区k;

20）

end if

21）

if pir/pik>θ

22）

将节点vi作为社区k和r的重叠节点;

23）

end if

24）

end for

程序后

3 实验结果及分析

3.1 实验设置

为了验证算法的有效性，选取LINK[11]算法、COPRA[13]算法和DPSCD（Density Peaksbased Clustering Method）[17]与本文方法在4个数据集上进行实验分析与比较。

3.1.1 数据集

为了测试算法的性能，本文实验选用斯坦福大学大型网络数据集中的3个真实世界网络数据[23]作为测试集，分别为facebook、twitter和gplus，以及一个在Flickr上抓取的数据集。数据集中的节点编号表示一个用户，节点之间的连边表示两个用户有联系，属性信息包括用户的性别、兴趣、所在地区等信息，每个节点的属性信息均用1或0标识。这4个数据集的详细信息见表1。观察表1的最后一列数值可知， flickr网络相对于其他三个网络比较稠密。

3.1.2 评价准则

由于模块度函数Q只适用于非重叠社区的情形，因此本文选取扩展模块度（Extended modularity， EQ）[24]函数用来衡量重叠社区结构划分的质量，其值越大表明社区划分效果越好，扩展模块度EQ函数定义如式（14）：

EQ=12m∑y∑i∈gy， j∈gy1QiQjBij-kikj2m （14）

其中：m为网络中的连边总数;Qi、Qj为节点vi、vj所属的社区个数;Bij為网络邻接矩阵中的元素;ki、kj分别为节点vi、vj的度;gy为第y社区包含的节点集。

另外，本文还采用精确率（Precision，P）、召回率（Recall，R）和F1measure将召回率和精确率相结合，作为综合评价指标F来衡量算法的性能。具体计算公式定义如式（15）：

R=TPTP+FN

P=TPTP+FP

F=2·PRP+R（15）

由文献[25]的定义，Cr（θ）={vi|pi，r≥θ}，其中Cr表示第r个重叠社区，θ为隶属关系阈值（0<θ≤1），pi，r表示节点i关于社区r的隶属度，来控制重叠社区的规模。通过计算重叠社区中的每个节点来获取本文算法的平均准确率、平均召回率和平均F1值，具体计算公式定义如式（16）～（18）：

P（θ）=∑ r=1，2，…，r vi∈Cr（θ）Cr（θ）∩TiCr（θ）∑ r=1，2，…，r vi∈Cr（θ）1 （16）

R（θ）=∑ r=1，2，…，r vi∈Cr（θ）Cr（θ）∩TiTi∑ r=1，2，…，r vi∈Cr（θ）1 （17）

F1=2P（θ）R（θ）P（θ）+R（θ） （18）

3.2 实验结果及分析

表2～4中各算法的参数设置如下：对于LINK算法，设置参数c表示其将链接社区转化为节点社区时的最小边数量，令c的取值范围为4～15;对于COPRA算法，设置参数v表示一个节点可以归属于不同社区的个数，令v的取值范围为1～10;对于DPSCD，设置参数α表示在社区划分过程中属性信息所占的权重，令α的取值范围为0.2～0.8;对于本文算法，阈值θ为节点关于某个社区的隶属度，设置为[0.1，1]。

在4个数据集上分别选择具有不同社区个数K的子网络进行仿真实验，结果如表2～4所示。其中，每个算法分别选取在不同参数下的最大扩展模块度EQ值作为最终的结果，表中加粗的数字分别表示各个网络上EQ的最大值。由于本文算法融合了网络拓扑结构和节点属性信息，充分考虑到了在社区结构形成过程中两者的共同作用关系，在真实网络上性能表现良好，实验结果整体优于只考虑网络拓扑结构的LINK算法、COPRA算法以及独立运用拓扑结构和节点属性两类信息进行社区划分的DPSCD。使用LINK算法获得的EQ是所有结果中最差的，这是由于LINK算法构造的一些小的链接社区影响了节点社区的形成。COPRA算法只是在少数情况下有较高的EQ值，这是由于该算法只依赖拓扑结构信息进行社区发现，并且在执行过程中存在较大随机性，难以获得较高的稳定性。而DPSCD的EQ值在大部分情况下比LINK和COPRA算法的EQ值高，这是由于DPSCD将节点属性信息运用于社区发现过程，同时该算法利用拓扑结构和节点属性分别在拓扑空间和特征空间中对节点相似性进行度量，忽略了二者对社区形成的共同作用，因此获得的EQ值比本文算法的EQ值低。另外，本文算法相较于其他三种算法，在同一种数据集的不同社区个数上计算得到的EQ值整体变化相对平稳，即网络中包含的社区数目较多时，算法性能对于社区数目不敏感，有较强的鲁棒性;在社区个数相同的情况下，该算法在flickr数据集上计算得到的EQ值明显优于在其他3个数据集上计算得到的值，表明本文的算法更适合于稠密网络。

表2～4中的提升率是指在同一个数据集上本文算法的EQ值相较于其他三种算法中最大的EQ值的提升程度。在以下三个表中计算的12次提升率中，有9次提升率的值大于0，并且在社区个数K为20和30时，本文算法在flickr数据集上的提升率均大于在其他3个数据集上的提升率，表明本文算法在稠密网络上的社区发现效果较好。

四种算法获得的召回率、精确率以及综合指标如图3～6所示。为了避免实验的随机性对结果产生影响，实验结果均为多次实验取平均值。本文算法能够融合拓扑结构和节点属性两类信息对社区结构的本质特征作出有效表达，因此在四个数据集上计算得到的平均精确率、平均召回率和平均F1measure值优于其他三种方法，而且结果比较稳定。如在flickr数据集上，本文算法的平均F1measure值在0.60左右波动，且波动范围不大，DPSCD的平均F1measure值在0.55左右波动，另外两种算法的平均F1measure值大部分都在 0.5以下。除此之外，还可以观察到DPSCD和本文算法在4种数据集上获得的平均精确率和平均召回率变化也比较平稳，而LINK算法的结果波动较大，这是由于LINK算法将所有的边都划分到特定的链接社区中，容易形成网络社区“过度重叠”的现象，导致社区发现效果不佳。

本文算法在不同阈值θ下获得的平均精确率、平均召回率和综合指标的值如表5所示，表中加粗的数字表示在同一个数据集上，不同阈值下综合指标F所取得的最大值。若在不同阈值下取得的综合指标值相同，则将在较小阈值下取得的值加粗。从表中可以看出，在facebook数据集和flickr数据集上，当阈值θ取0.8时，综合指标F获得最大值;在twitter数据集和gplus数据集上，当阈值 θ取0.9时，综合指标F获得最大值。因此本文算法在阈值θ取0.8或0.9时，性能最优。

4 结语

针对属性网络的重叠社区发现问题，本文提出了一种有效的社区发现算法，建立对社区结构内部联系紧密、外部联系松散这一本质特性的有效表达，基于密度峰值聚类思想进行社区中心快速搜索，通过隶属度迭代计算实现重叠节点的发现和重叠社区的划分。在真实网络上与现有社区发现方法进行大量对比实验，实验结果验证了该算法的有效性。

算法在計算节点间隔度的过程中，遍历不相邻节点之间的全部路径具有较高的计算复杂度，因此在未来工作中，将尝试使用并行计算技术拓展算法处理大规模网络计算的能力。 另外，还将围绕社区数量的自动确定开展研究，使算法能够应用于社区数量未知的场景中。

参考文献 （References）

[1]MA T， WANG Y， TANG M， et al. LED： a fast overlapping communities detection algorithm based on structural clustering[J].Neurocomputing， 2016， 207： 488-500.

[2]时京晶. 三种经典复杂网络社区结构划分算法研究[J]. 电脑与信息技术， 2011，19（4）：41-43.（SHI J J. Research on three classical complex network community structure partition algorithms[J]. Computer and Information Technology， 2011， 19（4）：41-43.）

[3]赵建军，汪清，由磊，等. 基于信息传递和峰值聚类的自适应社区发现算法[J]. 重庆大学学报， 2018， 41（11）： 76-83. （ZHAO J J， WANG Q， YOU L， et al. Adaptive community discovery algorithm based on information transfer and peak clustering[J].Journal of Chongqing University， 2018， 41（11）： 76-83.）

[4]刘大有，金弟，何东晓， 等.复杂网络社区挖掘综述[J]. 计算机研究与发展， 2013， 50（10）：2140-2154. （LIU D Y， JIN D， HE D X， et al. Review of mining of complex network communities[J].Journal of Computer Research and Development， 2013， 50（10）：2140-2154.）

[5]朱牧，孟凡荣，周勇. 基于链接密度聚类的重叠社区发现算法[J]. 计算机研究与发展， 2013， 50（12）：2520-2530. （ZHU M， MENG F R， ZHOU Y. Overlapping community detection algorithm based on link density clustering[J]. Journal of Computer Research and Development， 2013， 50（12）：2520-2530.）

[6]SARSWAT A， GUDDETI R M R. A novel overlapping community detection using parallel CFM and sequential nash equilibrium[C]// Proceedings of the 2018 10th International Conference on Communication Systems & Networks. Piscataway： IEEE， 2018： 649-654.

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

[8]FARKAS I，  BEL D， PALLA G， et al. Weighted network modules[J]. New Journal of Physics， 2007， 9：180.

[9]LANCICHINETTI A， FORTUNATO S， KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics， 2009， 11： 033015.

[10]ZHANG S， WANG R S， ZHANG X S. Identification of overlapping community structure in complex networks using fuzzy cmeans clustering[J]. Physica A： Statistical Mechanics and its Applications， 2007， 374（1）： 483-490.

[11]AHN Y Y， BAGROW J P， LEHMANN S. Link communities reveal multiscale complexity in networks[J]. Nature， 2010， 466（7307）： 761.

[12]GREGORY S. An algorithm to find overlapping community structure in networks[C]// Proceedings of the 11th European Conference on Principles of Data Mining and Knowledge Discovery. Berlin： Springer， 2007： 91-102.

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

[14]張振宇，朱培栋，王可，等.拓扑结构与节点属性综合分析的社区发现算法[J].计算机技术与发展，2018，28（4）：1-5.（ZHANG Z Y， ZHU P D， WANG K， et al. Community detection algorithm for comprehensive analysis of topology and node attributes[J]. Computer Technology and Development，2018，28（4）：1-5.）

[15]TIAN Y， HANKINS R A， PATEL J M. Efficient aggregation for graph summarization[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2008： 567-580.

[16]FREY B J， DUECK D. Clustering by passing messages between data points[J]. Science， 2007， 315（5814）： 972-976.

[17]WANG M， ZUO W， WANG Y. An improved density peaksbased clustering method for social circle discovery in social networks[J]. Neurocomputing， 2016， 179： 219-227.

[18]HE T， CHAN K C C. MISAGA： an algorithm for mining interesting subgraphs in attributed graphs[J]. IEEE Transactions on Cybernetics， 2017， 48（5）： 1369-1382.

[19]RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks[J].Science，2014， 344（6191）： 1492-1496.

[20]BENSON A R， GLEICH D F， LESKOVEC J. Higherorder organization of complex networks[J].Science， 2016，353（6295）：163-166.

[21]LI P Z， HUANG L， WANG C D， et al. Community detection using attribute homogenous motif[J]. IEEE Access， 2018， 6： 47707-47716.

[22]CHEN X， XIA C， WANG J. A novel trustbased community detection algorithm used in social networks[J]. Chaos， Solitons & Fractals， 2018， 108： 57-65.

[23]LESKOVEC J，KREVL A. Stanford large network dataset collection [DB/OL].[2019-03-02].https：//snap.standford.edu/data/index.html.

[24]SHEN H， CHENG X， CAI K， et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A： Statistical Mechanics and Its Applications， 2009， 388（8）： 1706-1712.

[25]BU Z， GAO G， WU Z， et al. Local community extraction for nonoverlapping and overlapping community detection[C]// Proceedings of the 10th International Conference on Advanced Data Mining and Applications. Berlin： Springer， 2014： 98-111.

This work is partially supported by the National Natural Science Foundation of China （61902227，61673295，61773247）， the Project of Shanxi Province Science Foundation for Youths （201701D221097）.

DU Hangyuan， born in 1985， Ph. D.， associate professor. His research interests include clustering analysis， complex network theory.

PEI Xiya， born in 1993， M. S. candidate. Her research interests include machine learning.

WANG Wenjian， born in 1968， Ph. D.， professor. Her research interests include computational intelligence， machine learning， machine vision.