一種社交網絡的增量社區檢測算法及實現優化

王冰玉，吳振宇，沈蘇彬

(1.南京郵電大學 物聯網學院，江蘇 南京 210000；2.南京郵電大學 計算機學院，江蘇 南京 210000)

1 概 述

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

現實中的社交網絡規模都是較大的，對DBLP數據集中1990年-2016年中包含的會議論文的共同作者關系所形成的網絡運行了K-Clique算法，算法的執行效率如圖1所示。

圖1 社區檢測隨網絡規模變化的時間消耗

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

2 相關研究

2.1 社區檢測算法研究

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

2.2 K-Clique基本原理

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

3 增量式社區檢測算法

3.1 算法整體設計

該算法需要對新時間片內網絡中新增的元素進行處理，再使用處理結果去更新已有結果。首先定義以下幾個概念：

定義1：CSS(complete subgraph set，完全子圖集)，這個集合中存儲的是已處理的網絡中現有的所有完全子圖結構。

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

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

首先對第一個時間片中的網絡進行傳統K-Clique社區發現，保存第一個時間片中節點數大于等于k的CSS,以及時間片中關于CSS的差集所構成的DS，這個DS實際上也就是非完全子圖所構成的局部網絡，這些非完全子圖雖然在當前處理的新增網絡內沒有被涵蓋在社區之中，但有可能會與后續新增網絡中的節點構成完全子圖，從而參與社區更新。

在對下一個時間片的數據進行處理時，需要將DS也融入當前的時間片新增數據中構成當前US。對于當前時間片上的US，先找出其中包含的所有完全子圖，之后，以新發現的完全子圖去更新CSS以及DS。處理完最后一個時間片中的US后，對于CSS中的每一個完全子圖，如果兩個完全子圖之間的共同節點數大于等于k-1,那么以完全子圖為基本節點，在兩個完全子圖之間連一條邊，構成一張宏觀上的圖H，圖H中的每個節點都是一個完全子圖，圖H中的每一個連通圖就是整個網絡中的一個社區。

上述步驟可以用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

在處理新時間片上未處理數據US時分為兩步，首先需要獲取當前US中所包含的完全子圖結構，然后以這些新的完全子圖去更新CSS。更新CSS時分為以下三種情況：

(1)新發現的clique與已有的所有clique均無交集;

(2)新發現的clique完全囊括于CSS中已有的clique中;

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

這幾種情況如圖2所示，白色節點和實線構成的圖表示已有clique，黑色節點和虛線構成的圖表示新發現的clique。

圖2 CSS更新類別

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

情況(2)：新發現的clique對CSS中已有的clique不會造成結構和數量上的改變，因此不需要對CSS進行更新。

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

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 性能優化

為了提高算法的執行效率，縮短節點與clique的查找時間，文中采用兩張哈希表的方式來存儲clique集合以及節點到已有clique之間的映射關系，如圖3所示。

圖3 clique存儲方式

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

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

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

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

5 實 驗

5.1 DBLP數據集

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

5.2 算法效率

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

圖4 增量K-Clique與傳統K-Clique效率對比

可以看到，隨著時間片的遞增，網絡規模不斷擴大，增量K-Clique算法比傳統K-Clique算法在運行效率上有明顯的提升，且k越大，效率提升得越顯著。這是由于隨著k的增大，對社區的密集程度要求更高，發現的社區數量相對較少，能夠更加有效地減少社區增量更新過程中的一些計算量。

5.3 算法準確率

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

表1 K-Clique與增量K-Clique社區檢測數量比較

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

6 結束語

社區檢測是現實中各種網絡的重要分析手段，因此社區檢測的研究具有重要的實際意義。文中對K-Clique團滲透算法(CMP)在大規模網絡中進行改進。這種改進算法適用于網絡結構比較緊密的大規模網絡中，在算法效率上有明顯提升。而在網絡規模稀疏的情況下可能效果會有所衰減，因為算法可能會忽略較多的細節從而導致準確率下降。后續會將這種算法應用到實際問題中，例如挖掘社交網絡的密集用戶社區，以進一步挖掘社區中的隱含信息等。

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社區檢測結果比較