動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)綜述

高 陽， 張宏莉

( 哈爾濱工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 哈爾濱 150001)

0 引 言

真實世界網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)總是在不斷變化的，網(wǎng)絡(luò)隨時可能會增加、刪除節(jié)點或者邊，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)也會隨之變化，于是就產(chǎn)生了動態(tài)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題。動態(tài)網(wǎng)絡(luò)可以采用2種模型來描述[1]：

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

(2)SN (Network Snapshots)。 動態(tài)網(wǎng)絡(luò)表示為一個向量〈G1,G2，…，Gt〉, 包含動態(tài)網(wǎng)絡(luò)在每個時間點的拓?fù)浣Y(jié)構(gòu)，其中Gi=(Vi,Ei)，Vi,Ei分別表示該時間點對應(yīng)的節(jié)點和邊的集合。

1 動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)概述

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

(1)快速準(zhǔn)確地發(fā)現(xiàn)動態(tài)網(wǎng)絡(luò)在每個時間點的社區(qū)結(jié)構(gòu)。

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

動態(tài)網(wǎng)絡(luò)中的社區(qū)可以發(fā)生以下變化：

(1)出生。指一個社區(qū)第一次在網(wǎng)絡(luò)中出現(xiàn)。

(2)消亡。指一個社區(qū)從網(wǎng)絡(luò)中消失，該社區(qū)內(nèi)全部節(jié)點不再隸屬于該社區(qū)。

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

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

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

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

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

(8)復(fù)活。一個社區(qū)消失一段時間后，再次沒有任何變化地在網(wǎng)絡(luò)中出現(xiàn)[1,5-6]。

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

(a) 社區(qū)的出生和消亡

(b) 社區(qū)的變大和收縮

(c) 社區(qū)的合并和分裂

(d) 社區(qū)保持不變

(e) 社區(qū)復(fù)活

圖1 社區(qū)變化[1]

Fig. 1 Community events[1]

2 動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)研究

目前獲取動態(tài)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的方法大致可分為3類，分別是：靜態(tài)方法、基于演化的方法和基于增量的方法。這里擬對此展開研究論述如下。

2.1 靜態(tài)方法

該類方法中，首先獨立地對動態(tài)網(wǎng)絡(luò)在每一個時間點上的網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)，一般采用某種靜態(tài)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法來求解；為了發(fā)現(xiàn)社區(qū)的變化過程，該類方法一般會對相鄰兩個時間點的社區(qū)進(jìn)行匹配。

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

這類方法的主要優(yōu)勢是可采用現(xiàn)有的靜態(tài)社區(qū)發(fā)現(xiàn)算法進(jìn)行每個時間點的社區(qū)發(fā)現(xiàn)，具有很大的選擇范圍，對相鄰時間點社區(qū)的匹配過程也有很多集合匹配算法作為基礎(chǔ)；而且，不同時間點的社區(qū)發(fā)現(xiàn)相對獨立，很容易實現(xiàn)算法的并行化[1]。

2.2 基于演化的方法

Chakrabarti等人[9]提出了基于演化的動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法(Evolutionary Clustering)。該類方法在進(jìn)行社區(qū)發(fā)現(xiàn)時需要優(yōu)化2個方面：首先，在每個時間點的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)需要與當(dāng)前網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)盡可能地吻合；與此同時，相鄰2個時間點的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)不能發(fā)生過大的變化。Chakrabarti等人提出了2種分別基于k-means方法和凝聚式層次聚類的動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法。Lin等人[10]基于同樣的方法提出了FacetNet, FacetNet采用非負(fù)矩陣分解方法用社區(qū)演化的平滑度來幫助發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。

這類方法可以平衡某一時間點網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的質(zhì)量和與前一時間點網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)之間的關(guān)聯(lián)，社區(qū)演化的平滑性得到了保證，但是不同時間點網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)一般需要單獨計算，耗時較高，難以完成大規(guī)模動態(tài)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。

2.3 基于增量的方法

對于給定動態(tài)網(wǎng)絡(luò)G={G0,G1…}，基于增量的動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法首先采用某種靜態(tài)社區(qū)發(fā)現(xiàn)算法對第一個時間點的網(wǎng)絡(luò)G0進(jìn)行完整的社區(qū)劃分，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化對社區(qū)進(jìn)行不斷更新，得到后續(xù)時間點的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。這種方法只完成一次整體的社區(qū)劃分，社區(qū)的更新一般只發(fā)生在網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化的位置附近，因而這種方法極大地提高了動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的效率，同時也可保證社區(qū)演化的平滑。

Ning等人[11]提出了一種基于譜聚類的動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，算法將動態(tài)網(wǎng)絡(luò)的變化分為節(jié)點之間相似度的變化和增刪節(jié)點，并用關(guān)聯(lián)向量和關(guān)聯(lián)矩陣表示2種動態(tài)變化，通過增量譜聚類算法得到動態(tài)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。Cazabet等人[12]提出iLCD算法。iLCD算法根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化(網(wǎng)絡(luò)不斷增加邊和節(jié)點)，對前一個時間點的社區(qū)進(jìn)行更新、合并、并生成新社區(qū)來發(fā)現(xiàn)當(dāng)前時間點的社區(qū)結(jié)構(gòu)。該算法可以發(fā)現(xiàn)動態(tài)網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)，但是沒有考慮到當(dāng)網(wǎng)絡(luò)中有節(jié)點或者邊刪除時社區(qū)的變化情況。

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

3 結(jié)束語

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