王冰玉，吳振宇，沈蘇彬

(1.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210000；2.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210000)

1 概 述

在社交網(wǎng)絡(luò)中，存在一些聯(lián)系較為緊密的人群，這些人之間的互動(dòng)和聯(lián)系緊密和頻繁，常常會(huì)把這類人群聚類用來(lái)分析[1]，在社交網(wǎng)絡(luò)研究領(lǐng)域中一般將這些人群所構(gòu)成的團(tuán)體稱為社區(qū)[2]。發(fā)現(xiàn)社交網(wǎng)絡(luò)中的社區(qū)是十分有意義的，可以從中挖掘出許多隱含信息[3-4]。目前針對(duì)社交網(wǎng)絡(luò)的社區(qū)檢測(cè)算法進(jìn)行了研究，如崔泓等[5]針對(duì)社交網(wǎng)絡(luò)提出一種基于模塊化的社區(qū)檢測(cè)算法。社區(qū)的特點(diǎn)顯而易見，即社區(qū)內(nèi)部的聯(lián)系緊湊，而社區(qū)之間的聯(lián)系較為疏松。社區(qū)內(nèi)部的人之間往往存在著一些共性，例如，在Facebook、Twitter、Weibo這樣的社交網(wǎng)絡(luò)中，聯(lián)系緊密的人群往往在討論一件他們都感興趣的事件。再如在DBLP(digital bibliography & library project，計(jì)算機(jī)界反映共同作者關(guān)系的公共數(shù)據(jù)集)這樣的數(shù)據(jù)網(wǎng)絡(luò)中，聯(lián)系緊密的學(xué)者往往是研究相關(guān)或者類似的領(lǐng)域。在眾多的社區(qū)挖掘算法中，K-clique(K團(tuán))[6]是一種較為經(jīng)典的社區(qū)檢測(cè)算法，優(yōu)點(diǎn)在于其允許重疊社區(qū)的存在，且其參數(shù)k可以直觀地表示社區(qū)檢測(cè)的密度要求。

現(xiàn)實(shí)中的社交網(wǎng)絡(luò)規(guī)模都是較大的，對(duì)DBLP數(shù)據(jù)集中1990年-2016年中包含的會(huì)議論文的共同作者關(guān)系所形成的網(wǎng)絡(luò)運(yùn)行了K-Clique算法，算法的執(zhí)行效率如圖1所示。

圖1 社區(qū)檢測(cè)隨網(wǎng)絡(luò)規(guī)模變化的時(shí)間消耗

由圖1可見，隨著社交網(wǎng)絡(luò)規(guī)模的不斷增大，K-Clique算法的運(yùn)行時(shí)間會(huì)急劇上升。對(duì)此，文中提出一種增量式社區(qū)檢測(cè)算法。該算法在時(shí)間片更新時(shí)使用新時(shí)間片上出現(xiàn)的節(jié)點(diǎn)和邊去更新已有的社區(qū)檢測(cè)結(jié)果，而非在整個(gè)網(wǎng)絡(luò)上重新進(jìn)行社區(qū)檢測(cè)。這里的增量式是批量遞增，而非每新出現(xiàn)一條邊或一個(gè)節(jié)點(diǎn)時(shí)就對(duì)已有社區(qū)進(jìn)行更新[7]。也有使用滑動(dòng)窗口[8]的方式對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)檢測(cè)，但是這種方式每次只能輸出網(wǎng)絡(luò)中的若干個(gè)時(shí)間切片所包含的社區(qū)，而不能針對(duì)整個(gè)網(wǎng)絡(luò)輸出其社區(qū)結(jié)構(gòu)。與傳統(tǒng)K-Clique進(jìn)行了對(duì)比，以驗(yàn)證該算法的有效性。

2 相關(guān)研究

2.1 社區(qū)檢測(cè)算法研究

社區(qū)檢測(cè)算法有多種類型，其中比較有代表性的是基于劃分的社區(qū)檢測(cè)算法[9-10]、基于模塊度[11-13]的社區(qū)檢測(cè)算法、基于標(biāo)簽傳播[14-16]的社區(qū)檢測(cè)算法以及基于團(tuán)滲透[6]的社區(qū)檢測(cè)算法等。基于劃分的社區(qū)檢測(cè)算法基本思想是找出社區(qū)之間的鏈接，然后逐步刪除這些鏈接，最后剩余的便是社區(qū)結(jié)構(gòu)。2004年Mark Newman基于貪心思想提出了模塊度最大化的貪心算法(FN)，將整體最優(yōu)化問(wèn)題分解為局部最優(yōu)化問(wèn)題。模塊度的思想實(shí)際上是社區(qū)內(nèi)部的邊的密度大于網(wǎng)絡(luò)中的整體密度。為了降低算法的時(shí)間復(fù)雜度，Vincent Blondel等提出了另一種層次貪心算法[12]-基于標(biāo)簽傳播(1abel propagation algorithm，LPA)，遵從的基本思想是“在具有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)中，任一節(jié)點(diǎn)都應(yīng)當(dāng)與其大多數(shù)鄰居在同一個(gè)社區(qū)內(nèi)”。重疊社區(qū)算法[17-18]也是目前研究較多的社區(qū)檢測(cè)算法，團(tuán)滲透算法(clique percolation method，CPM)是重疊社區(qū)檢測(cè)算法的代表性算法，這種算法將網(wǎng)絡(luò)中共享節(jié)點(diǎn)的團(tuán)連接在一起形成社區(qū)。這類理論認(rèn)為，網(wǎng)絡(luò)中存在的社區(qū)是可以有重疊的，這和實(shí)際的社交網(wǎng)絡(luò)也是相符的。以微博為例，一個(gè)共同話題社區(qū)中的人可能同時(shí)也對(duì)另一個(gè)話題感興趣。Yang等[19]還研究了在有向網(wǎng)絡(luò)中利用概率模型進(jìn)行社區(qū)檢測(cè)的算法。

2.2 K-Clique基本原理

K-Clique是一種團(tuán)滲透算法，基本原理可以描述如下：將圖中的完全子圖稱為團(tuán)(完全子圖就是每?jī)蓚€(gè)點(diǎn)之間都有一條邊的子圖)，若該子圖的節(jié)點(diǎn)數(shù)為k，那么該子圖就稱為K-Clique[1]，若兩個(gè)K-Clique之間有k-1個(gè)相同節(jié)點(diǎn)，那么就稱這兩個(gè)K-Clique是相鄰的。Clique滲透算法將彼此相鄰的clique構(gòu)成的最大集合稱為社區(qū)。

3 增量式社區(qū)檢測(cè)算法

3.1 算法整體設(shè)計(jì)

該算法需要對(duì)新時(shí)間片內(nèi)網(wǎng)絡(luò)中新增的元素進(jìn)行處理，再使用處理結(jié)果去更新已有結(jié)果。首先定義以下幾個(gè)概念：

定義1：CSS(complete subgraph set，完全子圖集)，這個(gè)集合中存儲(chǔ)的是已處理的網(wǎng)絡(luò)中現(xiàn)有的所有完全子圖結(jié)構(gòu)。

定義2：DS(difference subgraph，差分子圖)，這是一個(gè)圖結(jié)構(gòu)，在第一個(gè)時(shí)間片上，DS就是當(dāng)前時(shí)間片內(nèi)除去CSS中包含元素之外的子圖結(jié)構(gòu)。從第二個(gè)時(shí)間片開始，DS存儲(chǔ)的是當(dāng)前時(shí)間片中新增節(jié)點(diǎn)和邊以及上個(gè)時(shí)間片中遺留的DS所共同構(gòu)成的網(wǎng)絡(luò)US(unprocessed subgraph)中去除了CSS中包含的節(jié)點(diǎn)及邊之后的剩余元素。

定義3：US(unprocessed subgraph，未處理子圖)，這是當(dāng)前時(shí)間片中新增節(jié)點(diǎn)和邊以及上個(gè)時(shí)間片中遺留的DS所共同構(gòu)成的網(wǎng)絡(luò)。

首先對(duì)第一個(gè)時(shí)間片中的網(wǎng)絡(luò)進(jìn)行傳統(tǒng)K-Clique社區(qū)發(fā)現(xiàn)，保存第一個(gè)時(shí)間片中節(jié)點(diǎn)數(shù)大于等于k的CSS,以及時(shí)間片中關(guān)于CSS的差集所構(gòu)成的DS，這個(gè)DS實(shí)際上也就是非完全子圖所構(gòu)成的局部網(wǎng)絡(luò)，這些非完全子圖雖然在當(dāng)前處理的新增網(wǎng)絡(luò)內(nèi)沒(méi)有被涵蓋在社區(qū)之中，但有可能會(huì)與后續(xù)新增網(wǎng)絡(luò)中的節(jié)點(diǎn)構(gòu)成完全子圖，從而參與社區(qū)更新。

在對(duì)下一個(gè)時(shí)間片的數(shù)據(jù)進(jìn)行處理時(shí)，需要將DS也融入當(dāng)前的時(shí)間片新增數(shù)據(jù)中構(gòu)成當(dāng)前US。對(duì)于當(dāng)前時(shí)間片上的US，先找出其中包含的所有完全子圖，之后，以新發(fā)現(xiàn)的完全子圖去更新CSS以及DS。處理完最后一個(gè)時(shí)間片中的US后，對(duì)于CSS中的每一個(gè)完全子圖，如果兩個(gè)完全子圖之間的共同節(jié)點(diǎn)數(shù)大于等于k-1,那么以完全子圖為基本節(jié)點(diǎn)，在兩個(gè)完全子圖之間連一條邊，構(gòu)成一張宏觀上的圖H，圖H中的每個(gè)節(jié)點(diǎn)都是一個(gè)完全子圖，圖H中的每一個(gè)連通圖就是整個(gè)網(wǎng)絡(luò)中的一個(gè)社區(qū)。

上述步驟可以用Algorithem1來(lái)描述，其中最主要的部分包括updateCSS、updateDS。

Algorithem1:

Input：dynamic Graph increases over time，K

Output: Communities in Graph

Get CSS in first time slice

Get DS in first time slice

While time slice:

Get US by combining DS with new edges and nodes in current time slice

Find newCliques in US

Call updateCSS(newCliques)

Call updateDS(newCliques)

Communities=combination of those cliques in CSS who’s common nodes>k-1 (connected parts in H)

3.2 更新CSS

在處理新時(shí)間片上未處理數(shù)據(jù)US時(shí)分為兩步，首先需要獲取當(dāng)前US中所包含的完全子圖結(jié)構(gòu)，然后以這些新的完全子圖去更新CSS。更新CSS時(shí)分為以下三種情況：

(1)新發(fā)現(xiàn)的clique與已有的所有clique均無(wú)交集;

(2)新發(fā)現(xiàn)的clique完全囊括于CSS中已有的clique中;

(3)新發(fā)現(xiàn)的clique與多個(gè)clique有交集，但不囊括于其中任何一個(gè)。

這幾種情況如圖2所示，白色節(jié)點(diǎn)和實(shí)線構(gòu)成的圖表示已有clique，黑色節(jié)點(diǎn)和虛線構(gòu)成的圖表示新發(fā)現(xiàn)的clique。

圖2 CSS更新類別

情況(1)：直接將新發(fā)現(xiàn)的clique加入CSS中即可，不需要做其他改變。

情況(2)：新發(fā)現(xiàn)的clique對(duì)CSS中已有的clique不會(huì)造成結(jié)構(gòu)和數(shù)量上的改變，因此不需要對(duì)CSS進(jìn)行更新。

情況(3)：需要將與新clique有交集的已有clique進(jìn)行結(jié)構(gòu)上的更新，可能會(huì)造成CSS中已有clique的數(shù)量的變化。對(duì)于結(jié)構(gòu)上可能造成的改變，采取的方式是，將新發(fā)現(xiàn)的clique與與其有交集的若干個(gè)clique先拼接成一張臨時(shí)圖結(jié)構(gòu)，再?gòu)倪@個(gè)臨時(shí)圖結(jié)構(gòu)中找出其中包含的完全子圖。以這個(gè)方式重構(gòu)相關(guān)clique之后，需要將之前的clique從CSS中刪除，然后將重構(gòu)后的若干個(gè)新Clique加入CSS中。更新CSS的算法如下：

Algorithem2:updateCSS

Input:newCliques

Output:updated CSS

If CSS==null:

CSS=newCliques;

Else:

for clique innewCliques:

If clique has no intersection with CSS:

add clique into CSS;

Else:

If clique belongs to one of CSS:

Do nothing;

Else:

Joint clique with related cliques in CSS;

Find new cliques structure in the jointed graph;

Add these new cliques into CSS and remove the old ones;

3.3 更新DS

在更新DS時(shí)，基本原則是將新發(fā)現(xiàn)的clique中包含的節(jié)點(diǎn)和邊從DS中刪除，以免這些節(jié)點(diǎn)在下個(gè)時(shí)間片的US內(nèi)被重復(fù)運(yùn)算。但是實(shí)際情況下，新發(fā)現(xiàn)的clique中的節(jié)點(diǎn)可能還與DS中其他非clique中的節(jié)點(diǎn)有聯(lián)系，為了保存這樣的聯(lián)系，需要保留這樣的clique節(jié)點(diǎn)。判斷的依據(jù)是，如果某個(gè)clique中包含的某個(gè)節(jié)點(diǎn)的度大于其所在的所有clique中所有的節(jié)點(diǎn)數(shù)，即說(shuō)明當(dāng)前節(jié)點(diǎn)除了存在于clique中的邊以外還有其他邊連接，這樣的節(jié)點(diǎn)就不予刪除。采用遍歷的方式收集需要?jiǎng)h除的節(jié)點(diǎn)，上述過(guò)程描述如下：

Algorithem3:updateDS

Input:newCliques

Output:updated DS

S=all nodes in newCliques

For node N in S:

Find all the cliques innewCliques which include node N

If degree of node in DS>=sum of all cliques size:

Remove node from S

For clique innewCliques:

Remove edges innewClique from DS

Remove nodes in S from G

4 性能優(yōu)化

為了提高算法的執(zhí)行效率，縮短節(jié)點(diǎn)與clique的查找時(shí)間，文中采用兩張哈希表的方式來(lái)存儲(chǔ)clique集合以及節(jié)點(diǎn)到已有clique之間的映射關(guān)系，如圖3所示。

圖3 clique存儲(chǔ)方式

圖3中有兩張哈希表，HashTable2中，每個(gè)clique都是一個(gè)真實(shí)的圖結(jié)構(gòu)，且每一個(gè)clique都有唯一對(duì)應(yīng)的key值。HashTable1表示節(jié)點(diǎn)到clique鍵值對(duì)的映射，其中的Key_Clique表示的就是HashTable2中的key。當(dāng)節(jié)點(diǎn)屬于某一個(gè)clique中，那么就將node作為key，該clique對(duì)應(yīng)的編號(hào)作為值存儲(chǔ)在左側(cè)的哈希表中。

同時(shí)還定義了一個(gè)資源池POOL，即clique的key值的資源分配池，定義POOL的目的是當(dāng)容納clique哈希表有更新時(shí)，能夠有效地重分配key值。在更新HashTable2中的clique時(shí)，對(duì)POOL資源池的更新分為兩種情況：

(1)新發(fā)現(xiàn)的clique沒(méi)有對(duì)已有的clique的結(jié)構(gòu)造成影響，只要將新發(fā)現(xiàn)的clique直接加入HashTable2中并為其分配未使用過(guò)的唯一鍵值作為其標(biāo)識(shí)。而這個(gè)時(shí)候就必須要知道哪些鍵值已經(jīng)被使用過(guò)，每次都重新遍歷一次HashTable2的所有鍵就過(guò)于麻煩，而使用POOL資源池時(shí)就可以不用每次都遍歷，直接從POOL池中選取鍵值即可，選取之后POOL資源池中對(duì)應(yīng)的鍵值會(huì)被刪除，以保證鍵的唯一性。

(2)另一種情況是新發(fā)現(xiàn)的clique結(jié)構(gòu)對(duì)已有的clique結(jié)構(gòu)造成了影響，這種情況下要采取的措施是，結(jié)構(gòu)改變了的clique會(huì)從HashTable2中刪除，并且POOL資源池對(duì)這些被刪除的clique的鍵進(jìn)行回收。隨后將結(jié)構(gòu)改變后的clique重新放入HashTable2中，并且從POOL中分配相應(yīng)數(shù)目的鍵值對(duì)結(jié)構(gòu)更新后的clique進(jìn)行標(biāo)識(shí)。這種情況下使用POOL的好處是，既保證了HashTable2中每個(gè)clique都有唯一標(biāo)識(shí)，又可以使得鍵能被有效地回收利用，不用每次去與已有clique比對(duì)，從而保證不會(huì)分配已經(jīng)使用過(guò)的鍵值。

5 實(shí) 驗(yàn)

5.1 DBLP數(shù)據(jù)集

DBLP是計(jì)算機(jī)界反映共同作者關(guān)系的公共數(shù)據(jù)集，數(shù)據(jù)集中包含了期刊或會(huì)議論文的共同作者信息以及論文發(fā)表時(shí)間信息。在這個(gè)數(shù)據(jù)集中，提取了1990-2016年發(fā)表于ICML會(huì)議的論文的共同作者信息，以作者為節(jié)點(diǎn)，以作者之間的共同發(fā)表文章的關(guān)系為邊，即若兩個(gè)作者共同發(fā)表了一篇文章，就在這兩個(gè)作者中間連接一條邊。最終的圖中共包含4 771個(gè)節(jié)點(diǎn)，9 641條邊。

5.2 算法效率

分別在上述數(shù)據(jù)集中對(duì)比了傳統(tǒng)K-Clique與增量K-Clique在k分別為2,3,4,5時(shí)的運(yùn)行效率，如圖4所示。

圖4 增量K-Clique與傳統(tǒng)K-Clique效率對(duì)比

可以看到，隨著時(shí)間片的遞增，網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，增量K-Clique算法比傳統(tǒng)K-Clique算法在運(yùn)行效率上有明顯的提升，且k越大，效率提升得越顯著。這是由于隨著k的增大，對(duì)社區(qū)的密集程度要求更高，發(fā)現(xiàn)的社區(qū)數(shù)量相對(duì)較少，能夠更加有效地減少社區(qū)增量更新過(guò)程中的一些計(jì)算量。

5.3 算法準(zhǔn)確率

表1分別記錄了k=2,3,4,5時(shí)從1990年到某一年使用K-Clique(CK)算法和增量K-Clique(incremental K-Clique，ICK)算法所發(fā)現(xiàn)的社區(qū)數(shù)量比較。可以看到，k=2時(shí)，K-Clique與增量K-Clique算法均是尋找網(wǎng)絡(luò)中的連通圖，因此兩種方式尋找出的社區(qū)數(shù)量是一致的。當(dāng)k≥3時(shí)，由于增量式K-Clique算法會(huì)忽略少量的連接細(xì)節(jié)，因此發(fā)現(xiàn)的社區(qū)數(shù)量與K-Clique相比會(huì)略多一些，但是數(shù)量基本與K-Clique發(fā)現(xiàn)的社區(qū)數(shù)量持平。

表1 K-Clique與增量K-Clique社區(qū)檢測(cè)數(shù)量比較

為了更直觀地看到算法的檢測(cè)效果，圖5為在檢測(cè)出社區(qū)數(shù)量較小的情況下K-Clique算法與增量K-Clique算法的社區(qū)檢測(cè)結(jié)果對(duì)比。取時(shí)間片1990至1993年為止的(k=4時(shí))兩種算法社區(qū)檢測(cè)結(jié)果作對(duì)比，可以看到增量K-Clique算法與傳統(tǒng)K-Clique的檢測(cè)結(jié)果基本吻合。

6 結(jié)束語(yǔ)

社區(qū)檢測(cè)是現(xiàn)實(shí)中各種網(wǎng)絡(luò)的重要分析手段，因此社區(qū)檢測(cè)的研究具有重要的實(shí)際意義。文中對(duì)K-Clique團(tuán)滲透算法(CMP)在大規(guī)模網(wǎng)絡(luò)中進(jìn)行改進(jìn)。這種改進(jìn)算法適用于網(wǎng)絡(luò)結(jié)構(gòu)比較緊密的大規(guī)模網(wǎng)絡(luò)中，在算法效率上有明顯提升。而在網(wǎng)絡(luò)規(guī)模稀疏的情況下可能效果會(huì)有所衰減，因?yàn)樗惴赡軙?huì)忽略較多的細(xì)節(jié)從而導(dǎo)致準(zhǔn)確率下降。后續(xù)會(huì)將這種算法應(yīng)用到實(shí)際問(wèn)題中，例如挖掘社交網(wǎng)絡(luò)的密集用戶社區(qū)，以進(jìn)一步挖掘社區(qū)中的隱含信息等。

K-Clique增量K-Clique'John H.Gennari','KazuoHiraki','Yoshinobu Yamamoto','Yuichiro Anzai' 'John H.Gennari','KazuoHiraki','Yoshinobu Yamamoto','Yuichiro Anzai' 'DanaKedzier','DonaldMichie','ClaudeSammut','Scott Hurst''DanaKedzier','DonaldMichie','ClaudeSammut', 'Scott Hurst''Paul R. Cohen','Adam St.Amant', 'Adam Carlson','Lisa Ballesteros''Paul R. Cohen','Adam St.Amant','Adam Carlson','Lisa Ballesteros''James Garrett','Bradley L. Whitehall','Thomas G.Dietterich','Stephen C. Y. Lu','Richard J. Doyle','BrianFalkenhainer','Steve A.Chien''James Garrett','Bradley L. Whitehall','Thomas G.Dietterich','Stephen C. Y. Lu','Richard J. Doyle','BrianFalkenhainer','Steve A.Chien''JohnVittal','Bernard Silver','William J.Frawley','Kelly Bradford','Glenn A.Iba''JohnVittal','Bernard Silver','William J.Frawley','Kelly Bradford','Glenn A.Iba''David K.Tcheng','Stephen C. Y. Lu','Larry A. Rendell','Bruce L. Lambert''David K.Tcheng','Stephen C. Y. Lu','Larry A. Rendell','Bruce L. Lambert''Lee A.Appelbaum','Stuart L. Crawford','Richard M. Tong','Robert M. Fung''Lee A.Appelbaum','Stuart L. Crawford','Richard M. Tong','Robert M. Fung''Stewart W. Wilson','Alexandre Parodi','PierreBonelli','Sandip Sen''Stewart W. Wilson','Alexandre Parodi','PierreBonelli','Sandip Sen''Glenn R.Koller','Qian Yang','Jerry B. Weinberg','Gautam Biswas''Jerry B. Weinberg','Qian Yang','Glenn R.Koller','Gautam Biswas''Davide De Marchi','Attilio Giordana','Filippo Brancadori','FrancescoBergadano','Lorenza Saitta''Davide De Marchi', 'Attilio Giordana','Filippo Brancadori','FrancescoBergadano','Lorenza Saitta''Christopher M. Tuck','John E. Laird','Eric S.Yager','MichaelHucka''Christopher M. Tuck','John E. Laird','Eric S.Yager','MichaelHucka'

圖5 K-Clique與增量K-Clique社區(qū)檢測(cè)結(jié)果比較