王宏杰，滕 飛+，李天瑞

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

2.四川省云計(jì)算與智能技術(shù)高校重點(diǎn)實(shí)驗(yàn)室，成都 611756

模塊度引導(dǎo)下的社區(qū)發(fā)現(xiàn)增量學(xué)習(xí)算法*

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

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

2.四川省云計(jì)算與智能技術(shù)高校重點(diǎn)實(shí)驗(yàn)室，成都 611756

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

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

1 引言

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

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

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

2 相關(guān)工作

2.1 模塊度

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

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

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

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

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

2.2 FastUnfolding算法

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

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

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

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

3 基于模塊度的增量式擴(kuò)展算法

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

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

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

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

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

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

3.1 邊變化

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

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

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

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

當(dāng)社區(qū)內(nèi)部減少邊或社區(qū)之間增加邊時(shí)社區(qū)結(jié)構(gòu)變得松散，如圖3、圖4。由于邊連接節(jié)點(diǎn)為社區(qū)邊界節(jié)點(diǎn)，假設(shè)這些節(jié)點(diǎn)會(huì)發(fā)生社區(qū)歸屬變化，根據(jù)“模塊度最大化”原則，將這些點(diǎn)分別改變社區(qū)后的模塊度與保持在原有社區(qū)的模塊度進(jìn)行比較，比較結(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，總點(diǎn)數(shù)n，鄰接矩陣A={aij}，增加邊數(shù)據(jù)集Inc_Data={(ni,nj)}，考量節(jié)點(diǎn)為 p，Cneigh為p相鄰社區(qū)。

3.2 點(diǎn)變化

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

Fig.5 Increase of single vertex圖5 社區(qū)增加單個(gè)點(diǎn)

算法2單個(gè)點(diǎn)變化處理算法

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

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

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

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

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

算法3批量點(diǎn)變化處理算法

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

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

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

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

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

4.1.1 邊變化

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

Table 1 Experiment of link changes(Increase)表1 邊變化實(shí)驗(yàn)（增加邊）

Table 2 Experiment of link changes(Decrease)表2 邊變化實(shí)驗(yàn)（刪除邊）

4.1.2 點(diǎn)變化

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

Table 3 Experiment of vertex changes表3 點(diǎn)變化實(shí)驗(yàn)

4.1.3 綜合變化

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

Fig.9 Contrast between time costs of synthetical changes圖9 綜合變化時(shí)間對(duì)比

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

Table 4 Experiment of synthetical changes表4 綜合變化實(shí)驗(yàn)

4.2 實(shí)驗(yàn)總結(jié)

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

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

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

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

附中文參考文獻(xiàn)：

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

[21]王莉,程學(xué)旗.在線社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)及演化[J].計(jì)算機(jī)學(xué)報(bào),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—），男，西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院軟件工程系碩士研究生，主要研究領(lǐng)域?yàn)樵朴?jì)算，社區(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年于法國(guó)巴黎中央理工大學(xué)獲得計(jì)算機(jī)科學(xué)博士學(xué)位，現(xiàn)為西南交通大學(xué)講師，主要研究領(lǐng)域?yàn)樵朴?jì)算，分布式調(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年于西南交通大學(xué)獲得博士學(xué)位，現(xiàn)為西南交通大學(xué)軟件工程系主任、教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)樵朴?jì)算，數(shù)據(jù)挖掘，人工智能等。發(fā)表學(xué)術(shù)論文150余篇，主持過多項(xiàng)國(guó)家科學(xué)基金。

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(國(guó)家自然科學(xué)基金).

Received 2016-02,Accepted 2016-04.

CNKI網(wǎng)絡(luò)優(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.