顧 炎，熊 超

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210023)

動(dòng)態(tài)社區(qū)的點(diǎn)增量發(fā)現(xiàn)算法

顧 炎，熊 超

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210023)

當(dāng)前復(fù)雜網(wǎng)絡(luò)中動(dòng)態(tài)社區(qū)發(fā)現(xiàn)方式大多為孤立地考察當(dāng)前時(shí)間節(jié)點(diǎn)，沒(méi)有利用之前時(shí)間節(jié)點(diǎn)上社區(qū)結(jié)構(gòu)的信息，因而產(chǎn)生了大量的冗余計(jì)算。為解決此問(wèn)題，基于動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)在短時(shí)間內(nèi)未發(fā)生過(guò)多改變的短時(shí)平滑性假設(shè)，提出了一種增量聚類動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法。該算法將物理學(xué)領(lǐng)域萬(wàn)有引力的思想引入到動(dòng)態(tài)社區(qū)發(fā)現(xiàn)中，針對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)，定義了節(jié)點(diǎn)間的相互作用力，在t-1與t時(shí)刻社區(qū)變化差量的基礎(chǔ)上，通過(guò)比較節(jié)點(diǎn)間作用力對(duì)節(jié)點(diǎn)的社區(qū)歸屬進(jìn)行了分析和調(diào)整，以期在t時(shí)刻快速準(zhǔn)確地發(fā)現(xiàn)動(dòng)態(tài)社區(qū)。在安然郵件數(shù)據(jù)集上的實(shí)驗(yàn)表明，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量達(dá)到104以上，提出的算法能夠在兩分鐘左右的時(shí)間內(nèi)挖掘出模塊度為0.53左右的社區(qū)結(jié)構(gòu)，優(yōu)于其他幾種算法，說(shuō)明該方法能夠快速準(zhǔn)確地挖掘出較好的社區(qū)結(jié)構(gòu)。

節(jié)點(diǎn)；增量；動(dòng)態(tài)網(wǎng)絡(luò)；社區(qū)發(fā)現(xiàn)

0 引 言

人類是社會(huì)性動(dòng)物，往往基于類似的喜好、共享的利益和共同的地緣等聚集成群體，這樣的群體被稱之為社區(qū)?？傮w上，一個(gè)社區(qū)內(nèi)部個(gè)體之間的交往頻繁，不同社區(qū)個(gè)體之間的交往較少。社區(qū)是基于中觀尺度視角有效描述社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)的重要指標(biāo)，而社區(qū)發(fā)現(xiàn)則是社會(huì)網(wǎng)絡(luò)分析中的基礎(chǔ)性研究問(wèn)題之一。隨著Internet的不斷發(fā)展和普及，開放網(wǎng)絡(luò)環(huán)境下各種信息應(yīng)用平臺(tái)不斷涌現(xiàn)，為人和人之間的溝通提供了豐富的電子技術(shù)手段和虛擬交互環(huán)境。

在此應(yīng)用背景下，社區(qū)發(fā)現(xiàn)逐步成為工業(yè)界和學(xué)術(shù)界普遍關(guān)心的熱點(diǎn)問(wèn)題，人們希望通過(guò)對(duì)社區(qū)進(jìn)行定量、有效的數(shù)據(jù)分析和挖掘，發(fā)現(xiàn)被虛擬數(shù)據(jù)所隱藏的人群活動(dòng)規(guī)律。

復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)主要研究的問(wèn)題是如何挖掘出內(nèi)部節(jié)點(diǎn)密集互聯(lián)的子集，即網(wǎng)絡(luò)中所有節(jié)點(diǎn)被分成多個(gè)子部分，相比于不同子部分，位于同一個(gè)子部分內(nèi)的節(jié)點(diǎn)之間有著較為緊密的鏈接關(guān)系。對(duì)社區(qū)的發(fā)現(xiàn)和分析，有助于確定復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特性，找到有影響力的個(gè)人[1]，促進(jìn)例如目標(biāo)營(yíng)銷和廣告[2]等的應(yīng)用。社區(qū)發(fā)現(xiàn)問(wèn)題一經(jīng)社會(huì)學(xué)專家提出，便得到了諸如通信、商務(wù)、醫(yī)療等領(lǐng)域研究人員的廣泛關(guān)注。很多研究人員也提出了各自的社區(qū)發(fā)現(xiàn)方法，但是這些方法大都針對(duì)的是靜態(tài)社區(qū)，忽視了由于內(nèi)部節(jié)點(diǎn)頻繁的相互作用，復(fù)雜網(wǎng)絡(luò)在不斷動(dòng)態(tài)演變這一事實(shí)，效果不盡如人意。因此，越來(lái)越多的研究者將目光投向動(dòng)態(tài)社區(qū)發(fā)現(xiàn)。

社區(qū)結(jié)構(gòu)的動(dòng)態(tài)分析不僅有助于更好地理解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)，還能有效地預(yù)測(cè)網(wǎng)絡(luò)的未來(lái)趨勢(shì)[3]，對(duì)于信息傳播、網(wǎng)絡(luò)營(yíng)銷和群體事件的監(jiān)管等應(yīng)用都大有裨益。當(dāng)前大多數(shù)動(dòng)態(tài)社區(qū)發(fā)現(xiàn)方法是將不同時(shí)間節(jié)點(diǎn)上的復(fù)雜網(wǎng)絡(luò)看成一個(gè)獨(dú)立的網(wǎng)絡(luò)，這類方法忽略了復(fù)雜網(wǎng)絡(luò)隨時(shí)間變化的僅是少量信息，如幾個(gè)節(jié)點(diǎn)、幾條邊的加入以及消失，沒(méi)有充分利用到前面時(shí)間節(jié)點(diǎn)上的社區(qū)結(jié)構(gòu)信息，產(chǎn)生了大量的冗余計(jì)算。

因此通過(guò)局部調(diào)整復(fù)雜網(wǎng)絡(luò)中少量發(fā)生改變的部分，快速得到社區(qū)結(jié)構(gòu)的增量式方法成為研究人員關(guān)注的新焦點(diǎn)。

基于默認(rèn)網(wǎng)絡(luò)中社區(qū)數(shù)目不發(fā)生改變且不考慮節(jié)點(diǎn)增加與刪減的假設(shè)，引入物理學(xué)領(lǐng)域萬(wàn)有引力的思想，定義節(jié)點(diǎn)間的作用力Fin和Fout，基于動(dòng)態(tài)網(wǎng)絡(luò)在時(shí)刻t-1和t的變化差量，通過(guò)比較Fin和Fout的大小判斷節(jié)點(diǎn)在t時(shí)刻是否改變了社區(qū)歸屬，將改變了社區(qū)歸屬的節(jié)點(diǎn)劃分到Fout最大的社區(qū)，其余節(jié)點(diǎn)保持原有社區(qū)歸屬，以期達(dá)到快速準(zhǔn)確發(fā)現(xiàn)動(dòng)態(tài)社區(qū)的目的。

1 相關(guān)工作

動(dòng)態(tài)社區(qū)作為一個(gè)新興研究領(lǐng)域，很多問(wèn)題的提出及其研究方法都與靜態(tài)社區(qū)類似。Berger-Wolf等[3]提出了分析動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)的基本框架，以充分利用社區(qū)結(jié)構(gòu)改變的信息來(lái)描述動(dòng)態(tài)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。Tantipathananandh等[4]基于文獻(xiàn)[3]的研究成果，通過(guò)構(gòu)建社會(huì)成本模型，從任意圖表序列中挖掘出動(dòng)態(tài)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。竇炳琳等[5]基于事件框架分析了DBLP和Facebook的數(shù)據(jù)，通過(guò)研究社區(qū)結(jié)構(gòu)演化的進(jìn)程發(fā)現(xiàn)社區(qū)間的合并和分裂很大程度上與社區(qū)本身的聚類系數(shù)相關(guān)。

從數(shù)學(xué)模型的角度，動(dòng)態(tài)網(wǎng)絡(luò)可抽象為有序的圖序列。圖序列是網(wǎng)絡(luò)在不同時(shí)間節(jié)點(diǎn)上的快照，為社會(huì)網(wǎng)絡(luò)研究人員提供了研究社區(qū)演化的素材。Palla等[6]利用一種基于完全子圖滲透的算法聚類網(wǎng)絡(luò)快照，對(duì)社會(huì)網(wǎng)絡(luò)中的大小社區(qū)分別進(jìn)行了分析。Asur等[7]利用馬爾可夫算法聚類網(wǎng)絡(luò)快照，基于事件框架機(jī)制分別研究了社會(huì)網(wǎng)絡(luò)中的社區(qū)及個(gè)人。Falkowski等[8]兩次使用分裂式層次聚類算法，先從每個(gè)網(wǎng)絡(luò)快照中挖掘出靜態(tài)社區(qū)，構(gòu)成一組社區(qū)圖，對(duì)社區(qū)圖再次使用聚類算法得到動(dòng)態(tài)社區(qū)。

然而，這些算法雖然準(zhǔn)確性較高，但在效率方面往往不盡如人意。為彌補(bǔ)算法在效率上的缺失，在后續(xù)的研究中，研究人員又提出了許多增量聚類動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法。

Dinh等[9]提出了MIEN(Modules Identification in Evolving Networks)算法，這是一種動(dòng)態(tài)自適應(yīng)算法，核心在于用緊湊的模塊代替整個(gè)網(wǎng)絡(luò)，在縮小網(wǎng)絡(luò)規(guī)模的同時(shí)能夠及時(shí)有效地更新社區(qū)結(jié)構(gòu)。王玙等[10]在邊的橋系數(shù)[11]這一概念的基礎(chǔ)上，提出了一種基于橋系數(shù)的增量聚類動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法，依據(jù)橋系數(shù)對(duì)前一個(gè)時(shí)間節(jié)點(diǎn)上的社區(qū)結(jié)構(gòu)進(jìn)行局部調(diào)整，得到當(dāng)前網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。郭進(jìn)時(shí)等[12]仿照文獻(xiàn)[13]定義了拓?fù)鋭?shì)這一概念，通過(guò)聚類屬性加權(quán)序列圖得到動(dòng)態(tài)社區(qū)。單波等[14]定義了增量相關(guān)節(jié)點(diǎn)集合，通過(guò)分析和調(diào)整增量相關(guān)節(jié)點(diǎn)的社區(qū)歸屬快速挖掘出動(dòng)態(tài)社區(qū)結(jié)構(gòu)。

2 增量聚類形式化定義

用帶有N個(gè)節(jié)點(diǎn)v和M條邊e的無(wú)向圖G=(V,E)表示復(fù)雜網(wǎng)絡(luò)，其中V是頂點(diǎn)集合，E是邊集合。用C=(C1,C2,…,Ck)表示網(wǎng)絡(luò)中的社區(qū)，CSi(i=1,2,…,k)表示i社區(qū)的社區(qū)結(jié)構(gòu)。

為刻畫動(dòng)態(tài)網(wǎng)絡(luò)，需要在不同時(shí)刻對(duì)其采樣，得到不同時(shí)刻靜態(tài)網(wǎng)絡(luò)所對(duì)應(yīng)的一個(gè)無(wú)向圖，這個(gè)無(wú)向圖就是動(dòng)態(tài)網(wǎng)絡(luò)在這個(gè)時(shí)刻的網(wǎng)絡(luò)快照。動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)用G1,G2,…,Gn來(lái)表示，其中Gt=(Vt,Et)就是動(dòng)態(tài)網(wǎng)絡(luò)在t時(shí)刻的快照。

用模塊度[15]來(lái)度量社區(qū)劃分的好壞，其計(jì)算公式如下：

(1)

模塊度越高，說(shuō)明社區(qū)結(jié)構(gòu)越好。表1列出了所用概念的符號(hào)及其描述。

表1 符號(hào)和描述

由短時(shí)平滑性假設(shè)[16]可知，Gt-1與Gt變化很小。在此背景下，重新聚類Gt會(huì)產(chǎn)生大量的重復(fù)計(jì)算。因此增量聚類動(dòng)態(tài)社區(qū)發(fā)現(xiàn)主要研究的內(nèi)容是：針對(duì)Gt與Gt-1的變化，基于t-1時(shí)刻的聚類結(jié)果CSt-1，通過(guò)局部調(diào)整得到CSt。

問(wèn)題的形式化描述為：已知t-1時(shí)刻的社區(qū)結(jié)構(gòu)CSt-1，t-1時(shí)刻的網(wǎng)絡(luò)快照Gt-1，t時(shí)刻的網(wǎng)絡(luò)快照Gt。求t時(shí)刻的社區(qū)結(jié)構(gòu)CSt。

3 基于節(jié)點(diǎn)的增量聚類算法

3.1 算法基本思想

基于節(jié)點(diǎn)的增量聚類算法(Vertex-based Incremental Algorithm for Community Detecting，VICA)基于文獻(xiàn)[14]的思想：在動(dòng)態(tài)網(wǎng)絡(luò)中，t時(shí)刻大部分節(jié)點(diǎn)的社區(qū)歸屬都與t-1時(shí)刻相同，只有少量節(jié)點(diǎn)會(huì)改變其社區(qū)歸屬。在t-1時(shí)刻社區(qū)結(jié)構(gòu)已知的基礎(chǔ)上，將少量改變了社區(qū)歸屬的節(jié)點(diǎn)劃分給新社區(qū)，從而快速得到t時(shí)刻的社區(qū)結(jié)構(gòu)。

3.1.1 增量節(jié)點(diǎn)

在t時(shí)刻網(wǎng)絡(luò)中,若新加入的邊的兩端節(jié)點(diǎn)位于同一社區(qū)或者消失的邊的兩端節(jié)點(diǎn)位于不同社區(qū)，社區(qū)的凝聚力增強(qiáng)，社區(qū)結(jié)構(gòu)不會(huì)發(fā)生改變。相反，若新加入的邊的兩端節(jié)點(diǎn)位于不同社區(qū)或者消失的邊的兩端節(jié)點(diǎn)位于同一社區(qū)，社區(qū)的凝聚力減弱，社區(qū)結(jié)構(gòu)可能發(fā)生改變，這些節(jié)點(diǎn)就是在t時(shí)刻可能改變社區(qū)歸屬的節(jié)點(diǎn)，稱之為增量相關(guān)節(jié)點(diǎn)[14]，所有增量相關(guān)節(jié)點(diǎn)構(gòu)成增量相關(guān)節(jié)點(diǎn)集合。因?yàn)樵趖時(shí)刻網(wǎng)絡(luò)中大部分節(jié)點(diǎn)不會(huì)改變其社區(qū)歸屬，所以重點(diǎn)研究增量相關(guān)節(jié)點(diǎn)。增量相關(guān)節(jié)點(diǎn)集合和節(jié)點(diǎn)改變社區(qū)歸屬的定義如下。

定義1:t時(shí)刻的增量相關(guān)節(jié)點(diǎn)集合IVt={v|e+=(u,v)且C(u)和C(v)不是同一社區(qū)或e=(u,v)且C(u)和C(v)是同一社區(qū)}。

其中，e+=(u，v)∈(EtEt-1)表示t-1時(shí)刻不存在，而在t時(shí)刻新增的邊；e-=(u，v)∈(Et-1Et)表示t-1時(shí)刻存在，而t時(shí)刻刪減的邊。

定義2：若在t-1時(shí)刻v∈Ci，在t時(shí)刻v∈Cj，i≠j，稱節(jié)點(diǎn)v在t時(shí)刻改變了社區(qū)歸屬。

3.1.2 節(jié)點(diǎn)間作用力

對(duì)于增量相關(guān)節(jié)點(diǎn)，關(guān)鍵工作在于判斷其在t時(shí)刻是否改變了社區(qū)歸屬，若是，將其劃分給哪個(gè)社區(qū)。

文獻(xiàn)[14]提出的利用依存度判斷增量相關(guān)節(jié)點(diǎn)在t時(shí)刻是否改變了社區(qū)歸屬，并將改變了社區(qū)歸屬的節(jié)點(diǎn)劃分給其依存度最大的社區(qū)的方法未被采用，所需要的是，將改變了社區(qū)歸屬的節(jié)點(diǎn)劃分給新社區(qū)后，整個(gè)網(wǎng)絡(luò)能夠獲得最佳的模塊度。

(2)

(3)

其中，S∈NC(v)，doutS與dS相等，意思相反。

3.1.3 聚類分析

對(duì)于在t時(shí)刻改變了社區(qū)歸屬的節(jié)點(diǎn)，下一步工作就是將其劃分給新社區(qū)。

借鑒文獻(xiàn)[18]中的Theorem 1，但Theorem 1僅適用于t時(shí)刻網(wǎng)絡(luò)中新增節(jié)點(diǎn)改變社區(qū)歸屬的情形，并不適用于已存在的節(jié)點(diǎn)改變社區(qū)歸屬的情形。為此，提出了命題1，規(guī)定在t時(shí)刻將改變了社區(qū)歸屬的節(jié)點(diǎn)劃分至NC(v)中Fout(v)最大的社區(qū)，如圖1所示。

命題1:將在t時(shí)刻改變了社區(qū)歸屬的頂點(diǎn)v劃分給NC(v)中Fout(v)最大的社區(qū)，整個(gè)網(wǎng)絡(luò)的模塊度最佳。

證明:假設(shè)頂點(diǎn)v的度為p，社區(qū)C是NC(v)中Fout(v)最大的社區(qū)，D∈NC(v)，C≠D。當(dāng)v轉(zhuǎn)移至C時(shí)，整個(gè)網(wǎng)絡(luò)模塊度為：

(4)

其中,A是其他社區(qū)對(duì)模塊度的影響。

圖1 將頂點(diǎn)劃分給新社區(qū)

當(dāng)v轉(zhuǎn)移至D時(shí),模塊度為：

(5)

(6)

(7)

所以有:

(8)

于是Q-Q'>0，得證。

3.2 VICA算法

VICA算法步驟：在增量相關(guān)節(jié)點(diǎn)集合IVt中找到那些滿足改變社區(qū)歸屬條件的節(jié)點(diǎn)v，將其劃分到NC(v)中Fout(v)最大的社區(qū)中，其余頂點(diǎn)維持原來(lái)的社區(qū)歸屬。

VICA算法:

輸入：t-1時(shí)刻的社區(qū)結(jié)構(gòu)CSt-1,i(i=1,2,…,k)，t時(shí)刻的網(wǎng)絡(luò)拓?fù)銰t;

輸出：t時(shí)刻的社區(qū)結(jié)構(gòu)CSt,i(i=1,2,…,k)。

1.fori=1 tokdo

2.forv∈Ct-1,ido

3.if(v∈IVt)

6.把v劃分到社區(qū)Cj

7.else

8.v的社區(qū)歸屬不變

9.end if

10.end if

11.end for

12.end for

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)數(shù)據(jù)使用安然郵件數(shù)據(jù)集，這是當(dāng)前社會(huì)網(wǎng)絡(luò)研究中使用較多的公開數(shù)據(jù)集之一，它包括安然公司150位高級(jí)管理人員從1999年1月至2002年7月期間往來(lái)的郵件，這些郵件在安然公司接受美國(guó)聯(lián)邦能源監(jiān)管委員會(huì)調(diào)查時(shí)被公布到網(wǎng)上，可在CMU計(jì)算機(jī)學(xué)院網(wǎng)站上下載。用這一真實(shí)的數(shù)據(jù)集對(duì)VICA算法進(jìn)行驗(yàn)證，每個(gè)郵件聯(lián)系者在數(shù)據(jù)集中都通過(guò)唯一的一個(gè)標(biāo)識(shí)號(hào)來(lái)表示，每個(gè)鏈接則對(duì)應(yīng)于郵件聯(lián)系者之間發(fā)送的郵件。仿照文獻(xiàn)[14]的做法，采集了從2000年4月到2002年4月期間的數(shù)據(jù)，得到8個(gè)類似的網(wǎng)絡(luò)快照，在這些網(wǎng)絡(luò)快照的基礎(chǔ)上進(jìn)行實(shí)驗(yàn)。

實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM)2 2.66 GHz Quad CPU，4 GB DRAM，WinXP。為了驗(yàn)證VICA算法在動(dòng)態(tài)社區(qū)發(fā)現(xiàn)問(wèn)題上的有效性，用以下三種動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法作為對(duì)照。

(1)IC算法：由單波等提出，基于短時(shí)平滑性假設(shè)，通過(guò)分析社區(qū)結(jié)構(gòu)差量來(lái)發(fā)現(xiàn)動(dòng)態(tài)社區(qū)，根據(jù)文獻(xiàn)[14]將閾值ε設(shè)定為0.1；

(2)Framework算法：由Tantipathananandh等提出，基于染色法的算法框架來(lái)分析社團(tuán)演化，為簡(jiǎn)便起見，稱其為Framework算法；

(3)FaceNet算法：由Lin等[19]提出，基于快照序列，聚類以發(fā)現(xiàn)快照時(shí)間代價(jià)最小的網(wǎng)絡(luò)社區(qū)，為簡(jiǎn)便起見，稱其為FaceNet算法。

4.2 實(shí)驗(yàn)對(duì)比

首先比較四種算法的運(yùn)行時(shí)間，與文獻(xiàn)[14]類似，在上述網(wǎng)絡(luò)快照中抽樣出不同規(guī)模的網(wǎng)絡(luò)，頂點(diǎn)數(shù)量分別是16，112，927，10 223，91 469，分別對(duì)應(yīng)101，102，103，104，105這五個(gè)數(shù)量級(jí)。

不同規(guī)模網(wǎng)絡(luò)算法的運(yùn)行時(shí)間如圖2所示。

圖2 不同規(guī)模網(wǎng)絡(luò)算法的運(yùn)行時(shí)間

由圖2可以看出，當(dāng)網(wǎng)絡(luò)中頂點(diǎn)的量級(jí)不超過(guò)103時(shí)，四種算法的運(yùn)行時(shí)間相差無(wú)幾，其中VICA、IC、Framework都在10 s以內(nèi)，而FaceNet要稍長(zhǎng)一些。但是當(dāng)網(wǎng)絡(luò)中頂點(diǎn)的量級(jí)大于103時(shí)，F(xiàn)ramework和FaceNet的運(yùn)行時(shí)間大幅增加，其中Framework增加得尤為明顯，在105這個(gè)量級(jí)上運(yùn)行時(shí)間已經(jīng)達(dá)到了8 134 s。而此時(shí)VICA和IC的運(yùn)行時(shí)間分別是126 s和118 s，增幅相對(duì)平緩。因此得出結(jié)論：在相同情況下，VICA和IC的運(yùn)行時(shí)間要低于FaceNet和Framework，并且VICA的運(yùn)行時(shí)間要稍高于IC，但兩者的差距并不是很大。

其次比較四種算法得到的社區(qū)質(zhì)量，與文獻(xiàn)[14]一樣，用模塊度Modularity Q進(jìn)行衡量。

算法結(jié)果的模塊度如圖3所示。

圖3 算法結(jié)果的模塊度

由圖3可以看出，VICA、IC、FaceNet的Q值高于Framework，而在VICA、IC、FaceNet三者中VICA的Q值是最高的。此外，VICA、IC、FaceNet的Q值相對(duì)穩(wěn)定，維持在0.53上下，而Framework的Q值則波動(dòng)較大，最低為0.34，最高能達(dá)到0.50。因此得出結(jié)論：在相同情況下，相比于IC、FaceNet、Framework，VICA能夠得到更好的社區(qū)。

綜上所述，與IC、FaceNet、Framework算法相比，VICA算法能夠在較短的運(yùn)行時(shí)間內(nèi)得到更好的社區(qū)結(jié)構(gòu)。

5 結(jié)束語(yǔ)

依據(jù)短時(shí)平滑性假設(shè)，基于復(fù)雜網(wǎng)絡(luò)在短時(shí)間內(nèi)變化小這一事實(shí)，引入頂點(diǎn)間的相互作用力，通過(guò)分析社區(qū)變化差量，識(shí)別出改變了社區(qū)歸屬的節(jié)點(diǎn)，劃分到新的社區(qū)中，快速地發(fā)現(xiàn)動(dòng)態(tài)社區(qū)。實(shí)驗(yàn)在真實(shí)數(shù)據(jù)集上驗(yàn)證了VICA算法的準(zhǔn)確性和高效性。VICA算法的前提在于復(fù)雜網(wǎng)絡(luò)中社區(qū)數(shù)目保持不變，并且沒(méi)有考慮頂點(diǎn)增加和刪減的情形，顯然不完備，完善這些不足是今后工作的重點(diǎn)。

[1] Berger-Wolf T Y,Saia J.Critical groups in dynamic social networks[R].[s.l.]:[s.n.],2005.

[2] Kempe D,Kleinberg J,Tardos é.Maximizing the spread of influence through a social network[C]//Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2003:137-146.

[3] Berger-Wolf T Y,Saria J.A framework for analysis of dynamic social networks[C]//Proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2006:523-528.

[4] Tantipathananandh C,Berger-Wolf T Y,Kempe D.A framework for community identification in dynamic social networks[C]//Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2007:717-726.

[5] 竇炳琳,李澍淞,張世永.基于結(jié)構(gòu)的社會(huì)網(wǎng)絡(luò)分析[J].計(jì)算機(jī)學(xué)報(bào),2012,35(4):741-753.

[6] Palla G,Barabasi A L,Vicsek T.Quantifying social group evolution[J].Nature,2007,446(7136):664-667.

[7] Asur S,Parthasarathy S,Ucar D.An event-based framework for characterizing the evolutionary behavior of interaction graphs[J].ACM Transactions on Knowledge Discovery From Data,2009,3(4):913-921.

[8] Falkowski T.Community analysis in dynamic social networks[M].[s.l.]:[s.n.],2009.

[9] Dinh T,Xuan Y,Thai M T.Towards social-aware routing in dynamic communication networks[C]//28th international conference on performance computing and communications conference.[s.l.]:IEEE,2009:161-168.

[10] 王 玙,高 琳.動(dòng)態(tài)網(wǎng)絡(luò)橋系數(shù)增量聚類算法[J].西安電子科技大學(xué)學(xué)報(bào),2013,40(1):30-35.

[11] Cheng X Q,Ren F X,Shen H W,et al.Bridgeness:a local index on edge significance in maintaining global connectivity[J].Journal of Statistical Mechanics:Theory and Experiment,2010(10):595-685.

[12] 郭進(jìn)時(shí),湯紅波,王曉雷.基于社會(huì)網(wǎng)絡(luò)增量的動(dòng)態(tài)社區(qū)組織探測(cè)[J].電子與信息學(xué)報(bào),2013,35(9):2240-2246.

[13] 淦文燕,赫 南,李德毅,等.一種基于拓?fù)鋭?shì)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J].軟件學(xué)報(bào),2009,20(8):2241-2254.

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

[15] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[16] 王 莉,程學(xué)旗.在線社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)及演化[J].計(jì)算機(jī)學(xué)報(bào),2015,38(2):219-237.

[17] Ye Z,Hu S,Yu J.Adaptive clustering algorithm for community detection in complex networks[J].Physical Review E,2008,78(2):046115.

[18] Nguyen N P,Dinh T N,Xuan Y,et al.Adaptive algorithms for detecting community structure in dynamic social networks[C]//International conference on computer communications.[s.l.]:IEEE,2011:2282-2290.

[19] Lin Y R,Chi Y,Zhu S,et al.Facetnet:a framework for analyzing communities and their evolutions in dynamic networks[C]//Proceedings of the 17th international conference on World Wide Web.[s.l.]:ACM,2008:685-694.

Vertex-based Incremental Algorithm for Dynamic Communities Detecting

GU Yan，XIONG Chao

(School of Computer Science & Technology，Nanjing University of Posts and Telecommunications，Nanjing 210023,China)

Currently,most ways of community detection in dynamic complex networks belongs to separate observations on nonce time nodes without utilization of community structural information on former time nodes,thus more redundant computation has been generated.To solve this problem,on the short-term smoothness assumption that the dynamic community networks could not generate too many changes in short-time interval,an incremental clustering algorithm for detecting dynamic communities has been proposed.The universal gravitation in physic field has been introduced into community detection and mutual forces has been defined between nodes in dynamic community.The community adscription of the node has been analyzed and adjusted through comparison of the mutual forces based on the difference betweent-1 andtinterval so as to detect dynamic community quickly and accurately attinterval.Results of experiments on Enron email dataset show that when the network has more than 104 vertices,the proposed algorithm can detect community structures with modularity at around 0.53 within about two minutes and is more efficient than other algorithms,and thus it can detect dynamic community structures quickly and accurately.

vertex;incremental;dynamic network;community detecting

2016-07-12

2016-11-17 網(wǎng)絡(luò)出版時(shí)間：2017-05-03

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272422)

顧 炎(1992-)，男，碩士，研究方向?yàn)樯鐣?huì)計(jì)算。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170503.1347.002.html

TP391

A

1673-629X(2017)06-0081-05

10.3969/j.issn.1673-629X.2017.06.017