動態社區的點增量發現算法

顧 炎，熊 超

(南京郵電大學 計算機學院，江蘇 南京 210023)

動態社區的點增量發現算法

顧 炎，熊 超

(南京郵電大學 計算機學院，江蘇 南京 210023)

當前復雜網絡中動態社區發現方式大多為孤立地考察當前時間節點，沒有利用之前時間節點上社區結構的信息，因而產生了大量的冗余計算。為解決此問題，基于動態社會網絡在短時間內未發生過多改變的短時平滑性假設，提出了一種增量聚類動態社區發現算法。該算法將物理學領域萬有引力的思想引入到動態社區發現中，針對動態社會網絡中的節點，定義了節點間的相互作用力，在t-1與t時刻社區變化差量的基礎上，通過比較節點間作用力對節點的社區歸屬進行了分析和調整，以期在t時刻快速準確地發現動態社區。在安然郵件數據集上的實驗表明，當網絡中的節點數量達到104以上，提出的算法能夠在兩分鐘左右的時間內挖掘出模塊度為0.53左右的社區結構，優于其他幾種算法，說明該方法能夠快速準確地挖掘出較好的社區結構。

節點；增量；動態網絡；社區發現

0 引 言

人類是社會性動物，往往基于類似的喜好、共享的利益和共同的地緣等聚集成群體，這樣的群體被稱之為社區?？傮w上，一個社區內部個體之間的交往頻繁，不同社區個體之間的交往較少。社區是基于中觀尺度視角有效描述社會網絡結構的重要指標，而社區發現則是社會網絡分析中的基礎性研究問題之一。隨著Internet的不斷發展和普及，開放網絡環境下各種信息應用平臺不斷涌現，為人和人之間的溝通提供了豐富的電子技術手段和虛擬交互環境。

在此應用背景下，社區發現逐步成為工業界和學術界普遍關心的熱點問題，人們希望通過對社區進行定量、有效的數據分析和挖掘，發現被虛擬數據所隱藏的人群活動規律。

復雜網絡中社區發現主要研究的問題是如何挖掘出內部節點密集互聯的子集，即網絡中所有節點被分成多個子部分，相比于不同子部分，位于同一個子部分內的節點之間有著較為緊密的鏈接關系。對社區的發現和分析，有助于確定復雜網絡的結構特性，找到有影響力的個人[1]，促進例如目標營銷和廣告[2]等的應用。社區發現問題一經社會學專家提出，便得到了諸如通信、商務、醫療等領域研究人員的廣泛關注。很多研究人員也提出了各自的社區發現方法，但是這些方法大都針對的是靜態社區，忽視了由于內部節點頻繁的相互作用，復雜網絡在不斷動態演變這一事實，效果不盡如人意。因此，越來越多的研究者將目光投向動態社區發現。

社區結構的動態分析不僅有助于更好地理解復雜網絡的結構，還能有效地預測網絡的未來趨勢[3]，對于信息傳播、網絡營銷和群體事件的監管等應用都大有裨益。當前大多數動態社區發現方法是將不同時間節點上的復雜網絡看成一個獨立的網絡，這類方法忽略了復雜網絡隨時間變化的僅是少量信息，如幾個節點、幾條邊的加入以及消失，沒有充分利用到前面時間節點上的社區結構信息，產生了大量的冗余計算。

因此通過局部調整復雜網絡中少量發生改變的部分，快速得到社區結構的增量式方法成為研究人員關注的新焦點。

基于默認網絡中社區數目不發生改變且不考慮節點增加與刪減的假設，引入物理學領域萬有引力的思想，定義節點間的作用力Fin和Fout，基于動態網絡在時刻t-1和t的變化差量，通過比較Fin和Fout的大小判斷節點在t時刻是否改變了社區歸屬，將改變了社區歸屬的節點劃分到Fout最大的社區，其余節點保持原有社區歸屬，以期達到快速準確發現動態社區的目的。

1 相關工作

動態社區作為一個新興研究領域，很多問題的提出及其研究方法都與靜態社區類似。Berger-Wolf等[3]提出了分析動態社會網絡的基本框架，以充分利用社區結構改變的信息來描述動態網絡的社區結構。Tantipathananandh等[4]基于文獻[3]的研究成果，通過構建社會成本模型，從任意圖表序列中挖掘出動態網絡社區結構。竇炳琳等[5]基于事件框架分析了DBLP和Facebook的數據，通過研究社區結構演化的進程發現社區間的合并和分裂很大程度上與社區本身的聚類系數相關。

從數學模型的角度，動態網絡可抽象為有序的圖序列。圖序列是網絡在不同時間節點上的快照，為社會網絡研究人員提供了研究社區演化的素材。Palla等[6]利用一種基于完全子圖滲透的算法聚類網絡快照，對社會網絡中的大小社區分別進行了分析。Asur等[7]利用馬爾可夫算法聚類網絡快照，基于事件框架機制分別研究了社會網絡中的社區及個人。Falkowski等[8]兩次使用分裂式層次聚類算法，先從每個網絡快照中挖掘出靜態社區，構成一組社區圖，對社區圖再次使用聚類算法得到動態社區。

然而，這些算法雖然準確性較高，但在效率方面往往不盡如人意。為彌補算法在效率上的缺失，在后續的研究中，研究人員又提出了許多增量聚類動態社區發現算法。

Dinh等[9]提出了MIEN(Modules Identification in Evolving Networks)算法，這是一種動態自適應算法，核心在于用緊湊的模塊代替整個網絡，在縮小網絡規模的同時能夠及時有效地更新社區結構。王玙等[10]在邊的橋系數[11]這一概念的基礎上，提出了一種基于橋系數的增量聚類動態社區發現算法，依據橋系數對前一個時間節點上的社區結構進行局部調整，得到當前網絡的社區結構。郭進時等[12]仿照文獻[13]定義了拓撲勢這一概念，通過聚類屬性加權序列圖得到動態社區。單波等[14]定義了增量相關節點集合，通過分析和調整增量相關節點的社區歸屬快速挖掘出動態社區結構。

2 增量聚類形式化定義

用帶有N個節點v和M條邊e的無向圖G=(V,E)表示復雜網絡，其中V是頂點集合，E是邊集合。用C=(C1,C2,…,Ck)表示網絡中的社區，CSi(i=1,2,…,k)表示i社區的社區結構。

為刻畫動態網絡，需要在不同時刻對其采樣，得到不同時刻靜態網絡所對應的一個無向圖，這個無向圖就是動態網絡在這個時刻的網絡快照。動態社會網絡用G1,G2,…,Gn來表示，其中Gt=(Vt,Et)就是動態網絡在t時刻的快照。

用模塊度[15]來度量社區劃分的好壞，其計算公式如下：

(1)

模塊度越高，說明社區結構越好。表1列出了所用概念的符號及其描述。

表1 符號和描述

由短時平滑性假設[16]可知，Gt-1與Gt變化很小。在此背景下，重新聚類Gt會產生大量的重復計算。因此增量聚類動態社區發現主要研究的內容是：針對Gt與Gt-1的變化，基于t-1時刻的聚類結果CSt-1，通過局部調整得到CSt。

問題的形式化描述為：已知t-1時刻的社區結構CSt-1，t-1時刻的網絡快照Gt-1，t時刻的網絡快照Gt。求t時刻的社區結構CSt。

3 基于節點的增量聚類算法

3.1 算法基本思想

基于節點的增量聚類算法(Vertex-based Incremental Algorithm for Community Detecting，VICA)基于文獻[14]的思想：在動態網絡中，t時刻大部分節點的社區歸屬都與t-1時刻相同，只有少量節點會改變其社區歸屬。在t-1時刻社區結構已知的基礎上，將少量改變了社區歸屬的節點劃分給新社區，從而快速得到t時刻的社區結構。

3.1.1 增量節點

在t時刻網絡中,若新加入的邊的兩端節點位于同一社區或者消失的邊的兩端節點位于不同社區，社區的凝聚力增強，社區結構不會發生改變。相反，若新加入的邊的兩端節點位于不同社區或者消失的邊的兩端節點位于同一社區，社區的凝聚力減弱，社區結構可能發生改變，這些節點就是在t時刻可能改變社區歸屬的節點，稱之為增量相關節點[14]，所有增量相關節點構成增量相關節點集合。因為在t時刻網絡中大部分節點不會改變其社區歸屬，所以重點研究增量相關節點。增量相關節點集合和節點改變社區歸屬的定義如下。

定義1:t時刻的增量相關節點集合IVt={v|e+=(u,v)且C(u)和C(v)不是同一社區或e=(u,v)且C(u)和C(v)是同一社區}。

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

定義2：若在t-1時刻v∈Ci，在t時刻v∈Cj，i≠j，稱節點v在t時刻改變了社區歸屬。

3.1.2 節點間作用力

對于增量相關節點，關鍵工作在于判斷其在t時刻是否改變了社區歸屬，若是，將其劃分給哪個社區。

文獻[14]提出的利用依存度判斷增量相關節點在t時刻是否改變了社區歸屬，并將改變了社區歸屬的節點劃分給其依存度最大的社區的方法未被采用，所需要的是，將改變了社區歸屬的節點劃分給新社區后，整個網絡能夠獲得最佳的模塊度。

(2)

(3)

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

3.1.3 聚類分析

對于在t時刻改變了社區歸屬的節點，下一步工作就是將其劃分給新社區。

借鑒文獻[18]中的Theorem 1，但Theorem 1僅適用于t時刻網絡中新增節點改變社區歸屬的情形，并不適用于已存在的節點改變社區歸屬的情形。為此，提出了命題1，規定在t時刻將改變了社區歸屬的節點劃分至NC(v)中Fout(v)最大的社區，如圖1所示。

命題1:將在t時刻改變了社區歸屬的頂點v劃分給NC(v)中Fout(v)最大的社區，整個網絡的模塊度最佳。

證明:假設頂點v的度為p，社區C是NC(v)中Fout(v)最大的社區，D∈NC(v)，C≠D。當v轉移至C時，整個網絡模塊度為：

(4)

其中,A是其他社區對模塊度的影響。

圖1 將頂點劃分給新社區

當v轉移至D時,模塊度為：

(5)

(6)

(7)

所以有:

(8)

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

3.2 VICA算法

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

VICA算法:

輸入：t-1時刻的社區結構CSt-1,i(i=1,2,…,k)，t時刻的網絡拓撲Gt;

輸出：t時刻的社區結構CSt,i(i=1,2,…,k)。

1.fori=1 tokdo

2.forv∈Ct-1,ido

3.if(v∈IVt)

6.把v劃分到社區Cj

7.else

8.v的社區歸屬不變

9.end if

10.end if

11.end for

12.end for

4 實驗及結果分析

4.1 實驗設計

實驗數據使用安然郵件數據集，這是當前社會網絡研究中使用較多的公開數據集之一，它包括安然公司150位高級管理人員從1999年1月至2002年7月期間往來的郵件，這些郵件在安然公司接受美國聯邦能源監管委員會調查時被公布到網上，可在CMU計算機學院網站上下載。用這一真實的數據集對VICA算法進行驗證，每個郵件聯系者在數據集中都通過唯一的一個標識號來表示，每個鏈接則對應于郵件聯系者之間發送的郵件。仿照文獻[14]的做法，采集了從2000年4月到2002年4月期間的數據，得到8個類似的網絡快照，在這些網絡快照的基礎上進行實驗。

實驗環境為Intel(R) Core(TM)2 2.66 GHz Quad CPU，4 GB DRAM，WinXP。為了驗證VICA算法在動態社區發現問題上的有效性，用以下三種動態社區發現算法作為對照。

(1)IC算法：由單波等提出，基于短時平滑性假設，通過分析社區結構差量來發現動態社區，根據文獻[14]將閾值ε設定為0.1；

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

(3)FaceNet算法：由Lin等[19]提出，基于快照序列，聚類以發現快照時間代價最小的網絡社區，為簡便起見，稱其為FaceNet算法。

4.2 實驗對比

首先比較四種算法的運行時間，與文獻[14]類似，在上述網絡快照中抽樣出不同規模的網絡，頂點數量分別是16，112，927，10 223，91 469，分別對應101，102，103，104，105這五個數量級。

不同規模網絡算法的運行時間如圖2所示。

圖2 不同規模網絡算法的運行時間

由圖2可以看出，當網絡中頂點的量級不超過103時，四種算法的運行時間相差無幾，其中VICA、IC、Framework都在10 s以內，而FaceNet要稍長一些。但是當網絡中頂點的量級大于103時，Framework和FaceNet的運行時間大幅增加，其中Framework增加得尤為明顯，在105這個量級上運行時間已經達到了8 134 s。而此時VICA和IC的運行時間分別是126 s和118 s，增幅相對平緩。因此得出結論：在相同情況下，VICA和IC的運行時間要低于FaceNet和Framework，并且VICA的運行時間要稍高于IC，但兩者的差距并不是很大。

其次比較四種算法得到的社區質量，與文獻[14]一樣，用模塊度Modularity Q進行衡量。

算法結果的模塊度如圖3所示。

圖3 算法結果的模塊度

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

綜上所述，與IC、FaceNet、Framework算法相比，VICA算法能夠在較短的運行時間內得到更好的社區結構。

5 結束語

依據短時平滑性假設，基于復雜網絡在短時間內變化小這一事實，引入頂點間的相互作用力，通過分析社區變化差量，識別出改變了社區歸屬的節點，劃分到新的社區中，快速地發現動態社區。實驗在真實數據集上驗證了VICA算法的準確性和高效性。VICA算法的前提在于復雜網絡中社區數目保持不變，并且沒有考慮頂點增加和刪減的情形，顯然不完備，完善這些不足是今后工作的重點。

[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] 竇炳琳,李澍淞,張世永.基于結構的社會網絡分析[J].計算機學報,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] 王 玙,高 琳.動態網絡橋系數增量聚類算法[J].西安電子科技大學學報,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].電子與信息學報,2013,35(9):2240-2246.

[13] 淦文燕,赫 南,李德毅,等.一種基于拓撲勢的網絡社區發現方法[J].軟件學報,2009,20(8):2241-2254.

[14] 單 波,姜守旭,張 碩,等.IC:動態社會關系網絡社區結構的增量識別算法[J].軟件學報,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] 王 莉,程學旗.在線社會網絡的動態社區發現及演化[J].計算機學報,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 網絡出版時間：2017-05-03

國家自然科學基金資助項目(61272422)

顧 炎(1992-)，男，碩士，研究方向為社會計算。

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