李亞芳 賈彩燕 于 劍 劉光明

(1.北京交通大學(xué)計算機與信息技術(shù)學(xué)院，北京，100044； 2.交通數(shù)據(jù)分析與挖掘北京市重點實驗室，北京，100044)

?

一種新的社區(qū)/動態(tài)社區(qū)優(yōu)化方法*

李亞芳1,2賈彩燕1,2于 劍1,2劉光明1,2

(1.北京交通大學(xué)計算機與信息技術(shù)學(xué)院，北京，100044； 2.交通數(shù)據(jù)分析與挖掘北京市重點實驗室，北京，100044)

社區(qū)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)的重要拓?fù)涮匦灾?，成為?dāng)前的研究熱點。本文提出了一種基于邊排序和模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)方法。該方法首先對初始的靜態(tài)網(wǎng)絡(luò)進行稀疏化，然后在稀疏化后的網(wǎng)絡(luò)上依據(jù)邊的重要程度對邊進行排序，給出了一種模塊度最大化、快速邊合并的社區(qū)發(fā)現(xiàn)方法(Fast rank-based community detection, FRCD)。在初始網(wǎng)絡(luò)社區(qū)劃分結(jié)果的基礎(chǔ)上，將該方法推廣到動態(tài)、實時社區(qū)劃分上，給出了一種快速、魯棒的動態(tài)社區(qū)劃分方法(Incremental dynamic community detection, IDCD)。理論分析表明FRCD相對于邊具有線性時間復(fù)雜度。在實際和人工網(wǎng)絡(luò)上的實驗結(jié)果均表明，本文提出的方法無論在靜態(tài)網(wǎng)絡(luò)社區(qū)劃分還是在動態(tài)網(wǎng)絡(luò)社區(qū)追蹤上都優(yōu)于已有方法。

社區(qū)發(fā)現(xiàn)；模塊度；邊排序；動態(tài)性

引 言

現(xiàn)實世界中，很多系統(tǒng)都以網(wǎng)絡(luò)形式存在，如社會系統(tǒng)中的人際關(guān)系網(wǎng)、科學(xué)家合作網(wǎng)和流行病傳播網(wǎng)，生態(tài)系統(tǒng)中的神經(jīng)元網(wǎng)、基因調(diào)控網(wǎng)和蛋白質(zhì)相互作用網(wǎng)，科技系統(tǒng)中的電話網(wǎng)、因特網(wǎng)和萬維網(wǎng)等。近年來，復(fù)雜網(wǎng)絡(luò)研究已成為最重要的多學(xué)科交叉研究領(lǐng)域，吸引了越來越多研究者的目光。研究者發(fā)現(xiàn)很多實際的網(wǎng)絡(luò)具有“模塊性”[1]，即網(wǎng)絡(luò)組織結(jié)構(gòu)表現(xiàn)出明顯的社區(qū)結(jié)構(gòu)，表現(xiàn)為社區(qū)內(nèi)部連接稠密，社區(qū)間連接稀疏的中觀尺度結(jié)構(gòu)。找到網(wǎng)絡(luò)中連接緊密的簇結(jié)構(gòu)有助于更深入地了解網(wǎng)絡(luò)的本質(zhì)，認(rèn)識網(wǎng)絡(luò)結(jié)構(gòu)與其功能之間的關(guān)系，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的規(guī)則并對其行為進行預(yù)測。社區(qū)結(jié)構(gòu)可以揭示出社會系統(tǒng)的組織結(jié)構(gòu)及隨時間演化的關(guān)系，蛋白質(zhì)功能和蛋白質(zhì)物理相互作用間的內(nèi)在聯(lián)系以及網(wǎng)頁主題和超連接間的內(nèi)在關(guān)系等。

隨著對復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)分析的需求不斷增強，目前關(guān)于社區(qū)發(fā)現(xiàn)研究的方法和成果很多。如經(jīng)典的基于節(jié)點分裂的GN算法[1]、基于模塊度優(yōu)化的BGLL[2]和CNM算法[3]、基于標(biāo)簽傳播 (Label propagation algorithm, LPA)算法[4]以及基于隨機游走和壓縮編碼的Infomap算法[5]等。目前，網(wǎng)絡(luò)類型多樣化，針對網(wǎng)絡(luò)的不同類型提出的針對多模式和多內(nèi)容網(wǎng)絡(luò)的社區(qū)檢測方法[6-7]。在以上社區(qū)發(fā)現(xiàn)算法中，由于模塊度能夠作為一種衡量網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的內(nèi)部指標(biāo)，最大化模塊度以探測網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法(如BGLL和CNM)在很多領(lǐng)域得到了較成功的應(yīng)用[2-3]。然而，BGLL和CNM等方法只能對一段時間累積下的靜態(tài)網(wǎng)絡(luò)進行劃分，無法實時追蹤網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的變化，需要對相鄰時間快照得到的網(wǎng)絡(luò)重新進行社區(qū)劃分，并保存每一時間快照下的社區(qū)結(jié)構(gòu)。由于實際的動態(tài)社會網(wǎng)絡(luò)具有時間局部性，相鄰時間間隔的網(wǎng)絡(luò)結(jié)構(gòu)變化相對緩慢[8-9]。因此，對于非常相似的網(wǎng)絡(luò)反復(fù)進行社區(qū)劃分，會產(chǎn)生了很多重復(fù)的操作，從而降低算法的效率。

Shang等[10]對BGLL算法進行了擴展，該方法首先利用BGLL算法在初始子網(wǎng)絡(luò)上得到一個初始的社區(qū)劃分結(jié)果，然后通過隨機加邊的方式模擬網(wǎng)絡(luò)的增長，將新增節(jié)點不斷實時分配到已有社區(qū)之中。但是該方法存在以下兩個問題：(1)該方法屬于兩階段方法，依賴于BGLL算法得到的初始社區(qū)劃分，當(dāng)初始子網(wǎng)絡(luò)過小或選擇時機不當(dāng)而不能保證較好的初始劃分時，難以得到理想的動態(tài)社區(qū)劃分結(jié)果。對不斷增長的動態(tài)網(wǎng)絡(luò)，如何選擇一個合適的初始子網(wǎng)絡(luò)是該方法存在的一個問題；(2)由于Shang等的算法對下一個時刻增加的邊采用隨機處理的方法，導(dǎo)致不同的邊處理順序會得到不同的社區(qū)劃分結(jié)果。因此，算法的性能不夠穩(wěn)定。針對以上問題，本文提出一種基于邊排序的、模塊度優(yōu)化社區(qū)劃分算法(Fast rank-based community detection, FRCD)。該算法是一種從頭算法方法，對于靜態(tài)網(wǎng)絡(luò)能夠得到較準(zhǔn)確的社區(qū)劃分結(jié)果。并且，其動態(tài)網(wǎng)絡(luò)上的擴展算法(Incremental dynamic community detection, IDCD)對初始子網(wǎng)絡(luò)依賴性小，在FRCD算法在初始子網(wǎng)絡(luò)已有社區(qū)劃分的基礎(chǔ)上，能實時地處理以不同時間粒度為間隔的動態(tài)增加的網(wǎng)絡(luò)結(jié)構(gòu)，并且具有性能穩(wěn)定的優(yōu)點。

1 研究基礎(chǔ)

模塊度Q函數(shù)用網(wǎng)絡(luò)中連接社區(qū)內(nèi)部頂點的邊所占的比例與隨機網(wǎng)絡(luò)中連接社區(qū)結(jié)構(gòu)內(nèi)部頂點的邊所占比例的期望的差值來衡量網(wǎng)絡(luò)中社區(qū)劃分的質(zhì)量[1,11]，其定義如下

(1)

顯然，模塊度越大、網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯。因此，對于一個給定的網(wǎng)絡(luò)，可以通過最大化Q函數(shù)得到了一個較好的社區(qū)劃分結(jié)果(如BGLL算法[2]，CNM算法[3])。

通過對模塊度Q函數(shù)進行變形，可將其轉(zhuǎn)換為以下形式[10]

(2)

2 FRCD算法

基于網(wǎng)絡(luò)局部稀疏和排序的靜態(tài)社區(qū)模塊度優(yōu)化算法FRCD可分為3個步驟：計算邊的相似度、對網(wǎng)絡(luò)進行局部稀疏化及邊排序、節(jié)點社區(qū)指派及社區(qū)合并。本算法假設(shè)相似度越高的節(jié)點對，其關(guān)系越容易建立，在社區(qū)中所處的位置越靠近中心。

2.1 邊相似度計算

計算邊的強度的方法有很多，如邊介數(shù)[1]、橋系數(shù)[12]以及邊的聚集系數(shù)[12]等，這些方法都可以用于衡量兩節(jié)點關(guān)系的緊密程度。但是這些方法有的基于網(wǎng)絡(luò)全局結(jié)構(gòu)，有的計算復(fù)雜度較高，對于大規(guī)模網(wǎng)絡(luò)的處理代價較大。因此，本文采用一種基于局部的、計算簡單的Jaccard相似度方法來計算網(wǎng)絡(luò)中邊(i,j)的強度。其中，i和j為與邊(i,j)關(guān)聯(lián)的兩個節(jié)點。具體定義如下

(3)

式中：N(i)表示節(jié)點i的鄰居節(jié)點的集合，N(i)∩N(j)為節(jié)點i和節(jié)點j共有鄰居個數(shù)，N(i)∪N(j)為節(jié)點i和節(jié)點j總的鄰居個數(shù)。

通過Jaccard相似度的定義可知：如果兩個節(jié)點的共有的鄰居越多，節(jié)點間的相似程度越高，邊上的強度越大。根據(jù)本文的假設(shè)，如果兩個節(jié)點的相似性越高，這兩個節(jié)點間的關(guān)系更容易建立而且更加穩(wěn)固，并且這兩個節(jié)點在社區(qū)中所處的位置越靠近社區(qū)的中心。因此，首先按照邊的排序?qū)ψ钊菀捉㈥P(guān)系的節(jié)點進行社區(qū)指派。然后，通過最大化模塊度Q依次對其他節(jié)點進行社區(qū)指派。

2.2 網(wǎng)絡(luò)局部稀疏化

由于不同的網(wǎng)絡(luò)稀疏指數(shù)，得到的結(jié)果不同。如果稀疏值設(shè)的太小，會造成網(wǎng)絡(luò)過于稀疏，難以找到原始網(wǎng)絡(luò)中蘊含的社區(qū)結(jié)構(gòu)；設(shè)得太大，不能有效加快算法運行速度。因此，通過實驗選擇e=0.5來對網(wǎng)絡(luò)進行稀疏化，此時在各種網(wǎng)絡(luò)規(guī)模中均能得到較穩(wěn)定的社區(qū)劃分結(jié)果。顯然，通過網(wǎng)絡(luò)局部稀疏化，能夠有效減小運算復(fù)雜度，從而提高算法的運行效率。

2.3 社區(qū)指派和合并

依據(jù)假設(shè)，對稀疏化的網(wǎng)絡(luò)按照邊的相似度進行降序排序后，首先將排序在第一位的邊上兩個節(jié)點指派到同一個社區(qū)內(nèi)，作為初始的社區(qū)。然后，按照排序順序依次對后續(xù)的邊中的節(jié)點進行社區(qū)指派，即把相對位于社區(qū)邊緣的節(jié)點進行社區(qū)指派。其指派策略采用Shang等[10]動態(tài)社區(qū)指派策略。即根據(jù)邊的4種類型，依次對節(jié)點進行社區(qū)指派。通過排序，能夠保證得到比較穩(wěn)定的社區(qū)結(jié)構(gòu)。社區(qū)指派后，需要通過社區(qū)的合并對指派的結(jié)果進行進一步優(yōu)化，從而得到更符合實際的劃分結(jié)果。需要進行社區(qū)合并的小社區(qū)需要滿足以下兩個條件。

(1)不滿足弱社區(qū)的定義[14]。

如果社區(qū)A不滿足

(4)

(2)社區(qū)合并需要保證網(wǎng)絡(luò)的模塊度Q值不會減少。

本文提出了一種基于邊排序的模塊化最大化社區(qū)發(fā)現(xiàn)算法FRCD，其整體流程如下。

輸入：網(wǎng)絡(luò)G=(V，E)，稀疏化指數(shù)e。

輸出：社區(qū)結(jié)構(gòu)，節(jié)點列表。

2.4 算法的時間復(fù)雜度分析

3 IDCD算法

任給一個網(wǎng)絡(luò)，應(yīng)用FRCD算法可以對該網(wǎng)絡(luò)進行社區(qū)劃分。相應(yīng)于Shang等的方法，F(xiàn)RCD算法可以自然地擴展到對動態(tài)網(wǎng)絡(luò)社區(qū)劃分上，以實時的追蹤網(wǎng)絡(luò)結(jié)構(gòu)的變化。由于現(xiàn)實中的社會網(wǎng)絡(luò)結(jié)構(gòu)變化都是很緩慢的，合適的相鄰采樣時刻之間網(wǎng)絡(luò)變化很小。因此，通過調(diào)整時間間隔，能夠?qū)Σ煌瑫r間粒度內(nèi)增加的節(jié)點進行社區(qū)指派。

如果選取的時間粒度以一條邊的增加為粒度，稱其為基本元粒度。此時，只需要判斷該邊所屬的類型，根據(jù)邊的類型采取相應(yīng)的操作，實現(xiàn)邊關(guān)聯(lián)的節(jié)點的社區(qū)指派。在一定的時間間隔內(nèi)，當(dāng)增加的邊由多個基本元粒度邊構(gòu)成時，稱之為一定時間粒度。此時IDCD算法對新增的邊根據(jù)關(guān)聯(lián)節(jié)點是否出現(xiàn)在節(jié)點社區(qū)指派列表中分為3類：全新列表(都沒有進行社區(qū)指派)，半新列表(至少一個節(jié)點已經(jīng)進行了社區(qū)指派)，已有列表(都進行社區(qū)指派)。類似地，根據(jù)Jaccard相似度和節(jié)點的度可以對已有列表和半新的列表中的邊進行降序排列，進而由邊的重要程度逐個對邊關(guān)聯(lián)的節(jié)點進行社區(qū)指派，并更新節(jié)點社區(qū)歸屬列表，算法流程如下。

輸入：t-1時刻網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，原網(wǎng)絡(luò)以及新增的網(wǎng)絡(luò)，節(jié)點列表。

輸出：t時刻的社區(qū)結(jié)構(gòu)，更新的節(jié)點列表。

(1)對新增的節(jié)點和邊，根據(jù)節(jié)點列表分成3類；(2)根據(jù)原網(wǎng)絡(luò)對新增邊計算相似度，按照相似度和度進行降序排序；(3)在t-1時刻得到的社區(qū)結(jié)構(gòu)基礎(chǔ)上，對新組合的新增列表中的節(jié)點依次進行社區(qū)指派；(4)更新節(jié)點社區(qū)歸屬列表。

4 實驗結(jié)果與分析

為了定量地測試本文提出算法的有效性，分別在真實網(wǎng)絡(luò)數(shù)據(jù)和人工生成數(shù)據(jù)上測試了新給出的FRCD算法與基于模塊度優(yōu)化的BGLL算法以及CNM算法的社區(qū)劃分效率。同時，給出了FRCD算法在不進行網(wǎng)絡(luò)稀疏化時的劃分結(jié)果(記為FRCD*)。在人工網(wǎng)絡(luò)上模擬了當(dāng)網(wǎng)絡(luò)動態(tài)變化時，新給出的動態(tài)社區(qū)劃分方法IDCD和Shang等給出方法的社區(qū)劃分的差異。

由于這兩類數(shù)據(jù)集都已知社區(qū)結(jié)構(gòu)，因此選取了標(biāo)準(zhǔn)化互信息(Normalized mutual information, NMI)[14]以及準(zhǔn)確率[15]作為社區(qū)劃分結(jié)果優(yōu)劣的評價指標(biāo)。其中，NMI的定義為

(5)

4.1 靜態(tài)社區(qū)結(jié)構(gòu)的實驗比較

4.1.1 真實實驗數(shù)據(jù)

在本節(jié)實驗中用到的真實數(shù)據(jù)包括經(jīng)典的美國大學(xué)足球賽網(wǎng)絡(luò)Football[16]，Zachary空手道俱樂部網(wǎng)絡(luò)Karate[17]]以及海豚關(guān)系網(wǎng)絡(luò)Dolphins[18]。除了這3個經(jīng)典實際網(wǎng)絡(luò)，為了測試該算法在不同規(guī)模真實網(wǎng)絡(luò)中的社區(qū)劃分效果，本文還選取其他3個實際網(wǎng)絡(luò)，包括美國政治書籍網(wǎng)絡(luò)Political Books[19]，博客網(wǎng)絡(luò)Blogs[20]以及蛋白質(zhì)交互網(wǎng)絡(luò)PPI[21]，各網(wǎng)絡(luò)相關(guān)屬性如表1所示。

表1 真實網(wǎng)絡(luò)數(shù)據(jù)集

由于本文提出算法是基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)方法，首先將FRCD與BGLL和CNM算法進行實驗比較。Shang等人提出的方法缺乏穩(wěn)定性，導(dǎo)致程序每次運行的結(jié)果不同，因此選擇10次運行結(jié)果中得到Q值最大的結(jié)果進行對比，得到表2～4所示的實驗結(jié)果。

表2 真實網(wǎng)絡(luò)中的NMI對比結(jié)果

表3 真實網(wǎng)絡(luò)中的Accuracy對比結(jié)果

表4 真實網(wǎng)絡(luò)中的Q對比結(jié)果

通過實驗結(jié)果比較可以發(fā)現(xiàn)：(1)FRCD算法在各網(wǎng)絡(luò)中得到的最優(yōu)模塊度值與BGLL大致相同，都具有較高的模塊度；(2)在Karate，Dolphins，Political Books以及blogs網(wǎng)絡(luò)上得到的NMI以及準(zhǔn)確率要優(yōu)于BGLL；(3)網(wǎng)絡(luò)的稀疏化能夠減少社團間的部分連邊，同時會對社團內(nèi)部節(jié)點間的連邊進行稀疏，此時得到的結(jié)果與未稀疏化網(wǎng)絡(luò)相比，會優(yōu)于或者略差于未稀疏化的網(wǎng)絡(luò)。在Karate和Dolphins網(wǎng)絡(luò)上得到的NMI以及在Football網(wǎng)絡(luò)上得到的準(zhǔn)確率明顯優(yōu)于未稀疏化后的網(wǎng)絡(luò)，但是在Political Books網(wǎng)絡(luò)上效果略差，因此稀疏化的程度會對算法的準(zhǔn)確性產(chǎn)生一定的影響。FRCD算法能夠較準(zhǔn)確地發(fā)現(xiàn)網(wǎng)絡(luò)中蘊含的社區(qū)結(jié)構(gòu)。

4.1.2 人工網(wǎng)絡(luò)數(shù)據(jù)

為進一步實驗驗證本文算法的效果，本文選用Lancichinetti等提出的LFR人工網(wǎng)絡(luò)[22]進行比對，表5給出了生成的4個LFR人工網(wǎng)絡(luò)的參數(shù)設(shè)置。

表5中，N表示生成的網(wǎng)絡(luò)中節(jié)點的個數(shù)；MU是網(wǎng)絡(luò)的混合參數(shù)，表示與社區(qū)內(nèi)節(jié)點關(guān)聯(lián)的邊中處于社區(qū)之間邊的比例，該值越小表明生成的網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越清晰，取值為0.1到0.9；k表示網(wǎng)絡(luò)的平均度；kmax表示網(wǎng)絡(luò)中節(jié)點的最大度；minc表示網(wǎng)絡(luò)中最小社區(qū)中節(jié)點個數(shù)；maxc表示網(wǎng)絡(luò)中最大社區(qū)中節(jié)點的個數(shù)；t1為度分布的負(fù)指數(shù)值；t2為網(wǎng)絡(luò)中社區(qū)規(guī)模分布的負(fù)指數(shù)值。通過與BGLL和CNM進行比較，得到圖1～4的實驗結(jié)果。

表5 LFR人工網(wǎng)絡(luò)中的參數(shù)

圖1 LFR1上的實驗比較Fig.1 Experimental results on LFR1

圖2 LFR2上的實驗比較Fig.2 Experimental results on LFR2

圖3 LFR3上的實驗比較Fig.3 Experimental results on LFR3

圖4 LFR4上的實驗比較Fig.4 Experimental results on LFR4

通過在人工生成網(wǎng)絡(luò)上的實驗比較可知，當(dāng)網(wǎng)絡(luò)混合參數(shù)取不同值時，F(xiàn)RCD算法大部分情況優(yōu)于BGLL和CNM，尤其是MU=0.1～0.4時能得到完全準(zhǔn)確劃分。但是當(dāng)MU=0.7時，此時網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)不夠清晰，效果不如BGLL。整體的實驗結(jié)果可知FRCD在靜態(tài)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)中，能得到較準(zhǔn)確的社區(qū)結(jié)構(gòu)。

4.2 動態(tài)網(wǎng)絡(luò)的實驗比較

由于現(xiàn)實中的社會網(wǎng)絡(luò)結(jié)構(gòu)變化都很緩慢，相鄰采樣時刻之間網(wǎng)絡(luò)變化很小，因此通過對人工網(wǎng)絡(luò)隨機抽取的方法，模擬增加的網(wǎng)絡(luò)。具體生成方法如下。

輸入：含有n個節(jié)點的網(wǎng)絡(luò)G0，增量網(wǎng)絡(luò)個數(shù)N。

輸出：初始靜態(tài)網(wǎng)絡(luò)，以及后續(xù)的增量網(wǎng)絡(luò)G1,…,GN，其中Gr為第r個增量網(wǎng)絡(luò)，初始r=1。

在實驗中，設(shè)β1=0.01，β2=0.005，N=10。分別在LFR1和LFR3中，當(dāng)mu=0.3時，和Shang等人提出的方法進行實驗比較，由于Shang方法具有隨機性，因此采用10次實驗結(jié)果的平均值和提出的IDCD算法進行比較，橫坐標(biāo)為增加各子集個數(shù)，實驗結(jié)果如圖5，6所示。

圖5 LFR1上動態(tài)社區(qū)結(jié)果Fig.5 Dynamic community detection results on LFR1

圖6 LFR3上動態(tài)社區(qū)結(jié)果Fig.6 Dynamic community detection results on LFR3

通過與Shang等提出的方法進行比較，可以看到：隨著時間的推移，增量式的動態(tài)社區(qū)發(fā)現(xiàn)方法由于存在錯誤率累積的問題，得到的結(jié)果整體呈現(xiàn)變差趨勢；本文提出的IDCD方法在起初階段效果略差于BGLL，但是隨著網(wǎng)絡(luò)規(guī)模的增大，得到的效果逐漸優(yōu)于Shang等人的方法，從而說明本文算法在處理動態(tài)網(wǎng)絡(luò)時的有效性。

5 結(jié)束語

本文提出了一種新的基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)方法，該方法不僅能夠發(fā)現(xiàn)靜態(tài)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，而且可以對動態(tài)增加的網(wǎng)絡(luò)進行實時的社區(qū)結(jié)構(gòu)追蹤。通過在實際網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)中與基于模塊度最大化的BGLL和CNM算法進行比較，表明本文提出的靜態(tài)社區(qū)發(fā)現(xiàn)方法FRCD具有較高的劃分準(zhǔn)確率。進一步通過在動態(tài)網(wǎng)絡(luò)中與Shang等人的方法進行實驗對比，說明IDCD算法能夠有效追蹤網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的變化，對Shang方法存在的問題進行了有效改進。另外，本文所給出的算法是一種基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)方法，可以用于優(yōu)化其他的目標(biāo)函數(shù)，如模塊度密度[23]、Surprise[24]等。但本文中的算法在進行動態(tài)網(wǎng)絡(luò)追蹤時，只考慮了網(wǎng)絡(luò)規(guī)模不斷增大的情形。雖然，這在一定程度上符合實際網(wǎng)絡(luò)規(guī)模的變化，但是在現(xiàn)實世界中也存在部分節(jié)點和邊在下一個時刻消失的情況。目前，這在動態(tài)網(wǎng)絡(luò)研究中仍是一個研究難點，也是未來要探索解決的問題之一。

[1] Girvan M, Newman M E J. Community structure in social and biological networks[J]. PNAS, 2002,9(12):7821-7826.

[2] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008.

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

[4] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007,76(3):036106.

[5] Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008,105(4):1118-1123.

[6] Tang L, Liu H, Zhang J, et al. Community evolution in dynamic multi-mode networks[C]∥Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2008:677-685.

[7] 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.

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

Shan Bo, Jiang Shouxu, Zhang Shuo, et al. IC: Incremental algorithm for community identification in dynamic social networks[J]. Journal of Software, 2009,20:184-192.

[9] 周耀明,李弼程.一種自適應(yīng)網(wǎng)絡(luò)輿情演化建模方法[J].數(shù)據(jù)采集與處理,2013，28(1):69-76.

Zhou Yaoming, Li Bicheng. Adaptive evolution modeling method of internet public opinions[J]. Journal of Data Acquisition and Processing, 2013，28(1):69-76.

[10]Shang J, Liu L, Xie F, et al. A real-time detecting algorithm for tracking community structure of dynamic networks[C]∥The 6th SNA-KDD Workshop. New York, USA: ACM, 2012.

[11]Park J, Newman M E J. The origin of degree correlations in the Internet and other network[J]. Phys Rev E, 2003,68(2):026112.

[12]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):P10011.

[13]Satuluri V, Parthasarathy S, Ruan Y. Local graph sparsification for scalable clustering[C]∥Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. NewYork, NY, USA: ACM, 2011:721-732.

[14]Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004,101(9):2658-2663.

[15]Danon L, Diaz-Guilera A, Duch J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005(9):P09008.

[16]Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002,99(12):7821-7826.

[17]Zachary W. An information flow model for conflict and fission in small groups1[J]. Journal of Anthropological Research, 1977,33(4):452-473.

[18]Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003,54(4):396-405.

[19]Newman M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006,103(23):8577-8582.

[20]Adamic L A, Glance N. The political blogosphere and the 2004 US election: Divided they blog[C]∥Proceedings of the 3rd International Workshop on Link Discovery. NewYork, NY, USA: ACM, 2005:36-43.

[21]Vlasblom J, Wodak S J. Markov clustering versus affinity propagation for the partitioning of protein interaction graphs[J]. BMC Bioinformatics, 2009,10(1):99.

[22]Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008,78(4):046110.

[23]Li Z, Zhang S, Wang R S, et al. Quantitative function for community detection[J]. Physical Review E, 2008,77(3):036109.

[24]Aldecoa R, Marín I. Deciphering network community structure by surprise[J]. PLoS One, 2011,6(9):e24195.

Novel Community/Dynamic Community Optimization Algorithm

Li Yafang1,2， Jia Caiyan1,2， Yu Jian1,2, Liu Guangming1,2

(1.School of Computer and Information Technology, Beijing Jiaotong University, Beijing, 100044, China; 2.Beijing Key Lab of Traffic Data Analysis and Mining, Beijing, 100044, China)

Community structure is one of the most important topological characteristics in the complex network, being a hot research area in different fields. A novel community detection algorithm is proposed based on edges rank and modularity optimization. Local graph is sparsificated and edges are ranked according to the similarity. Therefore, a method called the fast rank-based community detection (FRCD) by maximizing modularity and fast mergement of edges is achieved. Meanwhile the method is also extended to dynamic and real-time community detection on the basis of initial community structure, and a fast and robust dynamic community detection algorithm called the incremental dynamic community detection (IDCD) is presented. Theoretical analysis exhibit that FRCD has linear complexity for network edges. Experimental results in real-world and artificial networks demonstrate the high accuracy and good performance of the algorithm on static community detection and tracking dynamic structure of networks.

community detection; modularity; rank; dynamic characteristic

國家自然科學(xué)基金(61473030,61370129)資助項目;北京市自然科學(xué)基金(4112046)資助項目;北京市科委(Z131110002813118)資助項目;中央高?；究蒲袠I(yè)務(wù)費專項基金(K15JB00070,2014JBM031)資助項目;北大方正集團有限公司數(shù)字出版技術(shù)國家重點實驗室開放課題資助項目。

2014-03-25；

2014-10-23

TP181

A

李亞芳(1988-), 女,博士研究生,研究方向：數(shù)據(jù)挖掘,復(fù)雜網(wǎng)絡(luò)分析,E-mail:cyjia@bjtu.edu.cn。

賈彩燕(1976-), 女,副教授，研究方向：數(shù)據(jù)挖掘、生物信息學(xué)以及復(fù)雜網(wǎng)絡(luò)分析等。

于劍(1969-), 男,教授，博士生導(dǎo)師,研究方向：機器學(xué)習(xí)、數(shù)據(jù)挖掘以及圖像分割等。

劉光明(1987-),男,博士研究生,研究方向：數(shù)據(jù)挖掘。