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

寧念文 許合利 劉喜峰

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

?

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

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

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

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

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

1.1 標簽傳播算法基本步驟

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

(1) 每個節(jié)點初始化唯一的標簽Lx=x。

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

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

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

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

1.2 資源分配指標(RA)

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

(1)

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

1.3 最大約束標記傳播模型

(2)

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

2 RALPA算法

2.1 RALPA算法思想

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

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

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

算法1 RALPA算法

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

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

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

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

算法流程：

1) 初始化每個節(jié)點的標簽Vi=i。

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

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

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

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

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

算法偽代碼：

For everyx∈V

xlabel= Initialize(x);

//將節(jié)點的標簽初始化

Fory∈xneighbor

//依次計算x和鄰域元素的相似度

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

End for

End for

For iter=1:Iterate

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

For everyx∈V

//根據(jù)下面公式更新節(jié)點自身的標簽

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ū)對

End For

End While

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

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

節(jié)點標簽更新的時間復(fù)雜度為：對每個節(jié)點進行相似性計算和更新標簽的時間復(fù)雜度為O(N)；Iterate次迭代的總時間復(fù)雜度為O(Iterate×N)。

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

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

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

3.1 模塊度Q

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

(3)

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

3.2 標準化互信息NMI

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

(4)

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

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

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

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

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

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

表3 各種算法NMI值的比較

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

本文算法運用模塊度最大化進行社區(qū)發(fā)現(xiàn)，但是由于模塊度的缺陷使以模塊度為目標函數(shù)的優(yōu)化算法只能夠發(fā)現(xiàn)特定的社區(qū)結(jié)構(gòu)，而真實網(wǎng)絡(luò)中的社區(qū)都是多規(guī)模的。因此，下一步的工作是對多分辨率社區(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)定的標簽傳播社區(qū)發(fā)現(xiàn)算法[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é)點聚集系數(shù)的分布式標簽傳播算法[J].計算機應(yīng)用與軟件,2016,33(4):125-128.

[7] 黃健斌, 鐘翔, 孫鶴立,等. 基于相似性模塊度最大約束標記傳播的網(wǎng)絡(luò)社團發(fā)現(xiàn)算法[J]. 北京大學(xué)學(xué)報(自然科學(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。國家自然科學(xué)基金項目(61202286)；國家科技重大專項核心電子器件、高端通用芯片及基礎(chǔ)軟件產(chǎn)品專項(2014ZX01045-102)。寧念文，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘，并行計算。許合利，教授。劉喜峰，教授。

TP3

A

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