寧念文 許合利 劉喜峰

1(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)2(鄭州工程技術(shù)學(xué)院機(jī)電與車輛工程學(xué)院 河南 鄭州 450044)

?

基于資源分配指標(biāo)的最大約束社區(qū)發(fā)現(xiàn)算法

寧念文1許合利1劉喜峰2

1(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)2(鄭州工程技術(shù)學(xué)院機(jī)電與車輛工程學(xué)院 河南 鄭州 450044)

在復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)一直受到廣泛的關(guān)注，基于模塊度最大化的方法是目前流行的社區(qū)發(fā)現(xiàn)技術(shù)。提出一種基于資源分配(RA)指標(biāo)和多步貪婪凝聚策略的模塊度最大化社區(qū)發(fā)現(xiàn)算法RALPA(Resource Allocation-based of Label propagation Algorithm)。該算法利用準(zhǔn)確衡量節(jié)點(diǎn)間相似性的RA指標(biāo)，通過(guò)最大約束標(biāo)記傳播模型使社區(qū)內(nèi)部節(jié)點(diǎn)擁有較高的相似性，與社區(qū)外部的節(jié)點(diǎn)擁有較低的相似性。然后，通過(guò)多步貪婪凝聚策略將劃分模塊度增加最大的多對(duì)小社區(qū)進(jìn)行合并。實(shí)驗(yàn)結(jié)果表明，該算法不僅避免了對(duì)節(jié)點(diǎn)更新順序的敏感和易得到平凡解的問(wèn)題，而且提高了算法的穩(wěn)定性和社區(qū)劃分的精度。

社區(qū)發(fā)現(xiàn) 模塊度最大化 資源分配指標(biāo) 最大約束標(biāo)記傳播模型

0 引 言

社區(qū)結(jié)構(gòu)具有內(nèi)部個(gè)體之間聯(lián)系密切，但與外部其他個(gè)體聯(lián)系稀疏的特點(diǎn)。因此，根據(jù)“在具有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)中，任何一個(gè)節(jié)點(diǎn)都應(yīng)當(dāng)與其大多數(shù)相鄰節(jié)點(diǎn)在同一個(gè)社區(qū)內(nèi)”的思想，2007年Raghavan[1]等提出了接近線性復(fù)雜度的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法—標(biāo)簽傳播算法(LPA)。該算法具有簡(jiǎn)單高效、不需要提供社區(qū)規(guī)模和社區(qū)個(gè)數(shù)等先驗(yàn)知識(shí)的特點(diǎn)。但是，由于LPA在標(biāo)簽傳播過(guò)程中存在著大量的隨機(jī)性，這些隨機(jī)性嚴(yán)重破壞了算法的魯棒性，進(jìn)而破壞了所識(shí)別社區(qū)結(jié)構(gòu)的穩(wěn)定性[2]。針對(duì)上述缺點(diǎn)，Barber[3]等為了避免算法將所有節(jié)點(diǎn)劃分到同一社區(qū)，提出了一種帶有約束的模塊化標(biāo)簽傳播算法(LPAm)，將社區(qū)聚類問(wèn)題轉(zhuǎn)化為求基于模塊度的目標(biāo)函數(shù)最大值問(wèn)題。但是，LPAm易陷入局部最優(yōu)并且基于不同的社區(qū)具有相似的總節(jié)點(diǎn)度數(shù)。Liu[4]等提出了LPAm+算法，該算法在LPAm的基礎(chǔ)上通過(guò)多步貪婪凝聚算法(MSG)使LPAm跳出局部最大值，提高了社區(qū)劃分的精度。但是，該算法循環(huán)迭代效率較低，并且應(yīng)用到大數(shù)據(jù)集上時(shí)性能受到限制。Leung等[5]發(fā)現(xiàn)算法經(jīng)過(guò)5次迭代后，大部分節(jié)點(diǎn)已經(jīng)正確聚集，后面的迭代主要是對(duì)社區(qū)內(nèi)的節(jié)點(diǎn)進(jìn)行不必要的更新。因此，通過(guò)改進(jìn)LPA的節(jié)點(diǎn)更新策略和迭代規(guī)則可以提高算法的執(zhí)行效率，減少迭代次數(shù)，使算法盡快收斂。

為了提高算法的迭代效率和劃分社區(qū)的準(zhǔn)確度，一方面通過(guò)節(jié)點(diǎn)影響力的優(yōu)化，另一方面通過(guò)節(jié)點(diǎn)之間相似度的優(yōu)化。張素智等[6]提出了基于節(jié)點(diǎn)聚集系數(shù)的分布式標(biāo)簽傳播算法。該算法通過(guò)聚集系數(shù)衡量節(jié)點(diǎn)的影響力，使算法能夠快速收斂到正確的社區(qū)中，同時(shí)通過(guò)并行化處理提高算法的執(zhí)行效率。黃健斌等[7]提出基于相似性模塊度最大約束標(biāo)記傳播算法。該算法將最大約束標(biāo)記傳播模型為目標(biāo)函數(shù)，使劃分的社區(qū)結(jié)構(gòu)更加緊密。很多研究者通過(guò)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)間的相似性衡量節(jié)點(diǎn)之間聯(lián)系的強(qiáng)弱。周濤等[8]基于不同類型的網(wǎng)絡(luò)對(duì)9種已知的基于局部信息的相似性指標(biāo)在鏈路預(yù)測(cè)中的效果進(jìn)行比較分析，并提出了資源分配指標(biāo)RA(Resource Allocation index) 和LP(Local Path index)。通過(guò)在網(wǎng)絡(luò)中的預(yù)測(cè)效果表明這種指標(biāo)都具有明顯好于9種已知指標(biāo)的預(yù)測(cè)能力。

本文所做的工作：第一，利用RA相似性指標(biāo)，使其準(zhǔn)確地衡量直接相連節(jié)點(diǎn)間的相似性；第二，通過(guò)最大約束標(biāo)記傳播模型對(duì)網(wǎng)絡(luò)進(jìn)行粗粒度的社區(qū)發(fā)現(xiàn)，提高社區(qū)劃分的準(zhǔn)確度，避免算法對(duì)節(jié)點(diǎn)更新順序敏感的缺點(diǎn)；第三，使用MSG算法依據(jù)模塊度最大化策略合并已得到的社區(qū)結(jié)構(gòu)，使算法得到更高質(zhì)量的社區(qū)結(jié)構(gòu)。

圖1 Karate網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)特點(diǎn)

1 相關(guān)工作

現(xiàn)有的針對(duì)標(biāo)簽傳播算法的改進(jìn)都存在迭代次數(shù)增加導(dǎo)致算法性能降低或者是仍然存在較高隨機(jī)性和不穩(wěn)定性。本節(jié)通過(guò)資源分配指標(biāo)準(zhǔn)確衡量節(jié)點(diǎn)之間的相似性，減少標(biāo)簽傳播過(guò)程中的隨機(jī)操作和迭代次數(shù)。在基于節(jié)點(diǎn)之間的資源分配相似性和目標(biāo)函數(shù)優(yōu)化理論的基礎(chǔ)上，通過(guò)最大約束標(biāo)記傳播模型判定標(biāo)簽的傳播方向, 使社團(tuán)的劃分結(jié)果更加符合社團(tuán)內(nèi)部結(jié)構(gòu)相對(duì)緊密, 社團(tuán)之間結(jié)構(gòu)較為稀疏的性質(zhì)，提高算法對(duì)社區(qū)劃分的精度。

1.1 標(biāo)簽傳播算法基本步驟

網(wǎng)絡(luò)G=(V,E),V表示節(jié)點(diǎn)集,E表示邊集。對(duì)于任意的x∈V,Cx(t)=Lx。Cx(t)表示t時(shí)刻節(jié)點(diǎn)x所屬的社區(qū)，Lx表示x節(jié)點(diǎn)t時(shí)刻的標(biāo)簽。LPA算法的具體步驟如下：

(1) 每個(gè)節(jié)點(diǎn)初始化唯一的標(biāo)簽Lx=x。

(2) 將V中節(jié)點(diǎn)隨機(jī)重新排序，并賦予節(jié)點(diǎn)集x。

(3) 對(duì)于重新排序后的任意x∈X，節(jié)點(diǎn)x將自身的標(biāo)簽更新為其鄰節(jié)點(diǎn)中擁有相同標(biāo)簽節(jié)點(diǎn)個(gè)數(shù)最多的標(biāo)簽。

(4) 當(dāng)所有節(jié)點(diǎn)的標(biāo)簽都與其大多數(shù)相鄰節(jié)點(diǎn)的標(biāo)簽相同時(shí)，算法結(jié)束。否則，繼續(xù)返回第2步再次進(jìn)行標(biāo)簽的更新。

標(biāo)簽的更新策略分為：同步更新策略和異步更新策略。同步更新策略是當(dāng)對(duì)節(jié)點(diǎn)進(jìn)行第t+1次標(biāo)簽更新時(shí)，依據(jù)鄰居的第t次標(biāo)簽來(lái)更新自身的標(biāo)簽。異步更新策略是對(duì)節(jié)點(diǎn)進(jìn)行第t+1次更新時(shí)，依據(jù)鄰居最新的標(biāo)簽來(lái)更新自身的標(biāo)簽。由于同步更新策略容易產(chǎn)生震蕩現(xiàn)象，所以本文算法采用異步更新策略。

1.2 資源分配指標(biāo)(RA)

為了更加準(zhǔn)確地衡量節(jié)點(diǎn)間的相似度，我們利用RA指標(biāo)相似性反映節(jié)點(diǎn)之間聯(lián)系的緊密程度。在圖1中節(jié)點(diǎn)12.0和節(jié)點(diǎn)1.0直接相連。那么，根據(jù)文獻(xiàn)[8]中RA的定義不能夠直接計(jì)算，文獻(xiàn)[9]計(jì)算得到兩點(diǎn)之間的相似性為0，將節(jié)點(diǎn)12.0和不在節(jié)點(diǎn)1.0鄰域中的其他節(jié)點(diǎn)同等對(duì)待，這樣導(dǎo)致衡量的結(jié)果不夠準(zhǔn)確，不能正確反映節(jié)點(diǎn)之間的關(guān)系。因此，本文對(duì)RA相似性進(jìn)行了擴(kuò)展：

(1)

x和y直接相連， 表示節(jié)點(diǎn)x和節(jié)點(diǎn)y之間的相似性， 表示x的鄰接點(diǎn)集(包括x節(jié)點(diǎn)本身以及與x直接相連的節(jié)點(diǎn))，k(z)表示x和y共享的鄰節(jié)點(diǎn)集中節(jié)點(diǎn)z的度數(shù)。擴(kuò)展之后的RA相似性能夠更加準(zhǔn)確地反映節(jié)點(diǎn)之間的相似性，將相鄰節(jié)點(diǎn)之間的相似性與非相鄰節(jié)點(diǎn)進(jìn)行了區(qū)分。

1.3 最大約束標(biāo)記傳播模型

(2)

本文基于RA指標(biāo)和最大約束標(biāo)記傳播模型對(duì)網(wǎng)絡(luò)進(jìn)行粗粒度的社區(qū)發(fā)現(xiàn)。因?yàn)镽A指標(biāo)能夠通過(guò)節(jié)點(diǎn)局部信息準(zhǔn)確地反映節(jié)點(diǎn)之間聯(lián)系的緊密程度，所以使最大約束標(biāo)記傳播模型能夠提高社區(qū)劃分的準(zhǔn)確度，并且使劃分結(jié)果更加符合社區(qū)結(jié)構(gòu)的特點(diǎn)。

2 RALPA算法

2.1 RALPA算法思想

本文提出的RALPA算法主要分為兩個(gè)部分：1) 通過(guò)RA相似性的最大約束標(biāo)記傳播模型進(jìn)行社區(qū)發(fā)現(xiàn)，得到粗粒度的社區(qū)劃分；2) 在上一步劃分的基礎(chǔ)上，進(jìn)行基于MSG算法的模塊度最大化社區(qū)的修正。

MSG算法的對(duì)于社區(qū)對(duì)的修正準(zhǔn)則為：假設(shè)t1和t2是要合并的社區(qū)對(duì)，合并后模塊度增加量為ΔQ(t1,t2)并且不存在其他任意的社區(qū)t，與t1、t2組成社區(qū)對(duì)(t,t1)或(t,t2)，使ΔQ(t,t1)、ΔQ(t,t2)>ΔQ(t1,t2)。通過(guò)兩種方式的結(jié)合，隨著迭代次數(shù)的增加，能夠更快、更準(zhǔn)確地將節(jié)點(diǎn)劃分到正確的社區(qū)中。同時(shí)，減少模塊度最大化合并的社區(qū)數(shù)目和在局部最優(yōu)空間中的小范圍循環(huán)次數(shù)，避免低效率的迭代。

RALPA算法的主要思想：首先，利用RA指標(biāo)計(jì)算每個(gè)點(diǎn)與相鄰節(jié)點(diǎn)之間的相似性；然后，根據(jù)最大約束標(biāo)記傳播模型來(lái)更新節(jié)點(diǎn)的標(biāo)簽，得到初步的社區(qū)劃分結(jié)果；最后，基于MSG算法合并能夠使社區(qū)模塊度最大程度提高的社區(qū)，得到最終的社區(qū)劃分。因?yàn)槲墨I(xiàn)[5]中經(jīng)過(guò)大量實(shí)驗(yàn)證明經(jīng)過(guò)5次迭代后，95%的節(jié)點(diǎn)已正確的聚集。所以，本文設(shè)置算法的迭代次數(shù)為5次。因?yàn)橥ㄟ^(guò)MSG算法對(duì)結(jié)果進(jìn)行修正，所以能夠同時(shí)合并多對(duì)符合要求的社區(qū)，提高算法的效率。

算法1 RALPA算法

輸入：網(wǎng)絡(luò)G=(V,E),V表示節(jié)點(diǎn)集,E表示邊集,迭代次數(shù)Iterate=5

輸出：各節(jié)點(diǎn)以及所屬的社區(qū)

變量和函數(shù)說(shuō)明：

ΔQt1t2表示社區(qū)t1和t2合并之后模塊度的變化量；Initialize(x)表示節(jié)點(diǎn)x的標(biāo)簽初始化；Merge(t1，t2)表示將社區(qū)t1和t2進(jìn)行合并。

算法流程：

1) 初始化每個(gè)節(jié)點(diǎn)的標(biāo)簽Vi=i。

2) 計(jì)算每個(gè)節(jié)點(diǎn)x的鄰域Γ(x)，根據(jù)式(1)計(jì)算每個(gè)節(jié)點(diǎn)x與其他節(jié)點(diǎn)y的資源分配相似性矩陣Sxy。

3) 迭代次數(shù)iter=1。

5) 如果每個(gè)節(jié)點(diǎn)的標(biāo)簽都不再變化或者達(dá)到最大迭代次數(shù)Iterate，則算法結(jié)束，具有相同標(biāo)簽的節(jié)點(diǎn)為同一個(gè)社區(qū)；否則iter=iter+1，返回步驟(4)。

6) 在步驟5)所得到結(jié)果的基礎(chǔ)上，根據(jù)MSG算法合并準(zhǔn)則，同時(shí)合并使模塊度增大的多對(duì)社區(qū)。

7) 如果任意社區(qū)對(duì)合并后模塊度不再增加，那么算法結(jié)束；具有相同標(biāo)簽的節(jié)點(diǎn)為同一個(gè)社區(qū)。

算法偽代碼：

For everyx∈V

xlabel= Initialize(x);

//將節(jié)點(diǎn)的標(biāo)簽初始化

Fory∈xneighbor

//依次計(jì)算x和鄰域元素的相似度

// Sxy表示節(jié)點(diǎn)之間的相似矩陣

End for

End for

For iter=1:Iterate

//設(shè)置最大迭代次數(shù)

For everyx∈V

//根據(jù)下面公式更新節(jié)點(diǎn)自身的標(biāo)簽

End for

End For

While ?(t1,t2):Δt1t2>0

//模塊度增加量為正整數(shù)

For every (t1,t2):Δt1t2>0∧!?t:Δt1t>Δt1t2∨Δt1t<Δt1t2

Merge(t1，t2);

//合并社區(qū)對(duì)

End For

End While

2.2 時(shí)間復(fù)雜度分析

對(duì)于圖G=(V,E)，N表示節(jié)點(diǎn)個(gè)數(shù)，M表示邊的個(gè)數(shù)，最大迭代次數(shù)Iterate。本文算法主要的時(shí)間復(fù)雜度為節(jié)點(diǎn)標(biāo)簽更新的時(shí)間復(fù)雜度和計(jì)算社區(qū)劃分模塊度的時(shí)間復(fù)雜度。

節(jié)點(diǎn)標(biāo)簽更新的時(shí)間復(fù)雜度為：對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行相似性計(jì)算和更新標(biāo)簽的時(shí)間復(fù)雜度為O(N)；Iterate次迭代的總時(shí)間復(fù)雜度為O(Iterate×N)。

計(jì)算模塊度的時(shí)間復(fù)雜度：每次計(jì)算模塊度增量計(jì)算的時(shí)間復(fù)雜度為O(M)；以模塊度優(yōu)化為目的進(jìn)行社區(qū)之間的合并所需要的最大時(shí)間復(fù)雜度為O(N)，社區(qū)合并在最壞情況下需要的迭代次數(shù)為O(logN)。因此，RALPA算法的時(shí)間復(fù)雜度為O(M×logN)。由于采用基于相似性的社區(qū)發(fā)現(xiàn)和MSG凝聚策略所以比LPAm+算法擁有更優(yōu)的時(shí)間復(fù)雜度。

3 實(shí)驗(yàn)結(jié)果與分析

在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和人工網(wǎng)絡(luò)數(shù)據(jù)集上，通過(guò)模塊度和NMI值，這兩種公認(rèn)的評(píng)價(jià)標(biāo)準(zhǔn)來(lái)驗(yàn)證算法的性能。本文所采用的數(shù)據(jù)集：1)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，數(shù)據(jù)來(lái)源于現(xiàn)實(shí)世界中，通過(guò)對(duì)真實(shí)世界中關(guān)系的建模得到；2)人工網(wǎng)絡(luò)數(shù)據(jù)集，即利用程序自動(dòng)生成的數(shù)據(jù)集。本文采用LFR基準(zhǔn)程序生成人工網(wǎng)絡(luò)數(shù)據(jù)集。本文算法的實(shí)驗(yàn)環(huán)境為Matlab2014a軟件，硬件的配置為：Pentium(R) Dual-Core CPU, E5800 @ 3.20GHz, RAM 4.00G；軟件配置：64位WIN8操作系統(tǒng)。

3.1 模塊度Q

Newman和Girvan在文獻(xiàn)[10]中提出模塊度的概念，后來(lái)作為衡量社區(qū)算法性能的公認(rèn)評(píng)價(jià)標(biāo)準(zhǔn)。模塊度用來(lái)衡量社區(qū)結(jié)構(gòu)性的強(qiáng)弱，其值越接近1，表示劃分出的社區(qū)結(jié)構(gòu)性越強(qiáng)，劃分的結(jié)果越好。模塊度的定義如下：

(3)

其中，N表示社區(qū)數(shù)目，lc表示社區(qū)c中的總邊數(shù)，m表示網(wǎng)絡(luò)中的總邊數(shù)，dc表示社區(qū)c中節(jié)點(diǎn)度數(shù)的總和。

3.2 標(biāo)準(zhǔn)化互信息NMI

NMI[11]即標(biāo)準(zhǔn)化互信息，通過(guò)NMI值比較社區(qū)劃分的結(jié)果與標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)的相似度，從而衡量社區(qū)劃分的質(zhì)量。由于本文采用的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的社區(qū)結(jié)構(gòu)已知，以此衡量劃分結(jié)果與真實(shí)社區(qū)的相似度。NMI的定義為：

(4)

其中，Ni,j表示兩個(gè)社區(qū)公共節(jié)點(diǎn)數(shù)，Ni和Nj分別表示混合矩陣中第i行與第j列的和。

3.3 真實(shí)數(shù)據(jù)集

為了驗(yàn)證本文提出的RALPA算法的性能，選擇的真實(shí)數(shù)據(jù)集為空手道俱樂(lè)部Karate數(shù)據(jù)集、海豚Dolphins數(shù)據(jù)集、橄欖球俱樂(lè)部Football數(shù)據(jù)集、政治書Polbooks數(shù)據(jù)集四種公認(rèn)的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，其參數(shù)如表1所示。

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

將算法應(yīng)用到真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集測(cè)試所劃分社區(qū)的平均模塊度Q和NMI指標(biāo)。將本文算法與傳統(tǒng)LPA、LPAm、LPAm+、MLPA進(jìn)行比較。不同算法分別在四種數(shù)據(jù)集上進(jìn)行100次運(yùn)算，計(jì)算結(jié)果的平均模塊度和NMI值見(jiàn)表2和表3。

表2 各種算法平均模塊度的比較

表3 各種算法NMI值的比較

通過(guò)對(duì)表2和表3的分析可知，RALPA算法在四種不同的真實(shí)數(shù)據(jù)集中表現(xiàn)出較好的性能。但在Karate數(shù)據(jù)集中本文算法的平均模塊度值不是最好。由于LPAm+算法從初始節(jié)點(diǎn)開(kāi)始進(jìn)行模塊度的優(yōu)化，所以獲得了很好的模塊度，同時(shí)導(dǎo)致算法具有較高的時(shí)間復(fù)雜度?？傮w而言，本文算法表現(xiàn)出較好的性能，特別是在Polbooks社區(qū)結(jié)構(gòu)不明顯的情況下也獲得了較好的結(jié)果。本文算法對(duì)karate數(shù)據(jù)集的劃分結(jié)果如圖2所示。

圖2 本文算法對(duì)Karate數(shù)據(jù)集劃分結(jié)果

通過(guò)圖1與圖2的對(duì)比，本文算法將以33.0為中心的社區(qū)劃分為兩部分。其中{25.0,26.0,29.0,32.0}表示一個(gè)小社區(qū)，這樣使獲得的社區(qū)結(jié)構(gòu)具有較高的模塊度。這四個(gè)節(jié)點(diǎn)在最大約束標(biāo)記傳播模型和模塊度最大化兩者作用下，最終獲得了具有更高模塊度的社區(qū)劃分。綜上所述，RALPA算法在4個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中得到了較好的社區(qū)結(jié)構(gòu)。

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

通過(guò)LFR基準(zhǔn)程序分別生成了500個(gè)節(jié)點(diǎn)基準(zhǔn)數(shù)據(jù)集和1 000節(jié)點(diǎn)的基準(zhǔn)數(shù)據(jù)集。節(jié)點(diǎn)數(shù)N,平均度數(shù)AD, 最大度數(shù)MD, 最大社區(qū)規(guī)模MXC, 最小社區(qū)規(guī)模MIC，節(jié)點(diǎn)度分布指數(shù)DD, 社團(tuán)規(guī)模分布指數(shù)DC, 社區(qū)混合參數(shù)μ。其中，μ表示混合參數(shù)，反映生成社區(qū)結(jié)構(gòu)性的關(guān)鍵指標(biāo)。具體信息如表4所示。

表4 兩種LFR網(wǎng)絡(luò)參數(shù)信息

LFR人工數(shù)據(jù)集已有確定的社區(qū)結(jié)構(gòu)，在這兩種數(shù)據(jù)集上通過(guò)分析NMI值比較算法的性能，考慮到實(shí)驗(yàn)中算法的不穩(wěn)定性，不考慮結(jié)果為0的樣本。實(shí)驗(yàn)結(jié)果如圖3(a)、(b)所示。

(a) 算法在LFR500數(shù)據(jù)集上NMI值

(b) 算法在LFR1000數(shù)據(jù)集上NMI值圖3 4種算法分別在兩種數(shù)據(jù)集上的NMI值

在節(jié)點(diǎn)為500和1 000的人工網(wǎng)絡(luò)數(shù)據(jù)集中，RALPA算法表現(xiàn)出較好的性能，劃分出更準(zhǔn)確的社區(qū)結(jié)果。其中，在μ≤0.6時(shí)，社區(qū)結(jié)構(gòu)不明顯的情況下能表現(xiàn)出比LPA、LPAm、LPAm+算法更好的性能。無(wú)論是在500個(gè)節(jié)點(diǎn)的數(shù)據(jù)集中還是1 000個(gè)節(jié)點(diǎn)的數(shù)據(jù)集中，本文算法劃分結(jié)果的NMI值都在0.60以上。表5為本文算法和MLPA算法在μ=0.6和μ=0.65時(shí)的NMI結(jié)果比較，可以看出本文算法在社區(qū)結(jié)構(gòu)不明顯的情況下優(yōu)于MLPA算法。由于RALPA算法具有較低的時(shí)間復(fù)雜度和較好的劃分結(jié)果，所以本文算法比以上算法具有更好的性能。

表5 社區(qū)結(jié)構(gòu)不明顯的情況下算法NMI值的比較

4 結(jié) 語(yǔ)

RALPA算法利用資源分配指標(biāo)更準(zhǔn)確地衡量節(jié)點(diǎn)之間的相似性。通過(guò)引入最大約束標(biāo)記傳播模型，使劃分出的社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)之間具有更高的相似性，與社區(qū)之間具有較低的相似性，提高了社區(qū)劃分精度，減少了在局部最優(yōu)取值空間中的迭代次數(shù)。通過(guò)多步貪婪凝聚算法進(jìn)行模塊度最大化，提高了社區(qū)合并的效率，同時(shí)使算法能夠跳出局部最優(yōu)解。通過(guò)在真實(shí)基準(zhǔn)數(shù)據(jù)集和人工網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明RALPA算法具有更好性能，能夠劃分出更高質(zhì)量的社區(qū)結(jié)構(gòu)。

本文算法運(yùn)用模塊度最大化進(jìn)行社區(qū)發(fā)現(xiàn)，但是由于模塊度的缺陷使以模塊度為目標(biāo)函數(shù)的優(yōu)化算法只能夠發(fā)現(xiàn)特定的社區(qū)結(jié)構(gòu)，而真實(shí)網(wǎng)絡(luò)中的社區(qū)都是多規(guī)模的。因此，下一步的工作是對(duì)多分辨率社區(qū)發(fā)現(xiàn)算法的研究。

[1] Usha Nandini R, Réka A, Soundar K. Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007,76(3):36106.

[2] 石立新, 張俊星. 一種穩(wěn)定的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)應(yīng)用與軟件, 2015,32(3):261-265.

[3] Barber M J, Clark J W. Detecting network communities by propagating labels under constraints[J].Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009,80(2):283-289.

[4] Liu X, Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J].Physica A: Statistical Mechanics and its Applications, 2010,389(7):1493-1500.

[5] Leung X Y, Hui P, Lio P, et al. Towards real-time community detection in large networks[J].Physical review E, Statistical, nonlinear, and soft matter physics,2009,79(6):066107.

[6] 張素智, 孫嘉彬, 王威. 基于節(jié)點(diǎn)聚集系數(shù)的分布式標(biāo)簽傳播算法[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(4):125-128.

[7] 黃健斌, 鐘翔, 孫鶴立,等. 基于相似性模塊度最大約束標(biāo)記傳播的網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J]. 北京大學(xué)學(xué)報(bào)(自然科學(xué)版),2013(3):389-396.

[8] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information[J].The European Physical Journal B, 2009,71(4):623-630.

[9] Pan Y, Li D H, Liu J G, et al. Detecting community structure in complex networks via node similarity[J].Physica A:Statistical Mechanics and its Applications,2010,389(14):2849-2857.

[10] Newman M E. Fast algorithm for detecting community structure in networks[J].Physical review. E, Statistical, nonlinear, and soft matter physics, 2004, 69(6):066133.

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

MAXIMUM CONSTRAINED COMMUNITY DETECTION ALGORITHM BASED ON RESOURCE ALLOCATION INDEX

Ning Nianwen1Xu Heli1Liu Xifeng2

1(CollegeofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)2(InstituteofElectricalandMechanicalVehicleEngineering,ZhengzhouInstituteofTechnology,Zhengzhou450044,Henan,China)

Community detection in complex networks have

wide attention, and the method based on modularity maximization is the popular community detection technology. In this paper, a modularity maximization community detection algorithm named RALPA (Resource Allocation-based of Label Propagation Algorithm) is proposed, which is based on resource allocation (RA) and multi-step greedy cohesion strategy. The algorithm uses the RA index to measure the similarity between nodes accurately. By using the maximum constraint label propagation model, the internal nodes of the community have high similarity, and have low similarity with the nodes outside the community. Then, through the multi-step greedy cohesion strategy, the multi-pair small communities with the largest increase of partitioning degree will be merged. The experimental results show that the proposed algorithm not only avoids the problem of the sensitivity of node update order and the trivial solution, but also improves the stability of the algorithm and the accuracy of community division.

Community detection Modularity optimization Resource allocation Maximum constraint label propagation model

2016-07-11。國(guó)家自然科學(xué)基金項(xiàng)目(61202286)；國(guó)家科技重大專項(xiàng)核心電子器件、高端通用芯片及基礎(chǔ)軟件產(chǎn)品專項(xiàng)(2014ZX01045-102)。寧念文，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘，并行計(jì)算。許合利，教授。劉喜峰，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.07.040