王宏杰，滕 飛+，李天瑞

1.西南交通大學 信息科學與技術(shù)學院，成都 611756

2.四川省云計算與智能技術(shù)高校重點實驗室，成都 611756

模塊度引導下的社區(qū)發(fā)現(xiàn)增量學習算法*

王宏杰1,2，滕 飛1,2+，李天瑞1,2

1.西南交通大學 信息科學與技術(shù)學院，成都 611756

2.四川省云計算與智能技術(shù)高校重點實驗室，成都 611756

當前社區(qū)發(fā)現(xiàn)領域存在諸多靜態(tài)社區(qū)劃分算法，而其劃分結(jié)果的不穩(wěn)定性和較高的算法復雜度已經(jīng)不能適應如今規(guī)模龐大，變化頻繁的網(wǎng)絡結(jié)構(gòu)。為解決傳統(tǒng)靜態(tài)算法這一局限性，提出了一種利用模塊度優(yōu)化的增量學習算法，將網(wǎng)絡結(jié)構(gòu)的變化劃分成邊變化、點變化兩種基本操作，在對“模塊度最大化”的規(guī)則指導下實現(xiàn)網(wǎng)絡結(jié)構(gòu)的增量學習。實驗表明，該算法在保證原有社區(qū)劃分結(jié)果的前提下，可以將新變化的節(jié)點快速劃分進已有社區(qū)，并使得模塊度與靜態(tài)算法重新計算模塊度相近，節(jié)省了時間，保持了社區(qū)劃分的實時性。

社區(qū)劃分；增量學習；模塊度

1 引言

近年來，隨著Web應用的推廣，對于其中包含的復雜網(wǎng)絡結(jié)構(gòu)也逐漸成為研究熱點[1]。作為復雜網(wǎng)絡結(jié)構(gòu)的3個主要特征之一[2-4]，社區(qū)結(jié)構(gòu)發(fā)現(xiàn)成為最受關注的研究方向，已在生物學、社會學和信息網(wǎng)絡等領域得到了廣泛應用。最早對于社區(qū)結(jié)構(gòu)劃分結(jié)果，人們往往以“內(nèi)聚性強，外聯(lián)性弱”等籠統(tǒng)直觀感覺進行判斷[5]，對社區(qū)劃分結(jié)果并無統(tǒng)一評價標準。直到2004年，Newman提出了“模塊度[6-9]”的概念，旨在將社區(qū)劃分結(jié)果量化以便橫向比較，人們才找到了一條社區(qū)劃分的新途徑。在模塊度指導下，傳統(tǒng)的社區(qū)劃分問題被轉(zhuǎn)化成單目標優(yōu)化問題[10]，之后有不少領域內(nèi)的研究者提出關于模塊度的社區(qū)發(fā)現(xiàn)算法，例如Newman提出的基于模塊度的簇聚類FN[11]方法，Blondel和Guillaume提出的FastUnfolding[12]方法，這些方法均達到了十分理想的分類效果。基于模塊度的各類研究方興未艾，然而隨著現(xiàn)實中的網(wǎng)絡結(jié)構(gòu)越來越復雜，傳統(tǒng)靜態(tài)社區(qū)劃分算法逐漸暴露出兩方面的缺陷：一是劃分效率低。FN算法復雜度達到O((m+n)n)，而FastUnfolding算法復雜度也達到O(kmn)，如果被應用到大規(guī)模網(wǎng)絡結(jié)構(gòu)中，很難保證社區(qū)劃分的實時性。二是劃分成本高。由于基于模塊度的社區(qū)劃分算法本質(zhì)上屬于優(yōu)化算法，而優(yōu)化算法的隨機性使得每次算法執(zhí)行之后的劃分結(jié)果不一致，并且當前實時場景中的圖結(jié)構(gòu)變化越來越趨于局部性和碎片化[13-14]。例如社交網(wǎng)絡中的好友關系[15-17]，每個人的朋友關系網(wǎng)一旦形成則很難發(fā)生大規(guī)模改變，而局部小圈子里好友增加，好友之間添加，刪除聯(lián)系的互動卻是時常發(fā)生，此時若利用靜態(tài)算法對社區(qū)重新劃分則可能會對原有社區(qū)劃分結(jié)果造成重大破壞，所有在原有劃分結(jié)果上的研究與應用系統(tǒng)也會受到影響。因此未來研究的新趨勢之一將會是網(wǎng)絡結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)增量學習算法[18]。

本文在“模塊度最大化”的劃分指導原則下，提出一種新的社區(qū)發(fā)現(xiàn)增量學習算法。其核心思想是將社區(qū)的變化總結(jié)成4種常見基本操作，并與模塊度相結(jié)合，針對每種變化設計了相應的增量學習過程。通過實驗證明，這種基于模塊度的增量學習算法有能力處理大規(guī)模社區(qū)數(shù)據(jù)，既能節(jié)省重新運用靜態(tài)算法劃分社區(qū)的時間，又能在不破壞大部分節(jié)點原有社區(qū)的基礎上，使得新增節(jié)點的劃分達到和靜態(tài)算法相近的效果。

本文組織結(jié)構(gòu)如下：第2章為相關工作；第3章介紹增量算法的具體實現(xiàn)流程；第4章給出了實驗方案和實驗結(jié)果；第5章為結(jié)束語。

2 相關工作

2.1 模塊度

2002年Girvan和Newman聯(lián)合提出了GN算法[19]。該算法每個執(zhí)行流程都找到一條具有最大邊介數(shù)的邊，刪除該條邊后原圖傾向于分成兩個獨立的聯(lián)系不緊密的子網(wǎng)絡，執(zhí)行若干次該過程直到每個節(jié)點就是一個退化網(wǎng)絡。這個過程中存在社區(qū)結(jié)構(gòu)沒有量化的缺陷，刪除操作要到哪一步停止需要引入變量指導等問題。之后模塊度被提出，作為網(wǎng)絡結(jié)構(gòu)中的一個性質(zhì)，它能衡量一個圖的劃分是否合理[20-22]。目前模塊度已成為社區(qū)劃分領域一個非常重要的社區(qū)評價指標。對于一個社區(qū)而言，最理想的劃分結(jié)果應是社區(qū)內(nèi)部連接緊密，社區(qū)之間連接稀疏。當社區(qū)i≠j，用eij表示連接i、j兩個社區(qū)的邊數(shù)所占圖中總邊數(shù)比例的一半；當社區(qū)i=j，用eij表示社區(qū)i內(nèi)部邊所占圖中總邊數(shù)的比例。對于ai：

其中，C表示社區(qū)集合，則有模塊度Q的表達式：

為了計算方便，現(xiàn)將式（2）變形：

其中，m是邊總數(shù)；Ii是社區(qū)內(nèi)部總邊數(shù)；Di是社區(qū)內(nèi)部節(jié)點總度數(shù)。

模塊度所指代的實際物理含義指網(wǎng)絡中連接社區(qū)結(jié)構(gòu)內(nèi)部頂點的邊所占的比例與另一個隨機網(wǎng)絡中連接社區(qū)內(nèi)部頂點的邊所占比例的期望值相減得到的差值。這種差值越大，表明該劃分下網(wǎng)絡結(jié)構(gòu)越優(yōu)于隨機劃分，所得結(jié)果更有參考價值，更符合圖社區(qū)要求。模塊度介于0到1之間，劃分結(jié)果大于0.4可以視為劃分有意義。模塊度是本文提出的增量算法的劃分依據(jù)。

2.2 FastUnfolding算法

FastUnfolding算法是基于模塊度的重要優(yōu)化算法。設G為社會網(wǎng)絡抽象出的圖結(jié)構(gòu)，V為G中點集，F(xiàn)astUnfolding算法提供一種劃分方案將V劃分為N個社區(qū){C1,C2,…,Cn}，每個子集對應一個社區(qū)，最后使得圖中。為使Q值最大，F(xiàn)astUnfolding算法將社區(qū)劃分問題分層處理：第一層是原始圖結(jié)構(gòu)，之后每一層都是上一層找到最大Q值劃分后合并相同社區(qū)節(jié)點產(chǎn)生的新圖。在每層中，初始每個點都作為單獨社區(qū)，之后對于每個點都考慮將其依次劃分到與相鄰點社區(qū)中所得到的Q值增益。Q值增益計算公式如下：

其中，ki,in是連接節(jié)點到目的社區(qū)中所有點的權(quán)重；ki是節(jié)點i的度數(shù)；Ic是社區(qū)內(nèi)部邊數(shù)；Dc是社區(qū)內(nèi)部點總度數(shù)；m是圖中總邊數(shù)。在找到增益最大的鄰居節(jié)點后，把歸屬社區(qū)改為鄰居節(jié)點社區(qū)。把對圖中所有節(jié)點完成劃分操作當成一個階段，迭代該階段執(zhí)行過程，直到?jīng)]有一種新的劃分會對圖造成正向ΔQ，即完成一層的操作。圖1為FastUnfolding算法流程實例圖，每一層都要分為Q值優(yōu)化和社區(qū)合并兩個流程。

Fig.1 Procedure of FastUnfolding圖1 FastUnfolding算法流程

該算法復雜度為O(kmn)，其中m為邊數(shù)，n為點數(shù)，k為圖劃分的層級。FastUnfolding算法對于靜態(tài)圖有著很好的處理效果，時間耗費也隨著層級的累積呈幾何式下降，是目前算法復雜度最低的社區(qū)發(fā)現(xiàn)算法。但是FastUnfolding算法的缺陷在于由于每一層中的點歸屬劃分操作次序隨機，導致針對一個圖進行多次劃分后劃分結(jié)果均不一致。實驗表明，當圖結(jié)構(gòu)越復雜，點邊數(shù)越多，劃分結(jié)果差別越大。如此性質(zhì)導致算法只能用于社區(qū)劃分的一次性靜態(tài)批量處理，而對于圖的結(jié)構(gòu)變化頻繁的增量社區(qū)環(huán)境中，F(xiàn)astUnfolding為代表的基于Q值的社區(qū)劃分算法便不適用，否則僅由于小部分局部變化的節(jié)點便對圖結(jié)構(gòu)進行重新劃分，導致原有社區(qū)劃分遭受破壞。因而本文提出一種只針對局部變化節(jié)點處理的增量式擴展算法，能有效地解決這個問題。

3 基于模塊度的增量式擴展算法

當圖結(jié)構(gòu)發(fā)生變化時，增量式算法保證原圖大部分節(jié)點從屬社區(qū)不變，利用現(xiàn)有社區(qū)作為劃分依據(jù)，從而只對變化部分涉及的節(jié)點進行重新劃分。針對基于模塊度劃分的社區(qū)，包含以下已知信息：

（1）社區(qū)數(shù)目w以及社區(qū)集合C={C1,C2,…,Cw}；

（2）社區(qū)內(nèi)部總邊數(shù)集合I={Ic1,Ic2,…,Icw}；

（3）社區(qū)的節(jié)點總度數(shù)D={Dc1,Dc2,…,Dcw}；

（4）圖的總邊數(shù)m，總節(jié)點數(shù)n。

根據(jù)式（3）可得各個社區(qū)的Q值。在上述信息基礎上，將社區(qū)變化劃分為兩類：一類是點的變化；一類是邊的變化。當點變化時，該點的鄰居點度數(shù)發(fā)生變化，I值、D值變化；當邊變化時，該邊連接兩個點的度數(shù)發(fā)生變化，I值、D值變化。因此無論哪類變化，社區(qū)Q值總會發(fā)生改變。不同的是有的變化需要對某些點重新劃分社區(qū)，有的變化則不需要。

3.1 邊變化

（1）社區(qū)之間減少邊或社區(qū)內(nèi)部增加邊

如圖2，社區(qū)之間連邊減少，社區(qū)內(nèi)部連邊增加（黑色虛線表示刪除，藍色虛線表示增加，圖3類似表示），此種情況處理方法較為簡單。由于社區(qū)劃分目的是達到社區(qū)之間聯(lián)系松散的狀態(tài)，故此類變化對已有社區(qū)劃分結(jié)果起正向鞏固作用，不會影響劃分結(jié)果，只需在更新m、I、D值后即可通過式（3）重新計算Q值。

Fig.2 Decrease of links between communities and increase of links inside communities圖2 社區(qū)之間邊減少和社區(qū)內(nèi)部邊增加

（2）社區(qū)之間增加邊或社區(qū)內(nèi)部減少邊

當社區(qū)內(nèi)部減少邊或社區(qū)之間增加邊時社區(qū)結(jié)構(gòu)變得松散，如圖3、圖4。由于邊連接節(jié)點為社區(qū)邊界節(jié)點，假設這些節(jié)點會發(fā)生社區(qū)歸屬變化，根據(jù)“模塊度最大化”原則，將這些點分別改變社區(qū)后的模塊度與保持在原有社區(qū)的模塊度進行比較，比較結(jié)果作為改變依據(jù)，若Q值有增大則改變社區(qū)，若Q值減少則保持原有社區(qū)不變。

Fig.3 Increase of links between communities圖3 社區(qū)之間增加邊

Fig.4 Decrease of links inside communities圖4 社區(qū)內(nèi)部減少邊

算法1邊變化處理算法

已知社區(qū)數(shù)目w，社區(qū)集合C，社區(qū)內(nèi)部總邊數(shù)集合I，社區(qū)內(nèi)部總度數(shù)集合D，圖的總邊數(shù)m，總點數(shù)n，鄰接矩陣A={aij}，增加邊數(shù)據(jù)集Inc_Data={(ni,nj)}，考量節(jié)點為 p，Cneigh為p相鄰社區(qū)。

3.2 點變化

刪除點可以看作刪除了跟一個點相關的所有邊，本質(zhì)上還是屬于在社區(qū)中刪除邊，故具體方法可以參照3.1節(jié)中介紹。此節(jié)著重強調(diào)增加點這種情形。如圖5，若增加點p與原圖中t個社區(qū)有連接，則增量算法要求p依次加入到t個社區(qū)中，再分別計算加入后的模塊度與原社區(qū)模塊度的差值作為Q值增量，之后將p加入到Q值增量最大的社區(qū)中。

Fig.5 Increase of single vertex圖5 社區(qū)增加單個點

算法2單個點變化處理算法

已知社區(qū)數(shù)目w，社區(qū)集合C，社區(qū)內(nèi)部總邊數(shù)集合I，社區(qū)內(nèi)部總度數(shù)集合D，圖的總邊數(shù)m，總點數(shù)n，鄰接矩陣A={aij}，增加邊數(shù)據(jù)集Inc_Data={(ni,nj)}，考量節(jié)點為 p，Cneigh為p相鄰社區(qū)。

若一次增加多個節(jié)點，如圖6所示，可將新增點分為兩類：一類節(jié)點與原社區(qū)有連接；二類節(jié)點沒有連接。在處理此類問題時，需要先將所有與原社區(qū)有連接的點，運用上述增加點的方法加入到已有社團中，并更新原有社區(qū)的社團結(jié)構(gòu)，更新之后的結(jié)果如圖7和圖8。

Fig.6 Increase of a group of vertexes圖6 社區(qū)增加多個點

Fig.7 Communities of Class I vertexes detected圖7 一類節(jié)點劃分完成

Fig.8 Communities of Class II vertexes detected圖8 二類節(jié)點劃分完成

算法3批量點變化處理算法

已知社區(qū)數(shù)目w，社區(qū)集合C，社區(qū)內(nèi)部總邊數(shù)集合I，社區(qū)內(nèi)部總度數(shù)集合D，圖的總邊數(shù)m，總點數(shù)n，鄰接矩陣A={aij}，增加邊數(shù)據(jù)集Inc_Data={(ni,nj)}，考量節(jié)點為p，Cneigh為 p相鄰社區(qū)。

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

本文的實驗部分首先針對邊變化和點變化分別進行增量式算法的驗證，再將點變化和邊變化匯總驗證，驗證的方向主要包括增量式算法和靜態(tài)算法在時間和效果上的比較。首先用靜態(tài)算法得到劃分結(jié)果，之后為了保證原圖的結(jié)構(gòu)不發(fā)生大的變化，從原圖抽出數(shù)據(jù)作為增量數(shù)據(jù)集，運行增量算法再與靜態(tài)算法的劃分結(jié)果比較，由此得到的結(jié)果可以較客觀地反映增量算法的運行效果。

4.1 Facebook交友數(shù)據(jù)集

Facebook數(shù)據(jù)集包括4 039個點，88 234條邊。在用FastUnfolding算法作出劃分后，可得到14個社區(qū)，模塊度為0.835。

4.1.1 邊變化

表1、表2分別記錄了在Facebook數(shù)據(jù)集中，增加社區(qū)之間邊和刪除社區(qū)內(nèi)部邊時，運用增量學習方法得到的劃分結(jié)果。表中可以對比看到靜態(tài)算法重新劃分時間和效果。

Table 1 Experiment of link changes(Increase)表1 邊變化實驗（增加邊）

Table 2 Experiment of link changes(Decrease)表2 邊變化實驗（刪除邊）

4.1.2 點變化

表3記錄了在隨機抽取了1%～5%的節(jié)點后，將其作為增量數(shù)據(jù)點，加回到剩余圖構(gòu)成的社區(qū)中得到的增量算法的運行時間和結(jié)果，并與初始完整數(shù)據(jù)集靜態(tài)算法的時間與結(jié)果進行比較。

Table 3 Experiment of vertex changes表3 點變化實驗

4.1.3 綜合變化

綜合變化將點變化以及邊變化匯總，在從原圖抽取點再加回到剩余圖這個過程中另加上邊的變化，包括增加邊、刪除邊。圖9、圖10顯示了綜合變化中，增量算法與靜態(tài)算法的時間對比以及Q值誤差的變化趨勢。表4記錄了Facebook數(shù)據(jù)集綜合變化實驗結(jié)果。

Fig.9 Contrast between time costs of synthetical changes圖9 綜合變化時間對比

Fig.10 Contrast between error of synthetical changes圖10 綜合變化誤差對比

Table 4 Experiment of synthetical changes表4 綜合變化實驗

4.2 實驗總結(jié)

通過Facebook數(shù)據(jù)集的實驗可以說明增量算法的運行效果良好，算法依照的“模塊度最大”原則能保證增量算法的劃分方案可以達到與靜態(tài)算法相近的效果，誤差在5%之內(nèi)；而在時間方面，增量算法耗時相較于靜態(tài)算法也有3～4倍的減小。因而本文的增量算法既能滿足提高劃分效率要求，又能在不破壞原有社區(qū)劃分的基礎上使得增量點獲得最好的劃分歸屬，保證模塊度最大，達到算法優(yōu)化的目的。

5 結(jié)束語

為應對網(wǎng)絡規(guī)模日益龐大的背景下傳統(tǒng)靜態(tài)社區(qū)劃分算法不能很好地處理頻繁小規(guī)模社區(qū)變化的社區(qū)歸屬問題，本文基于模塊度的概念提出了一套處理社區(qū)4種基本變化的增量學習算法，在“模塊度最大化”原則的指導下，變化節(jié)點劃分進對整體網(wǎng)絡模塊度提升最大的社區(qū)里。實驗證明，這種方法可以很好地應對較大規(guī)模數(shù)據(jù)集近1%～7%的動態(tài)變化，既提升了劃分效率，又能保證模塊度相差在可接受范圍。然而本文算法尚存在一些不足，算法的學習過程是建立在社區(qū)數(shù)目不變的前提下，而實際情況中若社區(qū)的擴張達到一定規(guī)模，社區(qū)數(shù)量亦有可能隨之變化。因此下一步的工作重點主要討論在社區(qū)規(guī)模的持續(xù)增量而引起社區(qū)數(shù)量變化時如何設計合理有效的增量算法。

[1]Watts D J,Strogatz S H.Collective dynamics of“smallworld”networks[J].Nature,1998,393(6684):440-442.

[2]Newman M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.

[3]Bader D,Madduri K.SNAP,small-world network analysis and partitioning:an open-source parallel graph framework for the exploration of large-scale networks[C]//Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing,Miami,USA,Apr 14-18,2008.Piscataway,USA:IEEE,2008:1-12.

[4]Rosvall M,Bergstrom C T.An information-theoretic framework for resolving community structure in complex networks[J].Proceedings of the National Academy of Sciences of the United States ofAmerica,2007,104(18):7327-7331.

[5]Danon L,Díaz-Guilera A,Duch J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics: Theory and Experiment,2005,9:P09008.

[6]Clauset A,Newman M E,Moore C.Finding community structure in very large networks[J].Physical Review E, 2004,70(6):066111.

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

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

[9]Duch J,Arenas A.Community detection in complex networks using extremal optimization[J].Physical Review E,2005, 72(2):027104.

[10]Li Zhenping,Zhang Shihua,Wang Ruisheng,et al.Quantitative function for community detection[J].Physical Review E,2008,77(3):036109.

[11]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6): 066133.

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

[13]Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[14]Bu Zhan,Zhang Chengcui,Xia Zhengyou,et al.A fast parallel modularity optimization algorithm(FPMQA)for community detection in online social network[J].Knowledge-Based Systems,2013,50:246-259.

[15]Gong Maoguo,Zhang Lingjun,Ma Jingjing,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.

[16]Ahn Y Y,Bagrow J P,Lehmann S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466 (7307):761-764.

[17]Yang J,Leskovec J.Defining and evaluating network communities based on ground-truth[J].Knowledge and Information Systems,2015,42(1):181-213.

[18]Polikar R,Upda L,Upda S S,et al.Learn++:an incremental learning algorithm for supervised neural networks[J].IEEE Transactions on Systems,Man,and Cybernetics:Part C Applications and Reviews,2001,31(4):497-508.

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

[20]Lin Youfang,Wang Tianyu,Tang Rui,et al.An effective model and algorithm for community detection in social networks[J].Journal of Computer Research and Development, 2012,49(2):337-345.

[21]Wang Li,Cheng Xueqi.Dynamic community in online social networks[J].Chinese Journal of Computers,2015,38 (2):219-237.

[22]Pinney J W,Westhead D R.Betweenness-based decomposition methods for social and biological networks[J].Interdisciplinary Statistics and Bioinformatics,2006:87-90.

附中文參考文獻：

[20]林友芳,王天宇,唐銳,等.一種有效的社會網(wǎng)絡社區(qū)發(fā)現(xiàn)模型和算法[J].計算機研究與發(fā)展，2012,49(2):337-345.

[21]王莉,程學旗.在線社會網(wǎng)絡的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J].計算機學報,2015,38(2):219-237.

WANG Hongjie was born in 1991.He is an M.S.candidate at School of Information Science and Technology, Southwest Jiaotong University.His research interests include cloud computing and community detection,etc.

王宏杰（1991—），男，西南交通大學信息科學與技術(shù)學院軟件工程系碩士研究生，主要研究領域為云計算，社區(qū)發(fā)現(xiàn)等。

TENG Fei was born in 1984.She received the Ph.D.degree from Ecole Centrale Paris in 2011.Now she is a lecturer at Southwest Jiaotong University.Her research interests include cloud computing,distributed deployment and community detection,etc.

滕飛（1984—），女，2011年于法國巴黎中央理工大學獲得計算機科學博士學位，現(xiàn)為西南交通大學講師，主要研究領域為云計算，分布式調(diào)度，社區(qū)發(fā)現(xiàn)等。

LI Tianrui was born in 1969.He received the Ph.D.degree in data mining from Southwest Jiaotong University in 2002.Now he is a professor and Ph.D.supervisor at Southwest Jiaotong University,and the senior member of CCF. His research interests include cloud computing,data mining and artificial intelligence,etc.

李天瑞（1969—），男，福建莆田人，2002年于西南交通大學獲得博士學位，現(xiàn)為西南交通大學軟件工程系主任、教授、博士生導師，CCF高級會員，主要研究領域為云計算，數(shù)據(jù)挖掘，人工智能等。發(fā)表學術(shù)論文150余篇，主持過多項國家科學基金。

Incremental Learning Algorithm of Community Detection under Guidance of Modularity*

WANG Hongjie1,2,TENG Fei1,2+,LI Tianrui1,2
1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China
2.Key Lab of Cloud Computing and Intelligent Technology of Sichuan Province,Chengdu 611756,China
+Corresponding author:E-mail:fteng@swjtu.edu.cn

There are many static algorithms in the community detection fields but very few of them are able to fit into the current network circumstances where network sizes are getting larger and small-scale changes are getting more frequent.To deal with the limitation,this paper proposes an incremental learning algorithm of community detection based on modularity,which takes consideration of two basic kinds of community operations,edge changes and point changes,and the incremental learning process is carried out with guidance of the principle of modularity maximization.Experimental evaluation shows that the incremental learning algorithm is capable of partitioning new timely changed nodes into existed communities rapidly without any devastation to primitive divisions.Meanwhile,the result is proved to get close to that gained by static algorithm thus saving time and keeping real-time.

community detection;incremental learning;modularity

10.3778/j.issn.1673-9418.1603045

A

TP311

*The National Natural Science Foundation of China under Grant No.61573292(國家自然科學基金).

Received 2016-02,Accepted 2016-04.

CNKI網(wǎng)絡優(yōu)先出版:2016-04-19,http://www.cnki.net/kcms/detail/11.5602.TP.20160419.1143.004.html

WANG Hongjie,TENG Fei,LI Tianrui.Incremental learning algorithm of community detection under guidance of modularity.Journal of Frontiers of Computer Science and Technology,2017,11(4)：556-564.