面向?qū)傩跃W(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)算法

杜航原 裴希亞 王文劍

摘 要：針對(duì)現(xiàn)實(shí)世界的網(wǎng)絡(luò)節(jié)點(diǎn)中包含大量屬性信息并且社區(qū)之間呈現(xiàn)出重疊特性的問(wèn)題，提出了一種面向?qū)傩跃W(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)算法。融合網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性定義了節(jié)點(diǎn)的密集度和間隔度，分別用于描述社區(qū)內(nèi)部連接緊密和外部連接松散的特點(diǎn)。基于密度峰值聚類的思想搜索局部密度中心作為社區(qū)中心，在此基礎(chǔ)上給出了非中心節(jié)點(diǎn)關(guān)于各個(gè)社區(qū)的隸屬度的迭代計(jì)算方法，實(shí)現(xiàn)了重疊社區(qū)的劃分。在真實(shí)數(shù)據(jù)集上進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明所提算法相對(duì)于LINK、COPRA和DPSCD能獲得更好的社區(qū)劃分結(jié)果。

關(guān)鍵詞：屬性網(wǎng)絡(luò);重疊社區(qū)發(fā)現(xiàn);密度峰值聚類;社區(qū)中心;節(jié)點(diǎn)隸屬度

中圖分類號(hào)： TP391

文獻(xiàn)標(biāo)志碼：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?引言

社區(qū)結(jié)構(gòu)作為一種數(shù)據(jù)組織形式廣泛存在于各種復(fù)雜網(wǎng)絡(luò)中[1]，如：引文網(wǎng)絡(luò)中針對(duì)同一主題的相關(guān)論文往往形成同一社區(qū)[2]。社區(qū)內(nèi)部的節(jié)點(diǎn)之間連接相對(duì)緊密，但是各社區(qū)之間的連接相對(duì)稀疏。社區(qū)結(jié)構(gòu)是現(xiàn)實(shí)世界實(shí)體關(guān)系的一種映射，對(duì)于理解網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和復(fù)雜系統(tǒng)的內(nèi)部規(guī)律有著重要的作用[3]， 如：萬(wàn)維網(wǎng)中的社區(qū)是討論相關(guān)主題的若干網(wǎng)站;電子電路網(wǎng)絡(luò)中的社區(qū)可能是具有某一類特定功能的單元， 發(fā)現(xiàn)這些網(wǎng)絡(luò)中的社區(qū)有助于研究人員有效地理解和開發(fā)這些網(wǎng)絡(luò)[2]。近年來(lái)一些學(xué)者圍繞這個(gè)問(wèn)題展開了深入研究，形成了大量的研究成果，其中具有代表性的方法包括以下幾類：基于模塊性優(yōu)化的社區(qū)挖掘方法、基于標(biāo)簽傳播的社區(qū)挖掘方法、基于劃分的社區(qū)挖掘方法和基于動(dòng)力學(xué)的社區(qū)挖掘方法[4]。

早期的研究認(rèn)為每個(gè)節(jié)點(diǎn)只能屬于一個(gè)社區(qū)，即社區(qū)之間是相互獨(dú)立的。隨著研究的深入，人們發(fā)現(xiàn)現(xiàn)實(shí)世界中往往存在一些節(jié)點(diǎn)同時(shí)屬于多個(gè)社區(qū)的情況，即社區(qū)結(jié)構(gòu)表現(xiàn)出重疊特性[5]，例如：在學(xué)術(shù)合作網(wǎng)絡(luò)中，一個(gè)學(xué)者可能同時(shí)參與多個(gè)學(xué)術(shù)團(tuán)體;在蛋白質(zhì)互作用網(wǎng)絡(luò)中，一個(gè)蛋白質(zhì)可以根據(jù)功能的不同被劃分到不同的社區(qū)。在這些場(chǎng)景中，經(jīng)典的面向獨(dú)立社區(qū)的硬劃分社區(qū)發(fā)現(xiàn)算法不再適用。重疊社區(qū)發(fā)現(xiàn)問(wèn)題逐漸引起人們的關(guān)注，目前，面向重疊社區(qū)的社區(qū)發(fā)現(xiàn)方法大體上可以分為以下5類：1）基于派系過(guò)濾的算法（Clique Percolation Method， CPM）[6]，該方法是最早開始研究重疊社區(qū)結(jié)構(gòu)的算法，由Palla等[7]提出，通過(guò)尋找網(wǎng)絡(luò)中各個(gè)由互相連通的k完全子圖組成的k派系社區(qū)來(lái)進(jìn)行重疊社區(qū)發(fā)現(xiàn)。隨后，F(xiàn)arkas等[8]把CPM算法擴(kuò)展到了加權(quán)網(wǎng)絡(luò)，提出了CPMw算法，規(guī)定只有內(nèi)部密度超過(guò)給定閾值的k派系才可以成為一個(gè)社區(qū)。2）基于局部擴(kuò)展的算法，此類方法一般通過(guò)一個(gè)局部適應(yīng)度函數(shù)來(lái)對(duì)所選取的種子節(jié)點(diǎn)進(jìn)行擴(kuò)展，代表算法是LFM（Local Fitness Method）[9]。在LFM中，適應(yīng)度函數(shù)的概念被提出，重疊社區(qū)發(fā)現(xiàn)的標(biāo)準(zhǔn)是適應(yīng)度函數(shù)最大化。由于LFM的種子節(jié)點(diǎn)是隨機(jī)選取的，導(dǎo)致算法穩(wěn)定性較差。3）基于模糊檢測(cè)的算法，不直接給出節(jié)點(diǎn)的社區(qū)劃分結(jié)果，而是用隸屬度表示節(jié)點(diǎn)屬于每個(gè)社區(qū)的概率，代表算法是模糊C均值（Fuzzy CMeans， FCM）算法[10]，該算法利用模糊C均值方法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行改進(jìn)分析，可以挖掘網(wǎng)絡(luò)中的k個(gè)重疊社區(qū)。4）基于鏈接密度的算法，將邊鏈接密度作為重點(diǎn)，代表算法為L(zhǎng)INK算法[11]，該算法對(duì)網(wǎng)絡(luò)中的邊進(jìn)行層次聚類分析，以此完成重疊社區(qū)發(fā)現(xiàn)。5）由獨(dú)立社區(qū)發(fā)現(xiàn)擴(kuò)展而來(lái)的算法，將獨(dú)立社區(qū)發(fā)現(xiàn)算法進(jìn)行改進(jìn)[12]，使其具有重疊社區(qū)發(fā)現(xiàn)的能力。如COPRA算法[13]就是由經(jīng)典的標(biāo)簽傳播算法（Label Propagation Algorithm， LPA）擴(kuò)展而來(lái)，COPRA算法在執(zhí)行時(shí)會(huì)使用隸屬度來(lái)幫助節(jié)點(diǎn)決定歸屬哪個(gè)社區(qū)，如果節(jié)點(diǎn)對(duì)于鄰居節(jié)點(diǎn)所在社區(qū)的隸屬度都低于閾值，那么節(jié)點(diǎn)就隨機(jī)選擇一個(gè)社區(qū)。

上述方法僅依賴拓?fù)潢P(guān)系進(jìn)行社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)，但社區(qū)的形成除了與節(jié)點(diǎn)間拓?fù)浣Y(jié)構(gòu)相關(guān)外，還受到另外一類重要信息的影響，即節(jié)點(diǎn)的屬性信息[14]。在現(xiàn)實(shí)世界中，這種影響表現(xiàn)為：在社交網(wǎng)絡(luò)中，有相似背景信息和個(gè)人愛好的用戶往往構(gòu)成同一社區(qū);在蛋白質(zhì)互作用網(wǎng)絡(luò)中，有相同功能的蛋白質(zhì)容易形成同一社區(qū)。為此，一些研究人員開始嘗試?yán)霉?jié)點(diǎn)屬性信息發(fā)掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，如：kSNAP（Summarization by Grouping Nodes on Attributes and Pairwise Relationships）是一種先根據(jù)節(jié)點(diǎn)屬性值是否相同把節(jié)點(diǎn)分成不同的簇結(jié)構(gòu)，然后把簇結(jié)構(gòu)作為輸入來(lái)實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)聚類算法[15];類似地，AP（Affinity Propagation）算法把節(jié)點(diǎn)間的屬性相似度作為輸入，迭代執(zhí)行算法，直到出現(xiàn)一個(gè)高質(zhì)量的樣例集和相應(yīng)的簇[16]。還有一些學(xué)者利用拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)屬性信息進(jìn)行社區(qū)發(fā)現(xiàn)研究，如：文獻(xiàn)[17]先利用屬性信息計(jì)算出節(jié)點(diǎn)間的屬性相似度，再通過(guò)拓?fù)浣Y(jié)構(gòu)關(guān)系計(jì)算出結(jié)構(gòu)相似度，最后將二者的加權(quán)和作為節(jié)點(diǎn)之間的距離度量進(jìn)行社區(qū)的劃分;MISAGA（Mining Interesting Subgraphs in Attributed Graph Algorithm）[18]通過(guò)使用一種統(tǒng)計(jì)度量的方式來(lái)發(fā)現(xiàn)社區(qū)，該統(tǒng)計(jì)度量方法首先根據(jù)屬性信息標(biāo)識(shí)出具有一定關(guān)聯(lián)強(qiáng)度的屬性值，如果一對(duì)頂點(diǎn)的屬性值滿足一定關(guān)聯(lián)強(qiáng)度，再通過(guò)拓?fù)浣Y(jié)構(gòu)信息計(jì)算出一個(gè)稱為關(guān)聯(lián)度的度量，在此基礎(chǔ)上發(fā)現(xiàn)社區(qū)。這些算法在社區(qū)發(fā)現(xiàn)過(guò)程中，利用拓?fù)浣Y(jié)構(gòu)或?qū)傩孕畔哪骋环矫鎸?duì)節(jié)點(diǎn)間的相似性關(guān)系進(jìn)行度量，忽略了兩類信息在網(wǎng)絡(luò)社區(qū)形成過(guò)程中的共同作用，導(dǎo)致社區(qū)發(fā)現(xiàn)結(jié)果可靠性不高。

網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)具有“內(nèi)部聯(lián)系緊密、外部聯(lián)系松散”的本質(zhì)特征， 探求拓?fù)潢P(guān)系和節(jié)點(diǎn)屬性對(duì)這一本質(zhì)特征形成的共同作用機(jī)制，以及有效描述和度量，是網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中的關(guān)鍵問(wèn)題。此外，在社區(qū)發(fā)現(xiàn)過(guò)程中對(duì)社區(qū)結(jié)構(gòu)呈現(xiàn)出的重疊特性進(jìn)行切實(shí)表達(dá)，也非常重要。針對(duì)上述問(wèn)題，本文提出了一種面向?qū)傩跃W(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法，主要工作如下：

1） 融合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)屬性信息，提出網(wǎng)絡(luò)社區(qū)本質(zhì)特征的描述和度量方法;

2） 基于密度峰值聚類思想設(shè)計(jì)了網(wǎng)絡(luò)社區(qū)中心的快速搜索算法;

3） 給出了非中心節(jié)點(diǎn)關(guān)于各社區(qū)隸屬度的迭代計(jì)算方法，以實(shí)現(xiàn)重疊社區(qū)劃分;

4） 在真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，本文提出的社區(qū)發(fā)現(xiàn)算法能有效發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)。

1?密度峰值聚類

密度峰值聚類[19]基于一個(gè)假設(shè)：簇中心被一些具有較低局部密度的節(jié)點(diǎn)包圍，并且與具有更高局部密度的節(jié)點(diǎn)距離較遠(yuǎn)。如果將網(wǎng)絡(luò)社區(qū)視為復(fù)雜網(wǎng)絡(luò)中的簇結(jié)構(gòu)，那么社區(qū)中心的特性將與這一假設(shè)保持一致，即社區(qū)中心作為密度中心被一些具有較低局部密度的節(jié)點(diǎn)包圍，且與具有更高局部密度的節(jié)點(diǎn)（其他社區(qū)中心）距離較遠(yuǎn)。因此，密度峰值聚類思想很適合用來(lái)反映社區(qū)結(jié)構(gòu)“內(nèi)部聯(lián)系緊密、外部聯(lián)系松散”的特性。

在密度峰值聚類算法中，對(duì)于每個(gè)節(jié)點(diǎn)i，計(jì)算它的局部密度ρi和它距離更高密度的節(jié)點(diǎn)的距離δi，這兩個(gè)值的計(jì)算都只依賴于數(shù)據(jù)節(jié)點(diǎn)之間的距離dij。節(jié)點(diǎn)i的局部密度ρi定義如式（1）：

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

式中： 如果x<0，則X（x）=1;否則X（x）=0，dc是一個(gè)截?cái)嗑嚯x。節(jié)點(diǎn)i的密度ρi等于與該節(jié)點(diǎn)的距離小于截?cái)嗑嚯xdc的節(jié)點(diǎn)個(gè)數(shù)。節(jié)點(diǎn)i到更高密度節(jié)點(diǎn)的距離δi是節(jié)點(diǎn)i與所有比它密度高的節(jié)點(diǎn)之間距離的最小值，定義如式（2）：

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

對(duì)于有最高密度的節(jié)點(diǎn)，定義為δi=maxj（dij），因此，將δi值異常大的節(jié)點(diǎn)作為簇中心。在確定簇中心之后，將剩余的節(jié)點(diǎn)分配到比其密度高并且距離它最近的簇中心所在的簇。

2?一種面向?qū)傩跃W(wǎng)路的重疊社區(qū)發(fā)現(xiàn)算法

密度峰值聚類基于幾何空間中的歐氏距離定義了節(jié)點(diǎn)的局部密度和到更高密度節(jié)點(diǎn)間的距離，很適合用來(lái)描述社區(qū)結(jié)構(gòu)的特性。網(wǎng)絡(luò)數(shù)據(jù)由兩類信息構(gòu)成：一種是拓?fù)淇臻g中的拓?fù)浣Y(jié)構(gòu); 另一種是特征空間中的節(jié)點(diǎn)屬性，這使得無(wú)法直接基于幾何空間為網(wǎng)絡(luò)數(shù)據(jù)定義密度和距離，必須探求新的適合于表達(dá)網(wǎng)絡(luò)數(shù)據(jù)本質(zhì)特征的度量手段。為此，本文提出了密集度和間隔度分別用來(lái)反映社區(qū)內(nèi)部聯(lián)系緊密、外部聯(lián)系松散的特性。

2.1?節(jié)點(diǎn)密集度

對(duì)于給定的屬性網(wǎng)絡(luò)G=〈V，E，F(xiàn)〉，其中V={v1，v2，…，vn}表示由網(wǎng)絡(luò)中的n個(gè)節(jié)點(diǎn)組成的集合，E={e1，e2，…，em}表示由網(wǎng)絡(luò)中的m條邊組成的集合，F(xiàn)={f1， f2，…， fd}表示由節(jié)點(diǎn)的d個(gè)屬性向量組成的集合。

網(wǎng)絡(luò)社區(qū)是由拓?fù)浣Y(jié)構(gòu)和屬性信息共同作用形成的，本文算法在社區(qū)發(fā)現(xiàn)過(guò)程中為了充分利用兩者的融合信息，通過(guò)計(jì)算滿足一定拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)子圖（模體[20]）的屬性同質(zhì)值，進(jìn)而求得該子圖中任意兩個(gè)節(jié)點(diǎn)間的屬性結(jié)構(gòu)連接強(qiáng)度[21]，屬性結(jié)構(gòu)連接強(qiáng)度越大，兩個(gè)節(jié)點(diǎn)的屬性同質(zhì)強(qiáng)度越大且結(jié)構(gòu)聯(lián)系越緊密（如圖1所示，用Mmn表示由n個(gè)節(jié)點(diǎn)、m條邊組成的網(wǎng)絡(luò)子圖（模體））。

節(jié)點(diǎn)間的屬性同質(zhì)值表示兩個(gè)節(jié)點(diǎn)的屬性同質(zhì)強(qiáng)度，其值越大，節(jié)點(diǎn)間的屬性同質(zhì)強(qiáng)度越大。節(jié)點(diǎn)vi和節(jié)點(diǎn)vj間的屬性同質(zhì)值HG（i， j）定義如式（3）：

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

其中：fi和fj分別表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的屬性向量，αi和αj分別表示屬性向量fi和fj中非零元素的下標(biāo)。S（αi，αj）為節(jié)點(diǎn)vi的第αi個(gè)屬性與節(jié)點(diǎn)vj的第αj個(gè)屬性的聯(lián)系強(qiáng)度，表示兩個(gè)節(jié)點(diǎn)的屬性相似程度。若fd（i）=1且fd（j）=1，則S（αi，αj）=1。

在得到兩個(gè)節(jié)點(diǎn)間屬性同質(zhì)值的基礎(chǔ)上，進(jìn)一步對(duì)模體的屬性同質(zhì)值定義如式（4）：

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

其中：Ht表示第t個(gè)模體的屬性同質(zhì)值，m表示第t個(gè)模體中邊的總數(shù)，uw和vw表示模體中第w條邊的兩個(gè)端點(diǎn)。在此基礎(chǔ)上，對(duì)于包含在模體中的任意兩個(gè)節(jié)點(diǎn)之間的屬性結(jié)構(gòu)連接強(qiáng)度定義如式（5）：

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

其中：It表示第t個(gè)模體，{i， j}∈It表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj同時(shí)被包含在It中。

社區(qū)結(jié)構(gòu)具有內(nèi)部聯(lián)系緊密的特點(diǎn)，因此社區(qū)內(nèi)的節(jié)點(diǎn)之間不僅有較高的屬性同質(zhì)強(qiáng)度，還存在較為密切的拓?fù)溥B接關(guān)系?；谝陨险J(rèn)識(shí)，將網(wǎng)絡(luò)節(jié)點(diǎn)的密集度定義如式（6）：

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

其中：Mi為節(jié)點(diǎn)vi的密集度，n為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量。節(jié)點(diǎn)vi的密集度定義為該節(jié)點(diǎn)與社區(qū)內(nèi)其他節(jié)點(diǎn)間的屬性結(jié)構(gòu)連接強(qiáng)度之和，其值越大，表示該節(jié)點(diǎn)與社區(qū)內(nèi)其他節(jié)點(diǎn)的屬性同質(zhì)程度越大，結(jié)構(gòu)聯(lián)系越緊密。

2.2?節(jié)點(diǎn)間隔度

社區(qū)結(jié)構(gòu)外部聯(lián)系松散，即不同社區(qū)之間的屬性同質(zhì)強(qiáng)度降低，拓?fù)溥B接關(guān)系也較為松散。為了反映這種特性，首先將節(jié)點(diǎn)的屬性信息和結(jié)構(gòu)信息進(jìn)行融合求得每條邊的邊適應(yīng)度[22]，在此基礎(chǔ)上定義節(jié)點(diǎn)間隔度，用來(lái)度量節(jié)點(diǎn)與更高密集度的節(jié)點(diǎn)間的距離。

若兩個(gè)節(jié)點(diǎn)相鄰，則對(duì)其直接相似度定義如式（7）：

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

其中：d_t（i， j）為節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的直接相似度;l（i， j）為節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間的屬性相似度，表示兩個(gè)節(jié)點(diǎn)的屬性相似程度;l（i）為節(jié)點(diǎn)vi與所有鄰居節(jié)點(diǎn)的屬性相似度總和;I（t）為節(jié)點(diǎn)vt的度。在此基礎(chǔ)上對(duì)不相鄰的兩個(gè)節(jié)點(diǎn)間的間接相似度定義如式（8）：

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

其中：i_t（i， j）為節(jié)點(diǎn)vi與節(jié)點(diǎn)vj間的間接相似度，m=min（d_t（i，i1），d_t（i1，i2），…，d_t（in， j）），dmax為設(shè)定的閾值，di， j為節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的路徑長(zhǎng)度。

基于以上兩個(gè)定義，可求得網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)vi和vj間的相似度t（i， j），定義如式（9）：

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

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

在求得節(jié)點(diǎn)間相似度的基礎(chǔ)上，對(duì)網(wǎng)絡(luò)中每條邊的邊適應(yīng)度定義如式（10），其值越大，表示兩個(gè)節(jié)點(diǎn)聯(lián)系越緊密。

Sij=SFjij+SFiij （10）

其中：Sij表示邊ei， j的邊適應(yīng)度，SFjij和SFiij分別表示邊ei， j相對(duì)于鄰居社區(qū)Fi和Fj的邊適應(yīng)度，F(xiàn)i=N（i）+{i}-{j}和Fj=N（j）+{j}-{i}表示邊ei， j的鄰居社區(qū)，N（i）和N（j）分別表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的鄰居節(jié)點(diǎn)。以圖2為例，N（1）={2，4，5}，N（5）={1，6，7}，邊e1，5的鄰居社區(qū)為F1={1，2，4}，F(xiàn)5={5，6，7}。

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

其中：t（p，q）表示節(jié)點(diǎn)vp和節(jié)點(diǎn)vq之間的相似度，a=∑p，q∈Fj，p>qt（p，q）表示社區(qū)Fj內(nèi)節(jié)點(diǎn)間相似度總和，b=∑p∈Fi，q∈Fjt（p，q）表示社區(qū)Fj內(nèi)節(jié)點(diǎn)與其鄰居社區(qū)Fi內(nèi)節(jié)點(diǎn)間相似度總和，c=∑p∈Fjt（i，p）示節(jié)點(diǎn)vi與鄰居社區(qū)Fj內(nèi)節(jié)點(diǎn)間相似度總和，d=∑q∈（Fi-{i}）t（i，q）表示節(jié)點(diǎn)vi與社區(qū)Fi內(nèi)節(jié)點(diǎn)間相似度總和。

為了刻畫不同社區(qū)之間聯(lián)系松散的特性，將節(jié)點(diǎn)的間隔度定義為節(jié)點(diǎn)vi與所有比它密集度大的節(jié)點(diǎn)之間邊適應(yīng)度的最大值的倒數(shù)，其值越大表明節(jié)點(diǎn)vi與有更高密集度的節(jié)點(diǎn)之間聯(lián)系越松散。間隔度定義如式（12）：

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

其中：Di為節(jié)點(diǎn)vi的間隔度，節(jié)點(diǎn)vj是比節(jié)點(diǎn)vi的密集度大的點(diǎn)，Mi和Mj分別表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的密集度。

2.3?搜索社區(qū)中心

社區(qū)內(nèi)的節(jié)點(diǎn)間具有較強(qiáng)的屬性同質(zhì)強(qiáng)度和較為密切的結(jié)構(gòu)聯(lián)系，社區(qū)間的節(jié)點(diǎn)具有較弱的屬性同質(zhì)強(qiáng)度和較為松散的結(jié)構(gòu)聯(lián)系，本文利用密集度和間隔度描述社區(qū)的這一結(jié)構(gòu)特性。中心節(jié)點(diǎn)作為社區(qū)的核心，對(duì)于這一特性的表現(xiàn)最為顯著，因此相比社區(qū)內(nèi)的一般節(jié)點(diǎn)應(yīng)具有較大的密集度和間隔度?；谶@一認(rèn)識(shí)，本文選擇密集度和間隔度乘積最大的K個(gè)節(jié)點(diǎn)作為網(wǎng)絡(luò)中各個(gè)社區(qū)的中心。

算法1?社區(qū)中心選擇算法。

輸入?網(wǎng)絡(luò)G=〈V，E，F(xiàn)〉，鄰接矩陣Bn×n，節(jié)點(diǎn)屬性值;

輸出?社區(qū)中心節(jié)點(diǎn)集合C={ck}Kk=1。

程序前

1）

for each node vi∈V

2）

通過(guò)式（3）計(jì)算模體中每條邊的兩個(gè)端點(diǎn)間的屬性同質(zhì)值HG（i， j）;

3）

通過(guò)式（4）計(jì)算模體的屬性同質(zhì)值Ht;

4）

if （i， j）∈Mmn

5）

通過(guò)式（5）計(jì)算節(jié)點(diǎn)vi與vj間的屬性結(jié)構(gòu)連接強(qiáng)度aij;

6）

else

7）

aij=0;

8）

end if

9）

通過(guò)式（6）計(jì)算節(jié)點(diǎn)vi的密集度Mi;

10）

if Bij=1

11）

通過(guò)式（7）計(jì)算節(jié)點(diǎn)間的直接相似度d_t（i， j）;

12）

else

13）

通過(guò)式（8）計(jì)算節(jié)點(diǎn)間的間接相似度i_t（i， j）;

14）

end if

15）

通過(guò)式（9）計(jì)算節(jié)點(diǎn)間的相似度t（i， j）;

16）

通過(guò)式（11）計(jì)算邊ei， j相對(duì)于鄰居社區(qū)Fi的邊適應(yīng)度SFjij;

17）

通過(guò)式（10）計(jì)算邊ei， j的邊適應(yīng)度Sij;

18）

通過(guò)式（12）計(jì)算節(jié)點(diǎn)的間隔度Di;

19）

end for

20）

將節(jié)點(diǎn)的密集度Mi與間隔度Di的乘積計(jì)作γ，選取γ>α（α為給定閾值）的節(jié)點(diǎn)作為社區(qū)中心ck;

21）

return C={ck}Kk=1

程序后

2.4?節(jié)點(diǎn)的社區(qū)劃分

在具有重疊特性的網(wǎng)絡(luò)中，某些節(jié)點(diǎn)可能同時(shí)歸屬于多個(gè)社區(qū)，本文使用隸屬度表達(dá)節(jié)點(diǎn)歸屬于不同社區(qū)的概率。假設(shè)網(wǎng)絡(luò)中有r個(gè)社區(qū)，則節(jié)點(diǎn)vi關(guān)于不同社區(qū)的隸屬度向量為pi={pi1，pi2，…，pir}，pik表示節(jié)點(diǎn)vi關(guān)于第k個(gè)社區(qū)的隸屬度。 假定一個(gè)社區(qū)中心只能屬于一個(gè)社區(qū)，設(shè)第k個(gè)社區(qū)中心的節(jié)點(diǎn)編號(hào)為ck，則pcju=1（u=j），pcju=0（u≠j）。

對(duì)于非中心節(jié)點(diǎn)，其關(guān)于不同社區(qū)的隸屬度受到所有密集度比它大的社區(qū)中心的影響，即若非中心節(jié)點(diǎn)vi的密集度大于社區(qū)中心vk的密集度，則節(jié)點(diǎn)vi關(guān)于社區(qū)k的隸屬度pik=0。為便于計(jì)算，將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)按照密集度大小降序排列，從非中心節(jié)點(diǎn)中密集度最大的節(jié)點(diǎn)開始計(jì)算。節(jié)點(diǎn)vi關(guān)于社區(qū)k的隸屬度pik定義如式（13）：

pik=Sik∑u∈NiSiu（13）

其中：Sik為邊ei，k的邊適應(yīng)度，其值越大表示兩個(gè)節(jié)點(diǎn)聯(lián)系越緊密; Ni表示比節(jié)點(diǎn)vi的密集度大的社區(qū)中心節(jié)點(diǎn)的集合。

通過(guò)上述方法計(jì)算得到所有非中心節(jié)點(diǎn)關(guān)于不同社區(qū)的隸屬度。接著，將非中心節(jié)點(diǎn)分配到隸屬度最大的社區(qū)，例如對(duì)于節(jié)點(diǎn)vi，如果k=argmaxu{piu，u=1，2，…，r}，那么就將節(jié)點(diǎn)vi分配到社區(qū)k。同時(shí)，若節(jié)點(diǎn)vi關(guān)于社區(qū)k的隸屬度與關(guān)于社區(qū)r的隸屬度滿足pir/pik>θ（0<θ<1），θ為閾值，則認(rèn)為節(jié)點(diǎn)vi是社區(qū)k和r的重疊節(jié)點(diǎn)。

算法2?節(jié)點(diǎn)社區(qū)分配算法。

輸入?社區(qū)中心節(jié)點(diǎn)集合C，網(wǎng)絡(luò)中所有節(jié)點(diǎn)集合V，節(jié)點(diǎn)密集度M，節(jié)點(diǎn)間隔度D，閾值θ;

輸出?節(jié)點(diǎn)的社區(qū)分配結(jié)果集合。

程序前

1）

for each community center ci∈C

2）

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

3）

if ci為第k個(gè)社區(qū)的中心;

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）

通過(guò)式（13）計(jì)算pik;

14）

else

15）

pik=0;

16）

end if

17）

end for

18）

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

19）

將節(jié)點(diǎn)vi分配到社區(qū)k;

20）

end if

21）

if pir/pik>θ

22）

將節(jié)點(diǎn)vi作為社區(qū)k和r的重疊節(jié)點(diǎn);

23）

end if

24）

end for

程序后

3?實(shí)驗(yàn)結(jié)果及分析

3.1?實(shí)驗(yàn)設(shè)置

為了驗(yàn)證算法的有效性，選取LINK[11]算法、COPRA[13]算法和DPSCD（Density Peaksbased Clustering Method）[17]與本文方法在4個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)分析與比較。

3.1.1?數(shù)據(jù)集

為了測(cè)試算法的性能，本文實(shí)驗(yàn)選用斯坦福大學(xué)大型網(wǎng)絡(luò)數(shù)據(jù)集中的3個(gè)真實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)[23]作為測(cè)試集，分別為facebook、twitter和gplus，以及一個(gè)在Flickr上抓取的數(shù)據(jù)集。數(shù)據(jù)集中的節(jié)點(diǎn)編號(hào)表示一個(gè)用戶，節(jié)點(diǎn)之間的連邊表示兩個(gè)用戶有聯(lián)系，屬性信息包括用戶的性別、興趣、所在地區(qū)等信息，每個(gè)節(jié)點(diǎn)的屬性信息均用1或0標(biāo)識(shí)。這4個(gè)數(shù)據(jù)集的詳細(xì)信息見表1。觀察表1的最后一列數(shù)值可知， flickr網(wǎng)絡(luò)相對(duì)于其他三個(gè)網(wǎng)絡(luò)比較稠密。

3.1.2?評(píng)價(jià)準(zhǔn)則

由于模塊度函數(shù)Q只適用于非重疊社區(qū)的情形，因此本文選取擴(kuò)展模塊度（Extended modularity， EQ）[24]函數(shù)用來(lái)衡量重疊社區(qū)結(jié)構(gòu)劃分的質(zhì)量，其值越大表明社區(qū)劃分效果越好，擴(kuò)展模塊度EQ函數(shù)定義如式（14）：

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

其中：m為網(wǎng)絡(luò)中的連邊總數(shù);Qi、Qj為節(jié)點(diǎn)vi、vj所屬的社區(qū)個(gè)數(shù);Bij為網(wǎng)絡(luò)鄰接矩陣中的元素;ki、kj分別為節(jié)點(diǎn)vi、vj的度;gy為第y社區(qū)包含的節(jié)點(diǎn)集。

另外，本文還采用精確率（Precision，P）、召回率（Recall，R）和F1measure將召回率和精確率相結(jié)合，作為綜合評(píng)價(jià)指標(biāo)F來(lái)衡量算法的性能。具體計(jì)算公式定義如式（15）：

R=TPTP+FN

P=TPTP+FP

F=2·PRP+R（15）

由文獻(xiàn)[25]的定義，Cr（θ）={vi|pi，r≥θ}，其中Cr表示第r個(gè)重疊社區(qū)，θ為隸屬關(guān)系閾值（0<θ≤1），pi，r表示節(jié)點(diǎn)i關(guān)于社區(qū)r的隸屬度，來(lái)控制重疊社區(qū)的規(guī)模。通過(guò)計(jì)算重疊社區(qū)中的每個(gè)節(jié)點(diǎn)來(lái)獲取本文算法的平均準(zhǔn)確率、平均召回率和平均F1值，具體計(jì)算公式定義如式（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?實(shí)驗(yàn)結(jié)果及分析

表2～4中各算法的參數(shù)設(shè)置如下：對(duì)于LINK算法，設(shè)置參數(shù)c表示其將鏈接社區(qū)轉(zhuǎn)化為節(jié)點(diǎn)社區(qū)時(shí)的最小邊數(shù)量，令c的取值范圍為4～15;對(duì)于COPRA算法，設(shè)置參數(shù)v表示一個(gè)節(jié)點(diǎn)可以歸屬于不同社區(qū)的個(gè)數(shù)，令v的取值范圍為1～10;對(duì)于DPSCD，設(shè)置參數(shù)α表示在社區(qū)劃分過(guò)程中屬性信息所占的權(quán)重，令α的取值范圍為0.2～0.8;對(duì)于本文算法，閾值θ為節(jié)點(diǎn)關(guān)于某個(gè)社區(qū)的隸屬度，設(shè)置為[0.1，1]。

在4個(gè)數(shù)據(jù)集上分別選擇具有不同社區(qū)個(gè)數(shù)K的子網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如表2～4所示。其中，每個(gè)算法分別選取在不同參數(shù)下的最大擴(kuò)展模塊度EQ值作為最終的結(jié)果，表中加粗的數(shù)字分別表示各個(gè)網(wǎng)絡(luò)上EQ的最大值。由于本文算法融合了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性信息，充分考慮到了在社區(qū)結(jié)構(gòu)形成過(guò)程中兩者的共同作用關(guān)系，在真實(shí)網(wǎng)絡(luò)上性能表現(xiàn)良好，實(shí)驗(yàn)結(jié)果整體優(yōu)于只考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的LINK算法、COPRA算法以及獨(dú)立運(yùn)用拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性兩類信息進(jìn)行社區(qū)劃分的DPSCD。使用LINK算法獲得的EQ是所有結(jié)果中最差的，這是由于LINK算法構(gòu)造的一些小的鏈接社區(qū)影響了節(jié)點(diǎn)社區(qū)的形成。COPRA算法只是在少數(shù)情況下有較高的EQ值，這是由于該算法只依賴拓?fù)浣Y(jié)構(gòu)信息進(jìn)行社區(qū)發(fā)現(xiàn)，并且在執(zhí)行過(guò)程中存在較大隨機(jī)性，難以獲得較高的穩(wěn)定性。而DPSCD的EQ值在大部分情況下比LINK和COPRA算法的EQ值高，這是由于DPSCD將節(jié)點(diǎn)屬性信息運(yùn)用于社區(qū)發(fā)現(xiàn)過(guò)程，同時(shí)該算法利用拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性分別在拓?fù)淇臻g和特征空間中對(duì)節(jié)點(diǎn)相似性進(jìn)行度量，忽略了二者對(duì)社區(qū)形成的共同作用，因此獲得的EQ值比本文算法的EQ值低。另外，本文算法相較于其他三種算法，在同一種數(shù)據(jù)集的不同社區(qū)個(gè)數(shù)上計(jì)算得到的EQ值整體變化相對(duì)平穩(wěn)，即網(wǎng)絡(luò)中包含的社區(qū)數(shù)目較多時(shí)，算法性能對(duì)于社區(qū)數(shù)目不敏感，有較強(qiáng)的魯棒性;在社區(qū)個(gè)數(shù)相同的情況下，該算法在flickr數(shù)據(jù)集上計(jì)算得到的EQ值明顯優(yōu)于在其他3個(gè)數(shù)據(jù)集上計(jì)算得到的值，表明本文的算法更適合于稠密網(wǎng)絡(luò)。

表2～4中的提升率是指在同一個(gè)數(shù)據(jù)集上本文算法的EQ值相較于其他三種算法中最大的EQ值的提升程度。在以下三個(gè)表中計(jì)算的12次提升率中，有9次提升率的值大于0，并且在社區(qū)個(gè)數(shù)K為20和30時(shí)，本文算法在flickr數(shù)據(jù)集上的提升率均大于在其他3個(gè)數(shù)據(jù)集上的提升率，表明本文算法在稠密網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)效果較好。

四種算法獲得的召回率、精確率以及綜合指標(biāo)如圖3～6所示。為了避免實(shí)驗(yàn)的隨機(jī)性對(duì)結(jié)果產(chǎn)生影響，實(shí)驗(yàn)結(jié)果均為多次實(shí)驗(yàn)取平均值。本文算法能夠融合拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性兩類信息對(duì)社區(qū)結(jié)構(gòu)的本質(zhì)特征作出有效表達(dá)，因此在四個(gè)數(shù)據(jù)集上計(jì)算得到的平均精確率、平均召回率和平均F1measure值優(yōu)于其他三種方法，而且結(jié)果比較穩(wěn)定。如在flickr數(shù)據(jù)集上，本文算法的平均F1measure值在0.60左右波動(dòng)，且波動(dòng)范圍不大，DPSCD的平均F1measure值在0.55左右波動(dòng)，另外兩種算法的平均F1measure值大部分都在 0.5以下。除此之外，還可以觀察到DPSCD和本文算法在4種數(shù)據(jù)集上獲得的平均精確率和平均召回率變化也比較平穩(wěn)，而LINK算法的結(jié)果波動(dòng)較大，這是由于LINK算法將所有的邊都劃分到特定的鏈接社區(qū)中，容易形成網(wǎng)絡(luò)社區(qū)“過(guò)度重疊”的現(xiàn)象，導(dǎo)致社區(qū)發(fā)現(xiàn)效果不佳。

本文算法在不同閾值θ下獲得的平均精確率、平均召回率和綜合指標(biāo)的值如表5所示，表中加粗的數(shù)字表示在同一個(gè)數(shù)據(jù)集上，不同閾值下綜合指標(biāo)F所取得的最大值。若在不同閾值下取得的綜合指標(biāo)值相同，則將在較小閾值下取得的值加粗。從表中可以看出，在facebook數(shù)據(jù)集和flickr數(shù)據(jù)集上，當(dāng)閾值θ取0.8時(shí)，綜合指標(biāo)F獲得最大值;在twitter數(shù)據(jù)集和gplus數(shù)據(jù)集上，當(dāng)閾值 θ取0.9時(shí)，綜合指標(biāo)F獲得最大值。因此本文算法在閾值θ取0.8或0.9時(shí)，性能最優(yōu)。

4?結(jié)語(yǔ)

針對(duì)屬性網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)問(wèn)題，本文提出了一種有效的社區(qū)發(fā)現(xiàn)算法，建立對(duì)社區(qū)結(jié)構(gòu)內(nèi)部聯(lián)系緊密、外部聯(lián)系松散這一本質(zhì)特性的有效表達(dá)，基于密度峰值聚類思想進(jìn)行社區(qū)中心快速搜索，通過(guò)隸屬度迭代計(jì)算實(shí)現(xiàn)重疊節(jié)點(diǎn)的發(fā)現(xiàn)和重疊社區(qū)的劃分。在真實(shí)網(wǎng)絡(luò)上與現(xiàn)有社區(qū)發(fā)現(xiàn)方法進(jìn)行大量對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的有效性。

算法在計(jì)算節(jié)點(diǎn)間隔度的過(guò)程中，遍歷不相鄰節(jié)點(diǎn)之間的全部路徑具有較高的計(jì)算復(fù)雜度，因此在未來(lái)工作中，將嘗試使用并行計(jì)算技術(shù)拓展算法處理大規(guī)模網(wǎng)絡(luò)計(jì)算的能力。 另外，還將圍繞社區(qū)數(shù)量的自動(dòng)確定開展研究，使算法能夠應(yīng)用于社區(qū)數(shù)量未知的場(chǎng)景中。

參考文獻(xiàn) （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]時(shí)京晶. 三種經(jīng)典復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究[J]. 電腦與信息技術(shù)， 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]趙建軍，汪清，由磊，等. 基于信息傳遞和峰值聚類的自適應(yīng)社區(qū)發(fā)現(xiàn)算法[J]. 重慶大學(xué)學(xué)報(bào)， 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]劉大有，金弟，何東曉， 等.復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘綜述[J]. 計(jì)算機(jī)研究與發(fā)展， 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]朱牧，孟凡榮，周勇. 基于鏈接密度聚類的重疊社區(qū)發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)研究與發(fā)展， 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]張振宇，朱培棟，王可，等.拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)屬性綜合分析的社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，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.