一種社交網(wǎng)絡(luò)的增量社區(qū)檢測算法及實現(xiàn)優(yōu)化

王冰玉，吳振宇，沈蘇彬

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

1 概 述

在社交網(wǎng)絡(luò)中，存在一些聯(lián)系較為緊密的人群，這些人之間的互動和聯(lián)系緊密和頻繁，常常會把這類人群聚類用來分析[1]，在社交網(wǎng)絡(luò)研究領(lǐng)域中一般將這些人群所構(gòu)成的團(tuán)體稱為社區(qū)[2]。發(fā)現(xiàn)社交網(wǎng)絡(luò)中的社區(qū)是十分有意義的，可以從中挖掘出許多隱含信息[3-4]。目前針對社交網(wǎng)絡(luò)的社區(qū)檢測算法進(jìn)行了研究，如崔泓等[5]針對社交網(wǎng)絡(luò)提出一種基于模塊化的社區(qū)檢測算法。社區(qū)的特點顯而易見，即社區(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ī)界反映共同作者關(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ū)檢測算法，優(yōu)點在于其允許重疊社區(qū)的存在，且其參數(shù)k可以直觀地表示社區(qū)檢測的密度要求。

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

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

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

2 相關(guān)研究

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

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

2.2 K-Clique基本原理

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

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

3.1 算法整體設(shè)計

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

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

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

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

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

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

上述步驟可以用Algorithem1來描述，其中最主要的部分包括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ù)據(jù)US時分為兩步，首先需要獲取當(dāng)前US中所包含的完全子圖結(jié)構(gòu)，然后以這些新的完全子圖去更新CSS。更新CSS時分為以下三種情況：

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

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

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

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

圖2 CSS更新類別

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

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

情況(3)：需要將與新clique有交集的已有clique進(jìn)行結(jié)構(gòu)上的更新，可能會造成CSS中已有clique的數(shù)量的變化。對于結(jié)構(gòu)上可能造成的改變，采取的方式是，將新發(fā)現(xiàn)的clique與與其有交集的若干個clique先拼接成一張臨時圖結(jié)構(gòu)，再從這個臨時圖結(jié)構(gòu)中找出其中包含的完全子圖。以這個方式重構(gòu)相關(guān)clique之后，需要將之前的clique從CSS中刪除，然后將重構(gòu)后的若干個新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時，基本原則是將新發(fā)現(xiàn)的clique中包含的節(jié)點和邊從DS中刪除，以免這些節(jié)點在下個時間片的US內(nèi)被重復(fù)運算。但是實際情況下，新發(fā)現(xiàn)的clique中的節(jié)點可能還與DS中其他非clique中的節(jié)點有聯(lián)系，為了保存這樣的聯(lián)系，需要保留這樣的clique節(jié)點。判斷的依據(jù)是，如果某個clique中包含的某個節(jié)點的度大于其所在的所有clique中所有的節(jié)點數(shù)，即說明當(dāng)前節(jié)點除了存在于clique中的邊以外還有其他邊連接，這樣的節(jié)點就不予刪除。采用遍歷的方式收集需要刪除的節(jié)點，上述過程描述如下：

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é)點與clique的查找時間，文中采用兩張哈希表的方式來存儲clique集合以及節(jié)點到已有clique之間的映射關(guān)系，如圖3所示。

圖3 clique存儲方式

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

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

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

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

5 實 驗

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

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

5.2 算法效率

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

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

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

5.3 算法準(zhǔn)確率

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

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

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

6 結(jié)束語

社區(qū)檢測是現(xiàn)實中各種網(wǎng)絡(luò)的重要分析手段，因此社區(qū)檢測的研究具有重要的實際意義。文中對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ī)模稀疏的情況下可能效果會有所衰減，因為算法可能會忽略較多的細(xì)節(jié)從而導(dǎo)致準(zhǔn)確率下降。后續(xù)會將這種算法應(yīng)用到實際問題中，例如挖掘社交網(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ū)檢測結(jié)果比較