杜航原 裴希亞 王文劍

摘 要：針對現(xiàn)實(shí)世界的網(wǎng)絡(luò)節(jié)點(diǎn)中包含大量屬性信息并且社區(qū)之間呈現(xià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)于各個社區(qū)的隸屬度的迭代計算方法，實(shí)現(xiàn)了重疊社區(qū)的劃分。在真實(shí)數(shù)據(jù)集上進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明所提算法相對于LINK、COPRA和DPSCD能獲得更好的社區(qū)劃分結(jié)果。

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

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

早期的研究認(rèn)為每個節(jié)點(diǎn)只能屬于一個社區(qū)，即社區(qū)之間是相互獨(dú)立的。隨著研究的深入，人們發(fā)現(xiàn)現(xiàn)實(shí)世界中往往存在一些節(jié)點(diǎn)同時屬于多個社區(qū)的情況，即社區(qū)結(jié)構(gòu)表現(xiàn)出重疊特性[5]，例如：在學(xué)術(shù)合作網(wǎng)絡(luò)中，一個學(xué)者可能同時參與多個學(xué)術(shù)團(tuán)體;在蛋白質(zhì)互作用網(wǎng)絡(luò)中，一個蛋白質(zhì)可以根據(jù)功能的不同被劃分到不同的社區(qū)。在這些場景中，經(jīng)典的面向獨(dú)立社區(qū)的硬劃分社區(qū)發(fā)現(xiàn)算法不再適用。重疊社區(qū)發(fā)現(xiàn)問題逐漸引起人們的關(guān)注，目前，面向重疊社區(qū)的社區(qū)發(fā)現(xiàn)方法大體上可以分為以下5類：1）基于派系過濾的算法（Clique Percolation Method， CPM）[6]，該方法是最早開始研究重疊社區(qū)結(jié)構(gòu)的算法，由Palla等[7]提出，通過尋找網(wǎng)絡(luò)中各個由互相連通的k完全子圖組成的k派系社區(qū)來進(jìn)行重疊社區(qū)發(fā)現(xiàn)。隨后，F(xiàn)arkas等[8]把CPM算法擴(kuò)展到了加權(quán)網(wǎng)絡(luò)，提出了CPMw算法，規(guī)定只有內(nèi)部密度超過給定閾值的k派系才可以成為一個社區(qū)。2）基于局部擴(kuò)展的算法，此類方法一般通過一個局部適應(yīng)度函數(shù)來對所選取的種子節(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）基于模糊檢測的算法，不直接給出節(jié)點(diǎn)的社區(qū)劃分結(jié)果，而是用隸屬度表示節(jié)點(diǎn)屬于每個社區(qū)的概率，代表算法是模糊C均值（Fuzzy CMeans， FCM）算法[10]，該算法利用模糊C均值方法對網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行改進(jìn)分析，可以挖掘網(wǎng)絡(luò)中的k個重疊社區(qū)。4）基于鏈接密度的算法，將邊鏈接密度作為重點(diǎn)，代表算法為LINK算法[11]，該算法對網(wǎng)絡(luò)中的邊進(jìn)行層次聚類分析，以此完成重疊社區(qū)發(fā)現(xiàn)。5）由獨(dú)立社區(qū)發(fā)現(xiàn)擴(kuò)展而來的算法，將獨(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ò)展而來，COPRA算法在執(zhí)行時會使用隸屬度來幫助節(jié)點(diǎn)決定歸屬哪個社區(qū)，如果節(jié)點(diǎn)對于鄰居節(jié)點(diǎn)所在社區(qū)的隸屬度都低于閾值，那么節(jié)點(diǎn)就隨機(jī)選擇一個社區(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ò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)作為輸入來實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)聚類算法[15];類似地，AP（Affinity Propagation）算法把節(jié)點(diǎn)間的屬性相似度作為輸入，迭代執(zhí)行算法，直到出現(xiàn)一個高質(zhì)量的樣例集和相應(yīng)的簇[16]。還有一些學(xué)者利用拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)屬性信息進(jìn)行社區(qū)發(fā)現(xiàn)研究，如：文獻(xiàn)[17]先利用屬性信息計算出節(jié)點(diǎn)間的屬性相似度，再通過拓?fù)浣Y(jié)構(gòu)關(guān)系計算出結(jié)構(gòu)相似度，最后將二者的加權(quán)和作為節(jié)點(diǎn)之間的距離度量進(jìn)行社區(qū)的劃分;MISAGA（Mining Interesting Subgraphs in Attributed Graph Algorithm）[18]通過使用一種統(tǒng)計度量的方式來發(fā)現(xiàn)社區(qū)，該統(tǒng)計度量方法首先根據(jù)屬性信息標(biāo)識出具有一定關(guān)聯(lián)強(qiáng)度的屬性值，如果一對頂點(diǎn)的屬性值滿足一定關(guān)聯(lián)強(qiáng)度，再通過拓?fù)浣Y(jié)構(gòu)信息計算出一個稱為關(guān)聯(lián)度的度量，在此基礎(chǔ)上發(fā)現(xiàn)社區(qū)。這些算法在社區(qū)發(fā)現(xiàn)過程中，利用拓?fù)浣Y(jié)構(gòu)或?qū)傩孕畔哪骋环矫鎸?jié)點(diǎn)間的相似性關(guān)系進(jìn)行度量，忽略了兩類信息在網(wǎng)絡(luò)社區(qū)形成過程中的共同作用，導(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)屬性對這一本質(zhì)特征形成的共同作用機(jī)制，以及有效描述和度量，是網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中的關(guān)鍵問題。此外，在社區(qū)發(fā)現(xiàn)過程中對社區(qū)結(jié)構(gòu)呈現(xiàn)出的重疊特性進(jìn)行切實(shí)表達(dá)，也非常重要。針對上述問題，本文提出了一種面向?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è)計了網(wǎng)絡(luò)社區(qū)中心的快速搜索算法;

3） 給出了非中心節(jié)點(diǎn)關(guān)于各社區(qū)隸屬度的迭代計算方法，以實(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]基于一個假設(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)。因此，密度峰值聚類思想很適合用來反映社區(qū)結(jié)構(gòu)“內(nèi)部聯(lián)系緊密、外部聯(lián)系松散”的特性。

在密度峰值聚類算法中，對于每個節(jié)點(diǎn)i，計算它的局部密度ρi和它距離更高密度的節(jié)點(diǎn)的距離δi，這兩個值的計算都只依賴于數(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是一個截斷距離。節(jié)點(diǎn)i的密度ρi等于與該節(jié)點(diǎn)的距離小于截斷距離dc的節(jié)點(diǎn)個數(shù)。節(jié)點(diǎn)i到更高密度節(jié)點(diǎn)的距離δi是節(jié)點(diǎn)i與所有比它密度高的節(jié)點(diǎn)之間距離的最小值，定義如式（2）：

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

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

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

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

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

節(jié)點(diǎn)間的屬性同質(zhì)值表示兩個節(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個屬性與節(jié)點(diǎn)vj的第αj個屬性的聯(lián)系強(qiáng)度，表示兩個節(jié)點(diǎn)的屬性相似程度。若fd（i）=1且fd（j）=1，則S（αi，αj）=1。

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

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

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

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

其中：It表示第t個模體，{i， j}∈It表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj同時被包含在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)識，將網(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)間隔度，用來度量節(jié)點(diǎn)與更高密集度的節(jié)點(diǎn)間的距離。

若兩個節(jié)點(diǎn)相鄰，則對其直接相似度定義如式（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之間的屬性相似度，表示兩個節(jié)點(diǎn)的屬性相似程度;l（i）為節(jié)點(diǎn)vi與所有鄰居節(jié)點(diǎn)的屬性相似度總和;I（t）為節(jié)點(diǎn)vt的度。在此基礎(chǔ)上對不相鄰的兩個節(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之間的路徑長度。

基于以上兩個定義，可求得網(wǎng)絡(luò)中任意兩個節(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ǔ)上，對網(wǎng)絡(luò)中每條邊的邊適應(yīng)度定義如式（10），其值越大，表示兩個節(jié)點(diǎn)聯(lián)系越緊密。

Sij=SFjij+SFiij （10）

其中：Sij表示邊ei， j的邊適應(yīng)度，SFjij和SFiij分別表示邊ei， j相對于鄰居社區(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ū)的核心，對于這一特性的表現(xiàn)最為顯著，因此相比社區(qū)內(nèi)的一般節(jié)點(diǎn)應(yīng)具有較大的密集度和間隔度?；谶@一認(rèn)識，本文選擇密集度和間隔度乘積最大的K個節(jié)點(diǎn)作為網(wǎng)絡(luò)中各個社區(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）

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

3）

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

4）

if （i， j）∈Mmn

5）

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

6）

else

7）

aij=0;

8）

end if

9）

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

10）

if Bij=1

11）

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

12）

else

13）

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

14）

end if

15）

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

16）

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

17）

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

18）

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

19）

end for

20）

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

21）

return C={ck}Kk=1

程序后

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

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

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

pik=Sik∑u∈NiSiu（13）

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

通過上述方法計算得到所有非中心節(jié)點(diǎn)關(guān)于不同社區(qū)的隸屬度。接著，將非中心節(jié)點(diǎn)分配到隸屬度最大的社區(qū)，例如對于節(jié)點(diǎn)vi，如果k=argmaxu{piu，u=1，2，…，r}，那么就將節(jié)點(diǎn)vi分配到社區(qū)k。同時，若節(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個社區(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）

通過式（13）計算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個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)分析與比較。

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

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

3.1.2?評價準(zhǔn)則

由于模塊度函數(shù)Q只適用于非重疊社區(qū)的情形，因此本文選取擴(kuò)展模塊度（Extended modularity， EQ）[24]函數(shù)用來衡量重疊社區(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ū)個數(shù);Bij為網(wǎng)絡(luò)鄰接矩陣中的元素;ki、kj分別為節(jié)點(diǎn)vi、vj的度;gy為第y社區(qū)包含的節(jié)點(diǎn)集。

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

R=TPTP+FN

P=TPTP+FP

F=2·PRP+R（15）

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

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

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

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

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

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

4?結(jié)語

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

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

參考文獻(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]時京晶. 三種經(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é)報， 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ī)研究與發(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ī)研究與發(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ī)技術(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.