董 哲，伊 鵬

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，450002，鄭州）

社團(tuán)作為復(fù)雜網(wǎng)絡(luò)的重要特性受到了研究者的日益關(guān)注。社團(tuán)將網(wǎng)絡(luò)劃分成許多由節(jié)點(diǎn)組成的群組，群組內(nèi)部節(jié)點(diǎn)連接非常緊密而群組之間連接則較為稀疏。發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)具有很多重要的應(yīng)用，如恐怖組織識(shí)別、網(wǎng)絡(luò)輿情監(jiān)控以及謠言的傳播行為分析等。在動(dòng)態(tài)網(wǎng)絡(luò)中，由于其結(jié)構(gòu)更加復(fù)雜，因此挖掘動(dòng)態(tài)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)變得異常困難。

目前，關(guān)于復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)的研究已經(jīng)取得了很多成果［1-3］。在現(xiàn)實(shí)生活中，絕大多數(shù)的網(wǎng)絡(luò)都具有動(dòng)態(tài)特性，這些網(wǎng)絡(luò)隨著時(shí)間的推移不斷發(fā)生演化。雖然，這些變化對(duì)于網(wǎng)絡(luò)的局部結(jié)構(gòu)產(chǎn)生的影響較小，但隨著時(shí)間積累網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)會(huì)發(fā)生明顯的變化，因此需要對(duì)其社團(tuán)進(jìn)行重新發(fā)現(xiàn)。目前，已經(jīng)提出了許多動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法。如Tang等人提出一種類似于語義迭代分析過程的算法［4］，發(fā)現(xiàn)動(dòng)態(tài)多模網(wǎng)絡(luò)中社團(tuán)演化情況，該算法能夠得到局部最優(yōu)的社團(tuán)結(jié)構(gòu)，但是卻需要人為指定社團(tuán)個(gè)數(shù)，不能自適應(yīng)地得到最優(yōu)的社團(tuán)結(jié)構(gòu)。文獻(xiàn)［5］提出了分析動(dòng)態(tài)網(wǎng)絡(luò)中社團(tuán)的Social Cost算法，將社團(tuán)發(fā)現(xiàn)轉(zhuǎn)化為圖著色問題，但該算法只關(guān)注特定個(gè)體的演化關(guān)系，不能從全局的角度來得到社團(tuán)結(jié)構(gòu)。還有其他一些動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)算法，如：Gong等人提出一種基于局部搜索的多目標(biāo)免疫算法［6］，但該算法復(fù)雜度非常大；Nguyen等人提出一種自適應(yīng)增量算法QCA算法［7］，該算法只對(duì)發(fā)生變化的節(jié)點(diǎn)進(jìn)行處理，能夠得到較優(yōu)的社團(tuán)，但節(jié)點(diǎn)的變化情況復(fù)雜多變，導(dǎo)致算法的復(fù)雜度較大；文獻(xiàn)［8］提出一種主題模型來發(fā)現(xiàn)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，但是其算法的復(fù)雜度較大；文獻(xiàn)［9］提出一種簡(jiǎn)單的增量社團(tuán)發(fā)現(xiàn)算法，該算法復(fù)雜度較小，但是其算法精度較差；文獻(xiàn)［10］提出了一種基于優(yōu)化算法的動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)方法，該算法避免了網(wǎng)絡(luò)中離群點(diǎn)對(duì)算法的影響，提高了算法精度，但是其復(fù)雜度較大。

大多數(shù)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)方法是基于節(jié)點(diǎn)聚類的算法，難以發(fā)現(xiàn)穩(wěn)定的社團(tuán)。在網(wǎng)絡(luò)中當(dāng)節(jié)點(diǎn)存在交互關(guān)系時(shí)認(rèn)為兩節(jié)點(diǎn)間存在鏈路且唯一。因此，文獻(xiàn)［11］提出一種基于鏈路的Link算法，該算法發(fā)現(xiàn)網(wǎng)絡(luò)中穩(wěn)定的社團(tuán)具有明顯的優(yōu)勢(shì)。算法首先對(duì)網(wǎng)絡(luò)中的鏈路進(jìn)行聚類，將得到的鏈路社團(tuán)通過節(jié)點(diǎn)鏈路關(guān)系映射為節(jié)點(diǎn)社團(tuán)［12］，但該算法無法發(fā)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。

針對(duì)上述問題，本文提出一種基于鏈路聚類的增量社團(tuán)發(fā)現(xiàn)算法（link-based dynamic community detection algorithm，LDC）。該算法通過各個(gè)時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)信息得到相關(guān)鏈路增量信息，再基于改進(jìn)的鏈路劃分密度函數(shù)（LD）對(duì)鏈路增量信息進(jìn)行處理，以改進(jìn)的鏈路模塊度為目標(biāo)函數(shù)，得到鏈路社團(tuán)。為了驗(yàn)證算法的有效性，本文將其應(yīng)用于人工動(dòng)態(tài)網(wǎng)絡(luò)和真實(shí)的動(dòng)態(tài)網(wǎng)絡(luò)中。實(shí)驗(yàn)證明，本文算法能夠有效地發(fā)現(xiàn)具有典型動(dòng)態(tài)信息網(wǎng)絡(luò)中的多尺度穩(wěn)定社團(tuán)結(jié)構(gòu)。

1 相關(guān)定義與指標(biāo)

給定網(wǎng)絡(luò)G（V，E），V 為節(jié)點(diǎn)集合，E為邊集合，Ci為第i個(gè)社團(tuán)節(jié)點(diǎn)集合。給出以下定義：定義1 節(jié)點(diǎn)時(shí)序圖St表示t時(shí)刻個(gè)體間的關(guān)系，動(dòng)態(tài)網(wǎng)絡(luò)G可以用節(jié)點(diǎn)時(shí)序圖的集合表示，T為時(shí)間段劃分總數(shù)，G=（S1，S2，S3，…，St，…，ST），1≤t=G。

定義2 給定St，則鏈路圖LG是St中節(jié)點(diǎn)間邊的關(guān)系構(gòu)成的鏈路集合，如圖1所示。LG=｛0，1，2，3，4，5，6，7，8，9，10，11｝。

圖1 鏈路圖

定義3 給定鏈路L1和L2，L1=＜v1，v2＞，L2=＜v3，v4＞，其中v1、v2、v3、v4為節(jié)點(diǎn)。若L1∩L2=＜v1，v2＞∩＜v3，v4＞?，則鏈路L2與L1互為鄰鏈路。

定義4 給定t時(shí)刻鏈路社團(tuán)Ci、Cj和鏈路L=＜v1，v2＞，若｛L|L?Ci，L?Cj，v1∈Ci，v2∈Cj，i≠j｝則L為橋鏈路。

1.1 鏈路劃分密度

本文通過文獻(xiàn)［11］中的鏈路劃分密度D函數(shù)提出一種改進(jìn)的鏈路劃分密度函數(shù)DL處理增量信息。假定一個(gè)網(wǎng)絡(luò)有M 條鏈路，｛P1，…，PC｝分別將網(wǎng)絡(luò)劃分成C個(gè)鏈路子集。定義社團(tuán)的鏈路劃分密度

式中：mC=|PC|和為子集PC中鏈路數(shù)和節(jié)點(diǎn)數(shù)；mb表示社團(tuán)之間的橋鏈路數(shù)；nb｝|表示社團(tuán)之間的節(jié)點(diǎn)數(shù)。改進(jìn)的鏈路劃分密度，則

1.2 鏈路模塊度

給出矩陣HN×M，N為網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)，M為網(wǎng)絡(luò)中鏈路總數(shù)。如果鏈路l與節(jié)點(diǎn)i相關(guān)（i∈l），則H中的元素Hil=1，否則為0。令節(jié)點(diǎn)度ki=，表示與鏈路l相關(guān)的節(jié)點(diǎn)數(shù)，則模塊度為

2 LDC動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)算法

給定網(wǎng)絡(luò) G=（V，E），C=｛C1，C2，…，Ck｝，令動(dòng)態(tài)網(wǎng)絡(luò)中的增量信息為ε=｛ε1，ε2，…，εn｝。網(wǎng)絡(luò)中的鏈路可分為2類：社團(tuán)內(nèi)部的鏈路（intracommunity links，IL），即邊的2個(gè)端點(diǎn)均在該社團(tuán)內(nèi)；社 團(tuán) 之 間 的 鏈 路 （bridge-community links，BL），即邊的2個(gè)端點(diǎn)位于2個(gè)不同的社團(tuán)內(nèi)。對(duì)于G中的每一個(gè)社團(tuán)C，當(dāng)添加IL鏈路或者移除BL鏈路時(shí)使得社團(tuán)的緊密性更強(qiáng)且網(wǎng)絡(luò)結(jié)構(gòu)更加清晰。相反，移除IL鏈路和添加BL鏈路使得網(wǎng)絡(luò)結(jié)構(gòu)漸漸模糊。當(dāng)2個(gè)社團(tuán)之間不存在干擾關(guān)系，或者干擾較小時(shí)，鏈路的增加或者移除有可能形成一個(gè)新的社團(tuán)結(jié)構(gòu)。因此，在更新社團(tuán)結(jié)構(gòu)時(shí)，網(wǎng)絡(luò)結(jié)構(gòu)的細(xì)微變化將會(huì)導(dǎo)致其社團(tuán)產(chǎn)生巨大的變化。從鏈路的角度出發(fā)，通常隨著時(shí)間的推移網(wǎng)絡(luò)的變化其實(shí)就是鏈路的增加或移除。因此，網(wǎng)絡(luò)中的變化信息就是一系列簡(jiǎn)單事件的集合，這些簡(jiǎn)單的事件包括新的鏈路的加入和已經(jīng)存在的鏈路的移除等信息。

2.1 鏈路添加

當(dāng)新增加一條鏈路e時(shí)，有2種情況：①鏈路e完全處于社團(tuán)Ci內(nèi)部；②鏈路e處于社團(tuán)Ci和Cj之間，i≠j。對(duì)于情況①，根據(jù)定理1，社團(tuán)結(jié)構(gòu)保持不變。對(duì)于情況②，由定理2可知，如果橋鏈路e被劃分進(jìn)新的社團(tuán)中，則該社團(tuán)必為Ci和Cj之一。推論1給出了對(duì)橋鏈路e進(jìn)行劃分的判斷條件，如果鏈路i或者j對(duì)應(yīng)的鏈路劃分密度變化值Δdi和Δdj均不滿足，則不對(duì)該鏈路進(jìn)行操作，具體見算法1。

算法1 添加邊new-link

步驟1 輸入新加入的鏈路e和t時(shí)刻鏈路社團(tuán)結(jié)構(gòu)Ct；

步驟2 輸出t+1時(shí)刻鏈路社團(tuán)結(jié)構(gòu)Ct+1；

步驟3 若e是社團(tuán)內(nèi)部鏈路，則Ct+1≡Ct，否則k=arg max（Δdi，Δdj）并將e加入到Ck，更新Ct+1。

定理1 如果Ci是網(wǎng)絡(luò)G中一個(gè)社團(tuán)，那么添加任何一條IL鏈路到Ci，Ci不會(huì)分解成更小的模塊。

證明 假設(shè)增量信息εi表示要添加一條內(nèi)部鏈路e到社團(tuán)Ci中，則Ci的鏈路劃分密度為

令D′c表示e加入到社團(tuán)Ci時(shí)的鏈路劃分密度，則

令Δ=D′c-Dc，則Δ＞0，D′c＞Dc，故當(dāng)加入內(nèi)部鏈路e到Ci中后，社團(tuán)更穩(wěn)健。

定理2 如果添加的鏈路位于社團(tuán)Ci和Cj之間，若該橋鏈路要被重新劃分，則社團(tuán)Ci和Cj為首選。證明 假設(shè)要添加的位于社團(tuán)Ci和Cj之間的鏈路為e，則由于e的節(jié)點(diǎn)分別位于社團(tuán)Ci和Cj中，所以當(dāng)把鏈路e加入到其他社團(tuán)時(shí)，DL值并不變。對(duì)社團(tuán)Ci，鏈路e未加入時(shí)，相應(yīng)鏈路前后對(duì)應(yīng)的鏈路劃分密度為

令Δ1=D′L，i-DL，i，則Δ1＞0，故鏈路e加入社團(tuán)Ci之后，Ci的鏈路劃分密度增大。同理，令Δ2=D′L，j-DL，j，Δ2＞0，Cj的鏈路劃分密度也增大。

綜上所述，如果添加的鏈路位于社團(tuán)Ci和Cj之間時(shí)，則社團(tuán)Ci和Cj為首選。

推論1 如果添加的橋鏈路e位于社團(tuán)Ci和Cj之間，若滿足條件Δd=DL，i（E+e）-DL，j（E+e）+DL，j（E）-DL，i（E）＞0，則橋鏈路e將被劃分進(jìn)社團(tuán)Ci中，反之，橋鏈路e將被劃分進(jìn)社團(tuán)Cj中。

證明 由定理2可知，如果添加的橋鏈路e位于社團(tuán)Ci和Cj之間，Ci和Cj為其首選，則有

當(dāng)Δd＞0時(shí)，Δ1＞Δ2，則橋鏈路e應(yīng)被劃分進(jìn)社團(tuán)Ci中；當(dāng)Δd＜0時(shí)，Δ1＜Δ2，則橋鏈路e應(yīng)被劃分進(jìn)社團(tuán)Cj中。

2.2 鏈路移除

當(dāng)某鏈路e被移除時(shí)，可分為2種情況：①該橋鏈路e處于社團(tuán)Ci和Cj之間，i≠j；②該鏈路e完全處于社團(tuán)Ci內(nèi)部。依據(jù)推論3，對(duì)于情況①，移除橋鏈路時(shí)，社團(tuán)不發(fā)生變化。

推論3 如果鏈路e為社團(tuán)Ci和Cj之間的橋鏈路，當(dāng)移除該鏈路時(shí)社團(tuán)Ci和Cj結(jié)構(gòu)更加明顯，整體社團(tuán)結(jié)構(gòu)不變。

證明 當(dāng)移除的鏈路e是社團(tuán)Ci和Cj之間的橋鏈路時(shí)，社團(tuán)內(nèi)部節(jié)點(diǎn)間的鏈路關(guān)系未發(fā)生變化，而鏈路社團(tuán)之間的鏈路被移除時(shí)，社團(tuán)間的連接關(guān)系變得更稀疏，網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)更加健壯、明顯。因此，整體社團(tuán)結(jié)構(gòu)不會(huì)發(fā)生變化。對(duì)于情況②，當(dāng)移除的鏈路e是一條IL鏈路時(shí)，令S（e）表示e的鄰鏈路集合，?l∈S（e），若Ck=argmax（DL，k（l）），則將鏈路l劃分進(jìn)社團(tuán)Ck中，其中1≤k≤N，N為當(dāng)前時(shí)刻的鏈路社團(tuán)總數(shù)，具體見算法2。

算法2 移除邊removal＿link

步驟1 輸入被刪除的鏈路e和t時(shí)刻鏈路社團(tuán)結(jié)構(gòu)Ct；

步驟2 輸出t+1時(shí)刻鏈路社團(tuán)結(jié)構(gòu)Ct+1；

步驟3 若鏈路e是一條BL鏈路，則Ct+1≡Ct，否則Ck=arg max（DL，k（l）），l∈S（e）、k∈（1，N），并將鏈路l加入到社團(tuán)Ck，更新Ct+1。

算法3給出了本文LDC算法的具體步驟。

算法3 LDC算法

步驟1 輸入G=G0=（V0，E0），增量信息ε=｛ε1，ε2，…，εn｝；

步驟2 輸出t時(shí)刻網(wǎng)絡(luò)Gt的社團(tuán)結(jié)構(gòu)Ct；

步驟3 將節(jié)點(diǎn)圖G0轉(zhuǎn)化為鏈路圖；

步驟4 發(fā)現(xiàn)初始時(shí)刻鏈路圖社團(tuán)結(jié)構(gòu)C0；

步驟5 從初始時(shí)刻起，若e∈new＿link（L（u，v）），則new＿link（Ct，L（u，v）），否則removal＿link（Ct，L（u，v））；

步驟6 將鏈路社團(tuán)結(jié)構(gòu)Ct映射成為節(jié)點(diǎn)社團(tuán)，得到各個(gè)時(shí)刻節(jié)點(diǎn)社團(tuán)結(jié)構(gòu)。

2.3 LDC算法的時(shí)間復(fù)雜度分析

如LDC算法所示，算法的步驟5雖然對(duì)所有時(shí)刻和變化的鏈路信息進(jìn)行掃描，但之后的操作都是以步驟5作為判斷條件的，如果條件不滿足，就不會(huì)有后續(xù)操作。因此，運(yùn)算中真正進(jìn)行操作的遍數(shù)是εt的集合mi，即所有與增量信息有關(guān)的鏈路的數(shù)目。mi的大小與網(wǎng)絡(luò)的時(shí)刻劃分尺度有關(guān)，通過統(tǒng)計(jì)發(fā)現(xiàn)，網(wǎng)絡(luò)中mi的規(guī)模為O（m），m為鏈路數(shù)。在步驟5添加邊操作，每次循環(huán)有O（1）個(gè)單元操作，移除邊操作需要O（lk）個(gè)單元操作，其中l(wèi)為鏈路的鄰鏈路數(shù)，k為社團(tuán)個(gè)數(shù)，因此每一遍需要時(shí)間O（lk）。綜合起來，總的算法時(shí)間復(fù)雜度為O（m x lk）。

3 仿真實(shí)驗(yàn)

為驗(yàn)證LDC算法的有效性，本節(jié)分別對(duì)人工動(dòng)態(tài)網(wǎng)絡(luò)和真實(shí)的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。本文將LDC算法分別與Link算法［11］、GaoCD算法［12］、QCA 算 法［7］及 MIEN 算 法［13］進(jìn) 行 比 較。Link算法從鏈路的角度發(fā)現(xiàn)網(wǎng)絡(luò)中社團(tuán)；GaoCD基于遺傳算法，從鏈路的角度發(fā)現(xiàn)靜態(tài)網(wǎng)絡(luò)中重疊社團(tuán)結(jié)構(gòu)；QCA算法是基于節(jié)點(diǎn)的增量動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法；MIEN算法通過壓縮與解壓縮，使用快速模塊度算法更新網(wǎng)絡(luò)中的社團(tuán)。

3.1 人工網(wǎng)絡(luò)

采用文獻(xiàn)［14］的方法來生成人工數(shù)據(jù)集。該人工網(wǎng)絡(luò)數(shù)據(jù)集共由128個(gè)節(jié)點(diǎn)組成，共4個(gè)社團(tuán)，每個(gè)社團(tuán)共有32個(gè)節(jié)點(diǎn)，如圖2所示。同一社團(tuán)內(nèi)的節(jié)點(diǎn)對(duì)之間存在鏈路的概率為pin，不同社團(tuán)的節(jié)點(diǎn)間存在鏈路的概率為pout，本文令pin=0.193 5，pout=0.020 8。

圖2 具有128個(gè)節(jié)點(diǎn)4個(gè)社團(tuán)結(jié)構(gòu)的人工網(wǎng)絡(luò)數(shù)據(jù)集

為了生成動(dòng)態(tài)人工網(wǎng)絡(luò)，在第一個(gè)時(shí)刻之后的每個(gè)時(shí)刻，隨機(jī)選擇10%的節(jié)點(diǎn)離開所屬的社團(tuán)，隨機(jī)地加入到其他3個(gè)社團(tuán)中。本文按照此方法生成10個(gè)時(shí)刻的人工網(wǎng)絡(luò)。

將LDC算法應(yīng)用于該數(shù)據(jù)集，仿真結(jié)果如圖3所示。由圖3a可知，在人工動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)集中，本文提出的LDC算法其模塊度要明顯優(yōu)于其他算法。由圖3b可以看出，LDC算法發(fā)現(xiàn)的4個(gè)社團(tuán)符合實(shí)際情況；由圖3c可以看出，因?yàn)榫W(wǎng)絡(luò)中的鏈路增量變化信息較少，所以LDC算法的運(yùn)行時(shí)間相比于其他算法要少很多。標(biāo)準(zhǔn)化互信息值用來表征算法發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)與真實(shí)社團(tuán)之間的差異，用于描述算法的準(zhǔn)確性。由圖3d可以看出，由于LDC算法只針對(duì)發(fā)生變化的鏈路信息進(jìn)行處理，符合真實(shí)網(wǎng)絡(luò)中社團(tuán)的變化情況，所以其標(biāo)準(zhǔn)化互信息值要大于其他算法，提高了0.15。因此，LDC算法能夠準(zhǔn)確地發(fā)現(xiàn)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。

圖3 5種算法處理人工數(shù)據(jù)集的性能對(duì)比

3.2 真實(shí)網(wǎng)絡(luò)

為了驗(yàn)證LDC算法在現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)中的性能，本文采用了2種真實(shí)的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集，分別是ENRON郵件網(wǎng)絡(luò)［5］和 VAST數(shù)據(jù)集。ENRON郵件網(wǎng)絡(luò)數(shù)據(jù)集來自ENRON公司內(nèi)部的郵件聯(lián)系網(wǎng)絡(luò)，包含來自151名用戶郵件消息的網(wǎng)絡(luò)數(shù)據(jù)集，其時(shí)間跨度為1999年5月到2002年3月；VAST數(shù)據(jù)集來自IEEE VAST 2008，是一個(gè)開放的競(jìng)賽項(xiàng)目的數(shù)據(jù)集，它包含一組共400人10天的通話數(shù)據(jù)。

采用VAST數(shù)據(jù)集，以每一天為一個(gè)時(shí)間粒度，對(duì)比本文LDC算法和其他4種算法處理人工數(shù)據(jù)集的性能，結(jié)果如圖4所示。

由圖4a可以看出，相比于其他算法，LDC算法的鏈路模塊度提高了20%；由圖4b可見，LDC算法中發(fā)現(xiàn)VAST數(shù)據(jù)集中的社團(tuán)更加穩(wěn)定；由圖4c可知，LDC算法的效率較高，算法性能優(yōu)越；由圖4d可知，相比于其他算法，LDC算法的標(biāo)準(zhǔn)化互信息值整體提高了0.13，LDC算法利用網(wǎng)絡(luò)中的鏈路增量信息，能夠發(fā)現(xiàn)更加準(zhǔn)確的社團(tuán)結(jié)構(gòu)。

采用ENRON數(shù)據(jù)集，以每個(gè)月為一個(gè)時(shí)間粒度，對(duì)比本文LDC算法并和其他4種算法處理人工數(shù)據(jù)集的性能，結(jié)果如圖5所示。

由圖5a可以看出，LDC算法能夠更有效地發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)，相比于其他算法，LDC算法的鏈路模塊度提高了19%；由圖5b中可以看出，相比于其他幾種算法，LDC算法得到的社團(tuán)數(shù)目相對(duì)較多，這是由于該公司內(nèi)部出現(xiàn)了一些變動(dòng)，導(dǎo)致網(wǎng)絡(luò)中的鏈路增量信息不完整導(dǎo)致了社團(tuán)個(gè)數(shù)的增加，但同時(shí)說明LDC算法更傾向于發(fā)現(xiàn)具有多尺度、結(jié)構(gòu)更加穩(wěn)定的社團(tuán)結(jié)構(gòu)；圖5c說明，LDC算法的運(yùn)行效率要優(yōu)于其他算法；由圖5d可知，LDC算法的NMI值相比于其他算法要提高0.15，且要比其他算法穩(wěn)定。

圖4 5種算法處理VAST數(shù)據(jù)集對(duì)比

通過將LDC算法分別應(yīng)用于人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中并和其他算法進(jìn)行對(duì)比，由仿真結(jié)果可知，由于LDC算法是從鏈路的角度來發(fā)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)中的社團(tuán)，只對(duì)網(wǎng)絡(luò)中的鏈路變化信息進(jìn)行處理，簡(jiǎn)化了網(wǎng)絡(luò)中的增量信息，相比于其他算法，LDC算法更能夠準(zhǔn)確地發(fā)現(xiàn)網(wǎng)絡(luò)中穩(wěn)定的社團(tuán)結(jié)構(gòu)。

圖5 5種算法處理Enron數(shù)據(jù)集性能對(duì)比

4 結(jié) 論

本文提出一種基于鏈路聚類的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法——LDC算法，并提出了一種改進(jìn)的社團(tuán)劃分密度，將復(fù)雜的動(dòng)態(tài)網(wǎng)絡(luò)中的變化信息簡(jiǎn)化為鏈路添加和鏈路移除2種增量信息，從鏈路的角度重新解決社團(tuán)結(jié)構(gòu)的發(fā)現(xiàn)問題。本文分別將LDC算法應(yīng)用于人工動(dòng)態(tài)網(wǎng)絡(luò)和真實(shí)的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，與當(dāng)前的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法相比，LDC算法能夠快速準(zhǔn)確地發(fā)現(xiàn)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中穩(wěn)定的多尺度社團(tuán)結(jié)構(gòu)。

［1］ 汪小帆.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)分析算法研究綜述［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2008，5（3）：1-12.

WANG Xiaofan.An overview of algorithms for analyzing community structure in complex networks［J］.Complex Systems and Complexity Science，2008，5（3）：1-12.

［2］ 李曉佳，張鵬，狄增如，等.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2008，5（3）：19-42.

LI Xiaojia.ZHANG Peng， DI Zengru，et al.Community structure in complex networks ［J］.Complex Systems and Complexity Science，2008，5（3）：19-42.

［3］ 陳國(guó)強(qiáng)，王宇平.采用離散粒子群算法的復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)檢測(cè) ［J］.西安交通大學(xué)學(xué)報(bào)，2013，47（1）：107-113.

CHEN Guoqiang， WANG Yuping.Overlapping community detection of complex networks based on discrete particle swarm algorithm ［J］.Journal of Xi’an Jiaotong University，2013，47（1）：107-113.

［4］ TANG L，LIU H，ZHANG J.Identifying evolving groups in dynamic multimode networks ［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24（1）：72-85.

［5］ TANTIPATHANANANDH C，BERGER-WOLF T，KEMNE D.A framework for community identification in dynamic social networks ［C］∥Proceedings of the 13th ACM International Conference on Knowledge discovery and Data Mining.New York，USA：ACM，2007：717-726.

［6］ GONG M G，ZHANG L J，MA J，et al.Community detection in dynamic social networks based on multiobjective immune algorithm ［J］.Journal of Computer Science and Technology，2012，27（3）：455-467.

［7］ NGUYEN N P，DINH T N，XUAN Y，et al.Adaptive algorithms for detecting community structure in dynamic social networks ［C］∥ Proceedings IEEE INFOCOM.Piscataway，NJ，USA：IEEE，2011：2282-2290.

［8］ LI D，DING Y，SHUAI X，et al.Adding community and dynamics to topic models ［J］.Journal of Informetrics，2012，6（2）：237-253.

［9］ 單波，姜守旭，張碩，等.IC：動(dòng)態(tài)社會(huì)關(guān)系網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的增量識(shí)別算法 ［J］.軟件學(xué)報(bào)，2009，20（1）：184-192.

SHAN Bo，JIANG Shouxu，ZHANG Shuo，et al.IC：incremental algorithm for community identification in dynamic social network ［J］.Journal of Software，2009，20（1）：184-192.

［10］BASSETT D S，PORTER M A，WYMBS N F，et al.Robust detection of dynamic community structure in networks［EB／OL］.［2013-03-14］.http：∥dx.doi.org／10.1063／1.4790830.

［11］AHN Y Y，BAGROW J P， LEHMANN S.Link communities reveal multiscale complexity in networks［J］.Nature，2010，466（7307）：761-764.

［12］SHI C，CAI Y，F(xiàn)U D，et al.A link clustering based overlapping community detection algorithm ［J］.Data＆ Knowledge Engineering，2013，87（1）：394-404.

［13］DINH T N，XUAN Y，THAI M T.Towards socialaware routing in dynamic communication networks［C］∥Proceedings of IEEE 28th International Conference on Performance Computing and Communications.Piscataway，NJ，USA：IEEE，2009：161-168.

［14］YANG T，CHI Y，ZHU S，et al.Detecting communities and their evolutions in dynamic social networks：a Bayesian approach ［J］.Machine Learning，2011，82（2）：157-189.