面向屬性網絡的重疊社區發現算法

杜航原 裴希亞 王文劍

摘 要：針對現實世界的網絡節點中包含大量屬性信息并且社區之間呈現出重疊特性的問題，提出了一種面向屬性網絡的重疊社區發現算法。融合網絡的拓撲結構和節點屬性定義了節點的密集度和間隔度，分別用于描述社區內部連接緊密和外部連接松散的特點。基于密度峰值聚類的思想搜索局部密度中心作為社區中心，在此基礎上給出了非中心節點關于各個社區的隸屬度的迭代計算方法，實現了重疊社區的劃分。在真實數據集上進行了仿真實驗，實驗結果表明所提算法相對于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.