基于粒子松密度的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法

姜 斐,王曉軍,許 斌,亓 晉

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院，江蘇 南京 210003；2.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003)

基于粒子松密度的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法

姜 斐1,王曉軍1,許 斌2,亓 晉2

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院，江蘇 南京 210003；2.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003)

復(fù)雜網(wǎng)絡(luò)的社團(tuán)挖掘算法是近幾年數(shù)據(jù)挖掘領(lǐng)域新興起的一個(gè)熱點(diǎn)課題。傳統(tǒng)的智能優(yōu)化算法雖然在社團(tuán)挖掘方面有較好的效果，但其執(zhí)行效率低，適用范圍窄；而已有的啟發(fā)式算法雖然在社團(tuán)挖掘效率方面的優(yōu)勢比較明顯，但相比于智能優(yōu)化算法，其普適性仍未得到改善。為綜合提高社團(tuán)劃分算法的效率，通過對材料科學(xué)領(lǐng)域的松密度的概念進(jìn)行調(diào)研，結(jié)合復(fù)雜網(wǎng)絡(luò)的特有屬性，提出一種基于節(jié)點(diǎn)松密度的社團(tuán)挖掘算法。實(shí)驗(yàn)結(jié)果表明，相比于其他算法，該算法在時(shí)間和精度上都有較為顯著的優(yōu)勢。

復(fù)雜網(wǎng)絡(luò)；松密度；社團(tuán)；挖掘

0 引 言

復(fù)雜網(wǎng)絡(luò)是對復(fù)雜系統(tǒng)的抽象和描述方式，任何包含大量組成單元(或子系統(tǒng))的復(fù)雜系統(tǒng)，當(dāng)把構(gòu)成單元抽象成節(jié)點(diǎn)、單元之間的相互關(guān)系抽象為邊時(shí)，都可以當(dāng)作復(fù)雜網(wǎng)絡(luò)來研究[1]；復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的一種角度和方法，它關(guān)注系統(tǒng)中個(gè)體相互關(guān)聯(lián)作用的拓?fù)浣Y(jié)構(gòu)，是理解復(fù)雜系統(tǒng)性質(zhì)和功能的基礎(chǔ)[2]。因此，在科學(xué)發(fā)展日趨復(fù)雜化的大背景下，網(wǎng)絡(luò)社團(tuán)挖掘算法的研究對分析復(fù)雜系統(tǒng)中的復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、理解其功能、發(fā)現(xiàn)其隱含模式、預(yù)測其行為具有十分重要的理論意義[3]。

1 網(wǎng)絡(luò)社團(tuán)劃分算法

網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最普遍和最重要的拓?fù)鋵傩灾籟4]，處于相同社團(tuán)內(nèi)的節(jié)點(diǎn)間相互連接密集、處于相異社團(tuán)的節(jié)點(diǎn)間相互連接稀疏；該特點(diǎn)也是對復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)的定義[5]。

幾乎所有的已知的社團(tuán)聚類算法都直接或間接地應(yīng)用了社團(tuán)的這一特點(diǎn)進(jìn)行計(jì)算[6]。在已知的應(yīng)用到此領(lǐng)域的智能優(yōu)化算法中，MODPSO(多目標(biāo)粒子群算法)是效果比較好的一個(gè)，該算法將復(fù)雜網(wǎng)絡(luò)的模塊密度D的概念[7]進(jìn)一步分解為RA和RC并將其作為算法的兩個(gè)優(yōu)化目標(biāo)[8]。

在MODPSO算法的核心的局部搜索部分,根據(jù)某一節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的所占社團(tuán)的比例進(jìn)行該節(jié)點(diǎn)的社團(tuán)歸屬劃分。該算法的實(shí)驗(yàn)結(jié)果表明，局部搜索這一應(yīng)用使得算法的效率有了顯著的提升；從社團(tuán)定義的角度對其進(jìn)行分析不難看出，對于一個(gè)社團(tuán)內(nèi)的某個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)在同一社團(tuán)的比例明顯要大于在不同社團(tuán)的比例；同時(shí)在模塊密度的公式中也可以看到對網(wǎng)絡(luò)社團(tuán)定義的間接應(yīng)用。

(1)

(2)

D=RA-RC

(3)

MODPSO算法通過局部搜索不斷優(yōu)化RA和RC，使得RA不斷增大，RC不斷減小，最終得出網(wǎng)絡(luò)聚類結(jié)果。模塊密度能夠很好地反映網(wǎng)絡(luò)社團(tuán)聚類情況的優(yōu)劣程度，文中算法也會用到這一指標(biāo)對實(shí)驗(yàn)結(jié)果進(jìn)行評測。實(shí)驗(yàn)數(shù)據(jù)顯示，MODPSO算法對于部分網(wǎng)絡(luò)聚類精度高，但該算法也同樣具有智能優(yōu)化算法的普遍缺陷—效率低[9]。

與智能優(yōu)化算法相比，啟發(fā)式算法在效率方面則有較大的優(yōu)勢[10]。啟發(fā)式算法根據(jù)網(wǎng)絡(luò)的節(jié)點(diǎn)與節(jié)點(diǎn)之間的內(nèi)在聯(lián)系(如度、介數(shù)及聚類系數(shù))等，對節(jié)點(diǎn)進(jìn)行聚少成多的社團(tuán)構(gòu)造[11]。不同的網(wǎng)絡(luò)指標(biāo)應(yīng)用到聚類算法中有不同的優(yōu)缺點(diǎn)：基于節(jié)點(diǎn)度的聚類算法，簡單直觀，便于計(jì)算，但忽略了網(wǎng)絡(luò)的整體特性，結(jié)果不夠準(zhǔn)確；基于中介數(shù)的聚類算法按節(jié)點(diǎn)的流量分析節(jié)點(diǎn)的重要性，可以反映網(wǎng)絡(luò)的動態(tài)特性，但算法復(fù)雜度過高，執(zhí)行效率低；基于特征向量的聚類算法考慮到了鄰居節(jié)點(diǎn)的重要性，但僅僅將各個(gè)節(jié)點(diǎn)進(jìn)行簡單的線性疊加，過于簡化實(shí)際情況。

基于數(shù)據(jù)場的復(fù)雜網(wǎng)絡(luò)聚類算法是一種典型的啟發(fā)式聚類算法[12]，在算法中首次將勢場和互信息的概念融合應(yīng)用到復(fù)雜網(wǎng)絡(luò)聚類問題。首先，將節(jié)點(diǎn)的互信息作為衡量節(jié)點(diǎn)重要性的指標(biāo)，根據(jù)節(jié)點(diǎn)互信息的大小劃分出網(wǎng)絡(luò)社團(tuán)的核心節(jié)點(diǎn)；然后，通過計(jì)算每個(gè)非核心節(jié)點(diǎn)與核心節(jié)點(diǎn)的勢值判斷節(jié)點(diǎn)的社團(tuán)歸屬。該算法執(zhí)行效率較高，但其具有一定的局限性，只能對部分網(wǎng)絡(luò)具有較好的聚類結(jié)果。

文中通過對大量網(wǎng)絡(luò)數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)進(jìn)行調(diào)研，提出一種基于度和粒子松密度的粒子社團(tuán)聚類算法；根據(jù)節(jié)點(diǎn)的度數(shù)劃分核心節(jié)點(diǎn)很容易忽略網(wǎng)絡(luò)的整體特性，而網(wǎng)絡(luò)松密度的概念則可以較好地彌補(bǔ)這一缺陷。將節(jié)點(diǎn)按照度大小進(jìn)行降序排列，序列的第一個(gè)節(jié)點(diǎn)選為第一個(gè)粒子社團(tuán)的核心節(jié)點(diǎn)；然后依次計(jì)算每個(gè)節(jié)點(diǎn)與核心節(jié)點(diǎn)的松密度，根據(jù)松密度的大小判斷該節(jié)點(diǎn)是否為新的粒子社團(tuán)的核心節(jié)點(diǎn)。

2 粒子社團(tuán)聚類算法

文中算法將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)形象化為微粒，則根據(jù)網(wǎng)絡(luò)社團(tuán)的定義，連接緊密的微粒聚集在一起形成粒子社團(tuán)。

2.1 粒子松密度

粒子松密度的概念來自于微粒學(xué)中的松密度的定義。在微粒學(xué)中，松密度指的是包括顆粒內(nèi)外孔及顆粒間空隙的松散顆粒堆積體的平均密度。用處于自然堆積狀態(tài)的未經(jīng)振實(shí)的顆粒物料的總質(zhì)量除以堆積物總體積求得，公式如下：

bulk=m/V

(4)

在粒子社團(tuán)運(yùn)算中，用節(jié)點(diǎn)數(shù)代替堆積物質(zhì)量m，節(jié)點(diǎn)之間的連接數(shù)代替堆積物的體積V，則網(wǎng)絡(luò)總體的粒子松密度B為：

(5)

其中，Nnode表示網(wǎng)絡(luò)中總的節(jié)點(diǎn)數(shù)；Nedge表示網(wǎng)絡(luò)中總的邊數(shù)。

任意兩個(gè)節(jié)點(diǎn)的粒子松密度Bij為:

(6)

其中，Aij表示網(wǎng)絡(luò)的鄰接矩陣中i行j列的值；di和dj表示節(jié)點(diǎn)i和j的度；δ(i,j)表示節(jié)點(diǎn)i和j鄰居節(jié)點(diǎn)的重復(fù)個(gè)數(shù)。

2.2 算法流程

考慮到節(jié)點(diǎn)的度值較大的點(diǎn)對網(wǎng)絡(luò)中部分社團(tuán)的劃分的影響比較大，因此文中算法根據(jù)節(jié)點(diǎn)的度值計(jì)算該節(jié)點(diǎn)是否為某一社團(tuán)的核心節(jié)點(diǎn)。首先，設(shè)定度值最大的節(jié)點(diǎn)為第一個(gè)社團(tuán)的核心節(jié)點(diǎn)；然后，按節(jié)點(diǎn)度值的降序次序依次根據(jù)如下條件判斷每個(gè)節(jié)點(diǎn)是否為核心節(jié)點(diǎn):

(7)

若滿足式(7)，則節(jié)點(diǎn)j不是新社團(tuán)的核心節(jié)點(diǎn)，將其加入到核心節(jié)點(diǎn)為i的社團(tuán)中；否則節(jié)點(diǎn)j為新社團(tuán)的核心節(jié)點(diǎn)。式中λ的取值為節(jié)點(diǎn)j對核心節(jié)點(diǎn)i的影響度，根據(jù)實(shí)驗(yàn)數(shù)據(jù)表明，λ的取值與網(wǎng)絡(luò)整體的粒子松密度密切相關(guān)，在實(shí)驗(yàn)分析部分會對其進(jìn)行詳細(xì)描述。

算法的具體執(zhí)行步驟如下：

Step1：對網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行度值的降序排列，得到節(jié)點(diǎn)序列S。

Step2：從序列S取出第一個(gè)節(jié)點(diǎn)作為網(wǎng)絡(luò)中的第一個(gè)社團(tuán)的核心節(jié)點(diǎn)，將該節(jié)點(diǎn)加入到核心節(jié)點(diǎn)序列C中。

Step3：依次取出序列S中的第二個(gè)節(jié)點(diǎn)，根據(jù)式(7)計(jì)算該節(jié)點(diǎn)與序列C中的節(jié)點(diǎn)是否滿足構(gòu)成核心節(jié)點(diǎn)的條件；若滿足則將該節(jié)點(diǎn)加入序列C，若不滿足則將該節(jié)點(diǎn)加入到對應(yīng)的核心節(jié)點(diǎn)所在社團(tuán)。

Step4：重復(fù)Step3，依次遍歷序列S中的所有節(jié)點(diǎn)。

在算法核心步驟Step2和Step3的執(zhí)行過程中分別會對網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行一次遍歷，算法的時(shí)間復(fù)雜度為O(n2)。

3 仿真實(shí)驗(yàn)與分析

文中算法運(yùn)行的硬件環(huán)境為Inter(R)Core(TM)i5-4200UCPU，1.60GHz，4GB內(nèi)存。軟件環(huán)境為微軟Windows8.1操作系統(tǒng)，jdk1.7，Eclipse軟件開發(fā)環(huán)境，采用Java語言進(jìn)行實(shí)現(xiàn)。

實(shí)驗(yàn)數(shù)據(jù)的驗(yàn)證采用國際通用的NormalizedMutualInformation(NMI)指標(biāo)進(jìn)行實(shí)際劃分結(jié)果與文中算法劃分結(jié)果的對比[13]，該指標(biāo)的值表示兩個(gè)向量的相似度，其取值范圍為(0,1)。文中用其作為實(shí)驗(yàn)結(jié)果的社團(tuán)號向量與真實(shí)社團(tuán)號向量的相似度，若NMI=1，則兩向量完全相同；反之則完全不同。在對比過程中輸入兩個(gè)向量A和B，向量的第i位表示第i個(gè)節(jié)點(diǎn)所歸屬的類。

NMI(A,B)的計(jì)算公式如下：

其中，CA(CB)表示向量A(B)中的社團(tuán)個(gè)數(shù)；C為向量A與向量B組成的混合矩陣，Cij表示向量B的第g個(gè)社團(tuán)與向量B的第j個(gè)社團(tuán)所共有的元素個(gè)數(shù)，Ci.(C.j)表示在矩陣C的第i行(j列)中所有元素之和；N為網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)。

文中對人造數(shù)據(jù)集及具有代表性的部分公共數(shù)據(jù)集如海豚網(wǎng)絡(luò)(dolphinnetworks)[14]、書局網(wǎng)絡(luò)(polbooksnetworks)[15]、空手道俱樂部網(wǎng)絡(luò)(karatenetworks)等[16]進(jìn)行了對比測試。通過對實(shí)驗(yàn)結(jié)果的分析證明文中算法相對其他算法而言具有良好的劃分效果和較高的執(zhí)行效率。

3.1 人工網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)分析

人工網(wǎng)絡(luò)數(shù)據(jù)集是由人工生成的嚴(yán)格符合網(wǎng)絡(luò)社團(tuán)定義的網(wǎng)絡(luò)數(shù)據(jù)集，該數(shù)據(jù)集包含50個(gè)節(jié)點(diǎn)、808條邊，該數(shù)據(jù)集的粒子松密度值為0.062。

按照網(wǎng)絡(luò)社團(tuán)劃分的標(biāo)準(zhǔn)，該數(shù)據(jù)集共有5個(gè)社團(tuán)，通過文中算法對其運(yùn)算得出的社團(tuán)聚類結(jié)果與原始聚類結(jié)果相同，該網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 人工數(shù)據(jù)集網(wǎng)絡(luò)拓?fù)鋱D

實(shí)驗(yàn)數(shù)據(jù)的NMI值為1表明文中算法的社團(tuán)聚類結(jié)果與原始結(jié)果相同。實(shí)驗(yàn)分別對λ取值0.1～0.9，這9個(gè)取值中對應(yīng)該結(jié)果的λ的取值為0.1和0.2，其他取值對應(yīng)的NMI值均為0.887。

3.2 海豚網(wǎng)絡(luò)實(shí)驗(yàn)數(shù)據(jù)分析

該數(shù)據(jù)集由Lusseau等在新西蘭對62只寬吻海豚的生活習(xí)性進(jìn)行了長時(shí)間的觀察得出，根據(jù)研究發(fā)現(xiàn)這些海豚的交往呈現(xiàn)出特定的模式，并構(gòu)造了包含有62個(gè)節(jié)點(diǎn)的海豚網(wǎng)絡(luò)。如果某兩只海豚經(jīng)常一起頻繁活動，那么網(wǎng)絡(luò)中相應(yīng)的兩個(gè)節(jié)點(diǎn)之間就會有一條邊存在。該數(shù)據(jù)集含有159條邊，其粒子松密度值為0.39。該數(shù)據(jù)集的實(shí)際社團(tuán)結(jié)構(gòu)有一定主觀因素，共有兩個(gè)社團(tuán)。當(dāng)λ取0.4時(shí)，文中算法對其的聚類結(jié)果與真實(shí)結(jié)果相符。取不同λ對應(yīng)實(shí)驗(yàn)結(jié)果的最優(yōu)解比例如圖2所示。當(dāng)λ取值在網(wǎng)絡(luò)整體的粒子松密度附近時(shí)，實(shí)驗(yàn)結(jié)果與原始聚類結(jié)果之間的差異將逐漸變小。其網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖3所示。

3.3 書局網(wǎng)絡(luò)實(shí)驗(yàn)數(shù)據(jù)分析

書局網(wǎng)絡(luò)數(shù)據(jù)集包含105個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)之間連接的邊數(shù)有159條，網(wǎng)絡(luò)的粒子松密度值為0.39。

該網(wǎng)絡(luò)數(shù)據(jù)集實(shí)際社團(tuán)的結(jié)構(gòu)如圖4所示。從該拓?fù)浣Y(jié)構(gòu)中可以明顯觀察出其并不完全符合網(wǎng)絡(luò)社團(tuán)的定義：1號社團(tuán)中的大部分節(jié)點(diǎn)都與其他社團(tuán)連接緊密。按照該社團(tuán)結(jié)構(gòu)計(jì)算的模塊密度D的值為2.019。根據(jù)文中算法聚類過后的數(shù)據(jù)集如圖5所示，算法對原數(shù)據(jù)集的社團(tuán)進(jìn)行了部分修正，將1號社團(tuán)中的部分節(jié)點(diǎn)重新進(jìn)行聚類，當(dāng)取值為0.4時(shí)，對應(yīng)的模塊密度值最大，為4.054。從拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)上進(jìn)行比較，結(jié)果表明文中算法的聚類結(jié)果明顯優(yōu)于實(shí)際的聚類結(jié)果。

圖2 不同λ取值對海豚網(wǎng)聚類的影響

圖3 海豚網(wǎng)絡(luò)拓?fù)鋱D

圖4 書局實(shí)際社團(tuán)聚類拓?fù)鋱D

圖5 文中算法對數(shù)據(jù)網(wǎng)絡(luò)聚類拓?fù)鋱D

3.4 空手道俱樂部網(wǎng)絡(luò)數(shù)據(jù)集測試

空手道俱樂部數(shù)據(jù)集包含34個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)之間連接的邊數(shù)為78，網(wǎng)絡(luò)的粒子松密度值為0.436。網(wǎng)絡(luò)數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)如圖6所示。當(dāng)取值為0.1～0.4時(shí)，NMI=1得出的聚類結(jié)果與實(shí)際聚類結(jié)果相符；取值為0.5～0.9時(shí)，NMI值為0.454與真實(shí)結(jié)果有偏差。

圖6 空手道俱樂部網(wǎng)絡(luò)拓?fù)鋱D

3.5 小 結(jié)

通過對各個(gè)數(shù)據(jù)集的實(shí)驗(yàn)數(shù)據(jù)分析可以判斷，λ的取值對于文中算法的聚類效果具有較大影響。邊數(shù)比較密集的網(wǎng)絡(luò)中，其網(wǎng)絡(luò)的粒子松密度則偏小，因此合并節(jié)點(diǎn)i和j時(shí)，需要將Bij的值適當(dāng)調(diào)大。λ的意義即是針對稀疏度不同的網(wǎng)絡(luò)來調(diào)整節(jié)點(diǎn)之間合并的條件。文中算法經(jīng)過實(shí)驗(yàn)數(shù)據(jù)測試得出λ與網(wǎng)絡(luò)整體的粒子松密度有著直接聯(lián)系，同時(shí)，實(shí)驗(yàn)結(jié)果表明，文中算法對于符合社團(tuán)基本定義的網(wǎng)絡(luò)可以給出準(zhǔn)確的聚類結(jié)果。

4 結(jié)束語

對于復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分的算法種類繁多，皆是優(yōu)缺點(diǎn)兼有。文中算法結(jié)合度值和粒子松密度的概念逐步對網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行聚類。通過對實(shí)驗(yàn)數(shù)據(jù)的分析得出，不同網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)與網(wǎng)絡(luò)整體的稀疏程度有著密切的聯(lián)系:稀疏的網(wǎng)絡(luò)社團(tuán)內(nèi)的節(jié)點(diǎn)連接也比較稀疏，但相比社團(tuán)之間的連接要緊密；稠密的網(wǎng)絡(luò)社團(tuán)之間的連接比較稠密，但相對比社團(tuán)內(nèi)的連接仍然稀疏。文中算法能準(zhǔn)確地利用網(wǎng)絡(luò)整體的稀疏度來對網(wǎng)絡(luò)進(jìn)行聚類分析。實(shí)驗(yàn)結(jié)果表明，文中算法可按網(wǎng)絡(luò)社團(tuán)聚類的基本原理給出較優(yōu)的社團(tuán)結(jié)構(gòu)，效率較高。

[1]LiuH,CaoM,WuCW.Couplingstrengthallocationforsynchronizationincomplexnetworksusingspectralgraphtheory[J].IEEETransactionsonCircuitsandSystemsI:RegularPapers,2014,61:1520-1530.

[2]KangS,BaderDA.Largescalecomplexnetworkanalysisusingthehybridcombinationofamapreduceclusterandahighlymultithreadedsystem[C]//Procof2010IEEEinternationalsymposiumonparallelanddistributedprocessing,workshopsandPhdforum.Atlanta,GA,UnitedStates:IEEE,2010.

[3]PeiT,ZhangH,LiZ,etal.Surveyofcommunitystructuresegmentationincomplexnetworks[J].JournalofSoftware,2014,9(1):89-93.

[4]NewmanMEJ.Thestructureofscientificcollaborationnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2001,98:404-409.

[5]LiZ,ZhangS,WangRS,etal.Quantitativefunctionforcommunitydetection[J].PhysicalReviewE,2008,77:036109.

[6]YangB,LiuDY,LiuJ,etal.Complexnetworkclusteringalgorithms[J].JournalofSoftware,2009,20(1):54-66.

[7]GongMG,CaiQ,ChenXW,etal.Complexnetworkclusteringbymultiobjectivediscreteparticleswarmoptimizationbasedondecomposition[J].IEEETransactionsonEvolutionaryComputation,2014,18(1):82-97.

[8]LeskovecJ,LangKJ,MahoneyM.Empiricalcomparisonofalgorithmsfornetworkcommunitydetection[C]//Procof19thinternationalworldwidewebconference.Raleigh,NC,UnitedStates:[s.n.],2010:631-640.

[9]TongC,NiuJW,DaiB,etal.Complexnetworksclusteringalgorithmbasedonthecoreinfluenceofthenodes[C]//Procof2012IEEE31stinternationalperformancecomputingandcommunicationsconference.[s.l.]:IEEE,2012:185-186.

[10]LiuX,LiD,WangS,etal.EffectivealgorithmfordetectingcommunitystructureincomplexnetworksbasedonGAandclustering[C]//Procof7thinternationalconferenceoncomputationalscience.Beijing,China:[s.n.],2007:657-664.

[11]TongC,NiuJW,DaiB,etal.Anovelcomplexnetworksclusteringalgorithmbasedonthecoreinfluenceofnodes[J].ScientificWorldJournal,2014,2014:801854.

[12]LiuYH,JinJZ,ZhangY,etal.Anewclusteringalgorithmbasedondatafieldincomplexnetworks[J].JournalofSupercomputing,2014,67(3):723-737.

[13]DanonL,Díaz-GuileraA,DuchJ,etal.Comparingcommunitystructureidentification[J].JournalofStatisticalMechanicsTheory&Experiment,2005,2005:P09008.

[14]LusseauD,SchneiderK,BoisseauOJ,etal.Thebottlenosedolphincommunityofdoubtfulsoundfeaturesalargeproportionoflong-lastingassociations[J].BehavioralEcology&Sociobiology,2003,54:396-405.

[15]NewmanME.Findingcommunitystructureinnetworksusingtheeigenvectorsofmatricies[J].PhysicalReviewE,2006,74:036104.

[16]GirvanM,NewmanMEJ.Communitystructureinsocialandbiologicalnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2002,99:7821-7826.

Community Clustering Algorithm in Complex Networks Based on Bulk Density

JIANG Fei1,WANG Xiao-jun1,XU Bin2,QI Jin2

(1.School of Computer Science and Technology,School of Software，NJUPT,Nanjing 210003,China;2.School of Internet of Things,NJUPT,Nanjing 210003,China)

The association clustering algorithm of complex networks is a new emerging hot topic in the field of data mining.Traditional intelligent optimization algorithm has better effect in clustering,but it has low execution efficiency and narrow application scope.Although some heuristic algorithm has obvious advantages of clustering efficiency,but compared with the intelligent optimization algorithm,universality still has not be improved.To improve the efficiency of community division algorithm,through the research of the concept of bulk density in the field of materials science,puts forward a kind of association clustering algorithm based on bulk density.The experiment shows that the algorithm proposed has obvious advantage in time and precision compared with other algorithms.

complex networks;bulk density;community;clustering

2015-11-23

2016-03-04

時(shí)間：2016-09-19

國家自然科學(xué)基金資助項(xiàng)目(61401225)；中國博士后科學(xué)基金資助項(xiàng)目(2015M571790)

姜 斐(1992-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘；王曉軍，副研究員，碩士生導(dǎo)師，研究方向?yàn)榉植加?jì)算技術(shù)與應(yīng)用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0839.004.html

TP301.6

A

1673-629X(2016)10-0060-04

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