動態網絡社區發現綜述

高 陽， 張宏莉

( 哈爾濱工業大學 計算機科學與技術學院, 哈爾濱 150001)

0 引 言

真實世界網絡的拓撲結構總是在不斷變化的，網絡隨時可能會增加、刪除節點或者邊，網絡的社區結構也會隨之變化，于是就產生了動態網絡的社區發現問題。動態網絡可以采用2種模型來描述[1]：

(1)TN (Temporal Networks)[1-4]。 動態網絡可表示為圖G=(V,E,T), 其中V表示動態網絡中節點的集合，V中每個元素(v,ts,te)(ts≤te)包含3個基本屬性，v表示網絡中一個節點，ts,te∈T分別表示該節點在網絡中出現和消亡時間點；E表示動態網絡中邊的集合，E中每個元素(u,v,ts,te)(ts≤te)包含4個基本屬性，u,v∈V表示該邊的2個端點，ts,te∈T分別表示該邊在網絡中出現和消亡的時間點。

(2)SN (Network Snapshots)。 動態網絡表示為一個向量〈G1,G2，…，Gt〉, 包含動態網絡在每個時間點的拓撲結構，其中Gi=(Vi,Ei)，Vi,Ei分別表示該時間點對應的節點和邊的集合。

1 動態網絡社區發現概述

給定一個動態網絡，一個動態社區DC (Dynamic Community)表示一些具有時間屬性(period)節點的集合，DC={(v1,P1),(v2,P2)，…，(vn,Pn)}，其中Pi=((ts0,te0),(ts1,te1)，…，(tsN,teN))(tsj≤tej)表示節點vi的N個存在時期。動態網絡社區發現是指發現動態網絡中所有的動態社區[1]。動態網絡的社區發現主要有2個研究目標，對此可做闡釋分述如下。

(1)快速準確地發現動態網絡在每個時間點的社區結構。

(2)建立演化鏈來描述社區的生命周期及演化過程[1]。

動態網絡中的社區可以發生以下變化：

(1)出生。指一個社區第一次在網絡中出現。

(2)消亡。指一個社區從網絡中消失，該社區內全部節點不再隸屬于該社區。

(3)變大。一個社區的規模由于加入了新節點而增長。

(4)收縮。一些節點移出某個社區，該社區規模因此變小。

(5)合并。2個或多個社區合并成一個社區。

(6)分裂，由于節點或邊的消失，一個社區分裂成多個部分。

(7)不變。一個社區沒有變化。

(8)復活。一個社區消失一段時間后，再次沒有任何變化地在網絡中出現[1,5-6]。

綜上變化如圖1所示[1]。

(a) 社區的出生和消亡

(b) 社區的變大和收縮

(c) 社區的合并和分裂

(d) 社區保持不變

(e) 社區復活

圖1 社區變化[1]

Fig. 1 Community events[1]

2 動態網絡社區發現研究

目前獲取動態網絡社區結構的方法大致可分為3類，分別是：靜態方法、基于演化的方法和基于增量的方法。這里擬對此展開研究論述如下。

2.1 靜態方法

該類方法中，首先獨立地對動態網絡在每一個時間點上的網絡進行社區發現，一般采用某種靜態網絡的社區發現算法來求解；為了發現社區的變化過程，該類方法一般會對相鄰兩個時間點的社區進行匹配。

Palla等人[6]將CPM算法應用到了動態網絡中。算法通過采用CPM算法對每個時間點的網絡獨立地進行社區發現，再對相鄰時間點的社區進行匹配，該算法把2個相鄰時間點的網絡組成一個網絡，并在這個組合網絡上用CPM算法進行社區發現，用組合網絡上的社區幫助匹配相鄰時間點的社區。Doyle等人[7]選擇非重疊社區發現算法Louvain作為每個時間點網絡的社區發現方法，采用二進制集合的Jaccard系數[8]來計算社區之間的相似度，從而進行相鄰時間點網絡社區之間的匹配并分析社區的演化過程。

這類方法的主要優勢是可采用現有的靜態社區發現算法進行每個時間點的社區發現，具有很大的選擇范圍，對相鄰時間點社區的匹配過程也有很多集合匹配算法作為基礎；而且，不同時間點的社區發現相對獨立，很容易實現算法的并行化[1]。

2.2 基于演化的方法

Chakrabarti等人[9]提出了基于演化的動態網絡社區發現方法(Evolutionary Clustering)。該類方法在進行社區發現時需要優化2個方面：首先，在每個時間點的網絡社區結構需要與當前網絡的拓撲結構盡可能地吻合；與此同時，相鄰2個時間點的網絡社區結構不能發生過大的變化。Chakrabarti等人提出了2種分別基于k-means方法和凝聚式層次聚類的動態網絡社區發現方法。Lin等人[10]基于同樣的方法提出了FacetNet, FacetNet采用非負矩陣分解方法用社區演化的平滑度來幫助發現社區結構。

這類方法可以平衡某一時間點網絡社區結構的質量和與前一時間點網絡社區結構之間的關聯，社區演化的平滑性得到了保證，但是不同時間點網絡的社區結構一般需要單獨計算，耗時較高，難以完成大規模動態網絡的社區發現。

2.3 基于增量的方法

對于給定動態網絡G={G0,G1…}，基于增量的動態網絡社區發現方法首先采用某種靜態社區發現算法對第一個時間點的網絡G0進行完整的社區劃分，根據網絡拓撲結構的變化對社區進行不斷更新，得到后續時間點的網絡社區結構。這種方法只完成一次整體的社區劃分，社區的更新一般只發生在網絡結構發生變化的位置附近，因而這種方法極大地提高了動態網絡社區發現的效率，同時也可保證社區演化的平滑。

Ning等人[11]提出了一種基于譜聚類的動態網絡社區發現算法，算法將動態網絡的變化分為節點之間相似度的變化和增刪節點，并用關聯向量和關聯矩陣表示2種動態變化，通過增量譜聚類算法得到動態網絡的社區結構。Cazabet等人[12]提出iLCD算法。iLCD算法根據網絡拓撲結構的變化(網絡不斷增加邊和節點)，對前一個時間點的社區進行更新、合并、并生成新社區來發現當前時間點的社區結構。該算法可以發現動態網絡中的重疊社區結構，但是沒有考慮到當網絡中有節點或者邊刪除時社區的變化情況。

Nguyen等人[13]提出了基于模塊化的QCA算法，將網絡拓撲結構的變化分為增刪節點和增刪邊，對每種網絡結構的變化分別建立了相應的社區結構更新方法。該算法可快速地根據網絡的變化對社區結構進行更新，但是不能發現重疊社區結構。在此基礎上，Nguyen等人[14]又提出了AFOCS算法，同樣將網絡拓撲結構的變化分為增刪節點和增刪邊等4種情況，但是允許一個節點屬于多個社區，可以發現動態網絡的重疊社區結構。Xin等人[15]提出了一種基于隨機游走的靜態網絡重疊社區發現算法RWS，并提出ARWS算法來實現對動態網絡社區的更新，ARWS算法同樣將動態網絡的變化分為以上四種情況，將網絡中的增刪節點以及其相鄰節點和網絡中增刪邊所連接的節點加入到隊列中，用RWS算法對隊列中節點進行計算，從而完成社區的更新。ARWS算法同樣具有很高的社區發現效率，但是算法具有過多的參數，不同參數值對社區發現結果影響較大。

3 結束語

針對目前存在的大量動態網絡社區發現算法，本文介紹了一些文獻對動態網絡和動態社區的定義，分析了動態網絡中社區發生的主要變化，給出了動態網絡社區發現算法的分類。本文可以幫助不熟悉這個研究領域的科研人員了解動態網絡的社區發現；也可以幫助科研人員在有動態社區發現需求時選擇最好的算法分類；同時也可以輔助做這方面研究的學者選擇今后的研究方向。