加權(quán)模塊度增量引導(dǎo)下的層次社區(qū)發(fā)現(xiàn)算法

張霄宏,郝浩宇,任杰成,王海濤

(河南理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

1 引 言

近年來,隨著智能移動設(shè)備的普及和5G通信技術(shù)的應(yīng)用,社交網(wǎng)絡(luò)迎來了新的發(fā)展高潮.社交網(wǎng)絡(luò)具有社區(qū)結(jié)構(gòu),即網(wǎng)絡(luò)中出現(xiàn)節(jié)點(diǎn)聚集的現(xiàn)象,這些“聚集”的節(jié)點(diǎn)及其邊共同構(gòu)成社區(qū)[1].研究表明社區(qū)結(jié)構(gòu)具有層次性,即低密度社區(qū)包含著高密度社區(qū),高密度社區(qū)可以包含著更高密度的社區(qū)[2].分析社交網(wǎng)絡(luò)中社區(qū)的層次結(jié)構(gòu),不僅有助于理解網(wǎng)絡(luò)的功能和演化機(jī)制,而且還可以為謠言溯源[3]、病毒傳播[4]等問題的解決提供支撐,具有十分重要的理論和應(yīng)用價值.

模塊度是評價社區(qū)劃分質(zhì)量的重要指標(biāo)之一[5,6].以優(yōu)化模塊度為目標(biāo)來挖掘社區(qū)結(jié)構(gòu)是發(fā)現(xiàn)層次社區(qū)的常用方法之一.基于模塊度優(yōu)化的層次社區(qū)發(fā)現(xiàn)算法[7,8]以迭代的方式逐層合并社區(qū),直至滿足收斂條件.由于在每輪迭代中只合并模塊度增量最大的社區(qū),故需要多輪迭代才能完成社區(qū)劃分,算法的收斂速度較慢.此外,受模塊度模型的影響,基于模塊度優(yōu)化的層次社區(qū)發(fā)現(xiàn)算法通常過度考慮社區(qū)之間的連接強(qiáng)度而忽視社區(qū)之間的相似性,導(dǎo)致連接強(qiáng)度較弱但相似性較高的社區(qū)無法合并[9],限制了社區(qū)劃分的質(zhì)量.盡管針對基于模塊度優(yōu)化的層次社區(qū)發(fā)現(xiàn)算法準(zhǔn)確率和效率問題開展了大量研究,但是該類算法在性能和社區(qū)劃分質(zhì)量方面存在的問題仍是開放問題.

針對這兩個問題,提出了加權(quán)模塊度增量引導(dǎo)下的非重疊社區(qū)發(fā)現(xiàn)算法.該算法引入與社區(qū)之間的相似性密切相關(guān)的相似性權(quán)重,構(gòu)建加權(quán)模塊度增量模型,以優(yōu)化加權(quán)模塊度增量為目標(biāo)進(jìn)行社區(qū)劃分,從而在社區(qū)劃分過程中既考慮社區(qū)之間的連接強(qiáng)度,又考慮社區(qū)之間的相似性.同時,為了提高收斂速度,在算法中引入了根據(jù)可調(diào)合并閾值動態(tài)進(jìn)行社區(qū)合并的策略,使得每輪迭代中有多組社區(qū)可以合并,從而加快算法收斂.

2 相關(guān)工作

模塊度是評價社區(qū)劃分質(zhì)量優(yōu)劣的重要指標(biāo)之一.Newman等人[7]提出以模塊度最大化作為優(yōu)化目標(biāo)的層次社區(qū)劃分算法—FN算法,該算法以迭代的方式貪婪地合并模塊度增量最大的社區(qū),直到所有節(jié)點(diǎn)融合為一個社區(qū)時為止.然而,FN算法存在時間復(fù)雜度較高問題.為了解決這個問題,Clauset等人[8]在FN算法基礎(chǔ)上提出FG算法,優(yōu)化了社區(qū)合并操作并使用堆數(shù)據(jù)結(jié)構(gòu)存儲網(wǎng)絡(luò)數(shù)據(jù),進(jìn)一步提高了FN算法性能.Fortunato等人[10]提出Louvain算法,該算法在每輪迭代中僅合并模塊度增量最大的鄰居社區(qū)直至模塊度增量不為正時為止.

為了解決FN算法的準(zhǔn)確率問題,付常雷[11]提出一種改進(jìn)FN算法的層次社區(qū)發(fā)現(xiàn)算法.該算法引入社團(tuán)貢獻(xiàn)度,以社團(tuán)貢獻(xiàn)度作為算法的優(yōu)化目標(biāo)來劃分層次社區(qū).陳東明[12]提出GD算法.該算法引入社團(tuán)密合度,以社團(tuán)密合度作為優(yōu)化目標(biāo),來劃分層次社區(qū).Jin等人等人[13]提出ModMRF算法.該算法將模塊度求解問題轉(zhuǎn)化為馬爾可夫圖形概率模型來劃分層次社區(qū).Du等人[14]提出Q-HAM算法.該算法基于模塊度增量進(jìn)行譜聚類來劃分層次社區(qū).Yuan等人[15]提出MSM算法.該算法將最大化模塊度方法轉(zhuǎn)化為子集識別問題,以模塊度模型為基礎(chǔ),提出一種非凸函數(shù)模型,并迭代地求解出該函數(shù)的最小值來劃分層次社區(qū).此外,邊介數(shù)[16]、節(jié)點(diǎn)相似度[17-19]、最優(yōu)模塊密度[21-23]等也被引入基于模塊度優(yōu)化的層次社區(qū)劃分算法中.

盡管針對基于模塊度優(yōu)化的層次社區(qū)發(fā)現(xiàn)算法[20]準(zhǔn)確率和效率問題開展了大量研究,但是該類算法在性能和社區(qū)劃分質(zhì)量方面存在的問題仍是開放問題.

3 問題分析

本文使用無向圖G=(V,E)來描述復(fù)雜網(wǎng)絡(luò).V表示網(wǎng)絡(luò)的節(jié)點(diǎn)集合,記為V={vi|i=1,2,…,n},n為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量.E表示邊集合,記為E={(vi,vj)|vi∈V,vj∈Vandi≠j}.該網(wǎng)絡(luò)的社區(qū)劃分結(jié)果可表示為C={Ci|i=1,2,…,r,Ci?G},r表示社區(qū)數(shù)量.在該社區(qū)集合中,Ci表示第i個社區(qū)劃分,且Ci=(Vi,Ei).在Ci中,Vi和Ei分別表示該社區(qū)中的節(jié)點(diǎn)集合和邊集合,且Vi?V,Ei?E.

模塊度是衡量社區(qū)劃分質(zhì)量的重要指標(biāo)之一.基于模塊度優(yōu)化的社區(qū)劃分方法以模塊度為優(yōu)化函數(shù),以迭代的方式進(jìn)行社區(qū)合并,直至滿足收斂條件.在每輪迭代中,僅合并模塊度增量最大的2個社區(qū).由于每輪迭代合并的社區(qū)數(shù)量有限,算法要經(jīng)過多輪次的迭代才能收斂,收斂速度較慢.按照上述社區(qū)合并方式,圖1(a)所示的社交網(wǎng)絡(luò)要經(jīng)過5輪迭代社區(qū)合并操作才會收斂.若每輪迭代中合并模塊度增量最大的2組社區(qū),則該網(wǎng)絡(luò)只需經(jīng)過1輪迭代社區(qū)劃分就可結(jié)束,劃分結(jié)果如圖1(b)所示.

(1)

(a) 每輪迭代合并模塊度增量最大的一組社區(qū) (b) 每輪迭代合并模塊度增量最大的兩組社區(qū)圖1 收斂速度分析(Ci,j表示第i輪迭代中合并生成的第j個社區(qū))Fig.1 Convergence rate analysis( Ci,j presents the j-th community merged in iteration i)

式(1)展示了模塊度模型.在該式中,Q為模塊度,C為社區(qū)集合,m表示網(wǎng)絡(luò)總邊數(shù),eCi表示社區(qū)Ci內(nèi)部邊數(shù),dCi表示社區(qū)Ci內(nèi)部節(jié)點(diǎn)度數(shù)的總和.根據(jù)該模型,社區(qū)內(nèi)部的連接越緊密、社區(qū)之間的連接越稀疏,模塊度越大.故而,基于模塊度優(yōu)化的社區(qū)劃分方法易將連接緊密的社區(qū)合并為一個新社區(qū).然而,除了社區(qū)之間連接的緊密性,社區(qū)之間的相似性也是判斷兩個社區(qū)是否能融合為一個社區(qū)的重要依據(jù)之一[24].僅依據(jù)模塊度合并社區(qū)容易將相似性較強(qiáng)的社區(qū)合并到不同的社區(qū)中,降低社區(qū)劃分的合理性.以圖2所示的網(wǎng)絡(luò)為例,如果只根據(jù)模塊度進(jìn)行層次社區(qū)劃分,則圖2中的網(wǎng)絡(luò)將劃分為虛線所示的3個社區(qū);如果在社區(qū)合并過程中同時考慮模塊度和相似性,則圖2中的網(wǎng)絡(luò)將劃分為實線所示的3個社區(qū).而且后一種劃分結(jié)果的模塊度更高.因此,在合并社區(qū)的過程中只考慮模塊度是不合理的.

圖2 社區(qū)劃分分析Fig.2 Community detection analysis

4 加權(quán)模塊度增量引導(dǎo)下的層次社區(qū)發(fā)現(xiàn)算法

針對基于模塊度優(yōu)化的層次社區(qū)發(fā)現(xiàn)算法在社區(qū)劃分結(jié)果合理性和收斂速度方面存在的問題,本文提出加權(quán)模塊度增量引導(dǎo)下的層次社區(qū)發(fā)現(xiàn)算法,在社區(qū)劃分過程中同時結(jié)合社區(qū)之間的模塊度增量和社區(qū)之間的相似性進(jìn)行社區(qū)合并,以提高社區(qū)劃分的合理性.為了提高收斂速度引入可調(diào)合并閾值,根據(jù)可調(diào)合并閾值動態(tài)決定每輪迭代中社區(qū)合并的數(shù)量.

4.1 加權(quán)模塊度增量模型

基于模塊度優(yōu)化的層次社區(qū)發(fā)現(xiàn)算法在社區(qū)合并過程中只考慮社區(qū)之間的連接強(qiáng)度而忽略社區(qū)之間相似性,這往往會降低社區(qū)劃分的合理性.針對這一問題,本文方法擬在社區(qū)合并過程中同時考慮社區(qū)之間的連接強(qiáng)度和社區(qū)之間的相似性.為實現(xiàn)這一目標(biāo),引入了加權(quán)模塊度增量模型對兩個社區(qū)之間的連接強(qiáng)度和相似性進(jìn)行度量;在社區(qū)合并過程中,優(yōu)先合并加權(quán)模塊度增量最大的社區(qū).

為了度量社區(qū)之間的相似性,引入了社區(qū)相似度權(quán)重.社區(qū)相似度權(quán)重根據(jù)社區(qū)之間的共同鄰居計算社區(qū)間的相似程度.兩社區(qū)具有的共同鄰居社區(qū)越多,這兩個社區(qū)之間的相似性就越大;反之亦然.兩個社區(qū)越相似,在較高的劃分層次中融合為一個社區(qū)的可能性也越大.社區(qū)相似度權(quán)重的定義描述如下:

定義1.社區(qū)相似度權(quán)重.描述兩個社區(qū)之間的相似程度,記為ws.

(?Ci)Ci∈C(?Cj)Cj∈C,i≠j,Ci與Cj之間的相似性記為ws(Ci,Cj),可根據(jù)式(2)計算.在該式中,r表示社區(qū)數(shù)量,sC(Ci,Cj)根據(jù)式(3)計算.在式(3)中,NC(Ci)表示Ci的鄰居社區(qū)集合.

(2)

(3)

為了達(dá)到同時根據(jù)社區(qū)之間的連接強(qiáng)度和相似性進(jìn)行社區(qū)合并的目標(biāo),在社區(qū)相似度和模塊度增量的基礎(chǔ)之上定義了加權(quán)模塊度增量.

定義2.加權(quán)模塊度增量.從相似度和連接強(qiáng)度兩個方面入手度量兩個社區(qū)合并后的增益,記為ΔQw.

(?Ci)Ci∈C,(?Cj)Cj∈C,i≠j,Ci與Cj的加權(quán)模塊度增量記為ΔQw(Ci,Cj),根據(jù)式(4)計算.在該式中ΔQ(Ci,Cj)表示Ci與Cj合并后的模塊度增量,可根據(jù)文獻(xiàn)[7]中的方法計算.

ΔQw(Ci,Cj)=ΔQ(Ci,Cj)×ws(Ci,Cj)

(4)

4.2 社區(qū)合并策略

在基于加權(quán)模塊度增量進(jìn)行社區(qū)合并時,每次只選擇加權(quán)模塊度增量最大的社區(qū)進(jìn)行合并.這會從兩個方面制約算法的性能:1)由于每次迭代只能合并少量社區(qū),算法的收斂速度較慢;2)在每次迭代時都要進(jìn)行模塊度增量排序以篩選出模塊度增量最大的社區(qū)組合,迭代次數(shù)越多,排序次數(shù)越多,算法的復(fù)雜度越大.為了避免上述問題,本文引入了可調(diào)合并閾值,結(jié)合加權(quán)模塊度增量,動態(tài)決定每輪迭代中可以合并的社區(qū)數(shù)量.

Mθ=θ×max(ΔQw),0<θ<1

(5)

可調(diào)合并閾值根據(jù)式(5)計算.在式(5)中,max(ΔQw)表示當(dāng)前迭代中加權(quán)模塊度增量的最大值,θ為調(diào)節(jié)參數(shù).若θ取1,則只合并加權(quán)模塊度增量最大的社區(qū),這與已有算法的合并策略相同;若θ取值0,則任意兩個社區(qū)都可合并,合并操作失去意義;故本文將θ的取值范圍限定為(0,1).同時,為了便于描述社區(qū)的合并過程,定義了待合并社區(qū)集合描述需要合并的社區(qū)組合,并在待合并社區(qū)集合的基礎(chǔ)上定義了待合并社區(qū)集合之間可能存在的合并關(guān)系.為了加快算法收斂,存在合并關(guān)系的多個待合并社區(qū)集合中包含的社區(qū)也要進(jìn)行合并.

定義3.待合并社區(qū)集合.(?Ci)Ci∈C,(?Cj)Cj∈C,i≠j,若ΔQw(Ci,Cj)≥Mθ,則Ci和Cj構(gòu)成待合并社區(qū)集合,記為Cm={Ci,Cj}.

在待合并社區(qū)集合及其合并關(guān)系的基礎(chǔ)上,本文提出了加權(quán)模塊度增量優(yōu)化的層次社區(qū)發(fā)現(xiàn)算法,該算法采用的社區(qū)合并策略描述如下:

合并策略2.給定一個待合并社區(qū)集合,若該集合與其它待合并社區(qū)集合存在合并關(guān)系,則將該集合以及與該社區(qū)集合存在合并關(guān)系的所有待合并社區(qū)集合中不重復(fù)的社區(qū)進(jìn)行合并.

合并策略3.若Mθ≤0,則社區(qū)合并結(jié)束.

以圖3所示網(wǎng)絡(luò)為例說明根據(jù)合并策略1-3合并社區(qū)的過程.本例中采用的假設(shè)條件描述如下:1)初始的社區(qū)劃分為每個節(jié)點(diǎn)為一個單獨(dú)社區(qū)(節(jié)點(diǎn)的編號即為社區(qū)的編號),2)θ=0.8.

圖3 社區(qū)合并過程Fig.3 Community mergence process

在第3輪和第4輪迭代中通過合并關(guān)系生成的新社區(qū)分別記為C3,0和C4,0,C3,0包含的節(jié)點(diǎn)為v0、v1、v2和v3,C4,0包含的節(jié)點(diǎn)為v4、v6、v6和v7.在第5輪迭代時,由于Mθ<0,算法收斂.若每次只合并模塊度增量最大的社區(qū),則需要7輪迭代算法才能收斂.

4.3 算法描述

加權(quán)模塊度增量引導(dǎo)下的層次社區(qū)發(fā)現(xiàn)算法首先對網(wǎng)絡(luò)進(jìn)行初始社區(qū)劃分,然后以迭代的方式進(jìn)行社區(qū)合并,直至滿足收斂條件.在每輪迭代中,先計算社區(qū)之間的加權(quán)模塊度增量,然后更新可調(diào)合并閾值,最后根據(jù)合并策略1-3執(zhí)行具體的社區(qū)合并操作.以加權(quán)模塊度增量進(jìn)行層次社區(qū)劃分的詳細(xì)描述如算法1所示.

算法1.加權(quán)模塊度增量引導(dǎo)下的層次社區(qū)發(fā)現(xiàn)算法.

輸入:G=(V,E)

輸出:社區(qū)集合C

1.對G進(jìn)行初始化社區(qū)劃分

2.根據(jù)劃分結(jié)果生成加權(quán)模塊度增量矩陣M

3.獲取M中的最大元素,并計算Mθ的初始值

4.While(Mθ≤0)

5.構(gòu)建待合并社區(qū)集合

6.根據(jù)合并策略1～3執(zhí)行合并操作,更新C

7.根據(jù)集合C更新矩陣M

8.獲取M中的最大元素,并更新Mθ

9. End while

10. ReturnC

假設(shè)1)網(wǎng)絡(luò)包含的總節(jié)點(diǎn)數(shù)為n,2)每輪迭代中平均有h(h

5 實 驗

為了驗證本文算法的正確性和有效性,在多個真實數(shù)據(jù)集和人工數(shù)據(jù)集上開展了多項對比實驗,按照相同的評價指標(biāo)將本文算法的實驗結(jié)果和多個經(jīng)典算法的實驗結(jié)果進(jìn)行比較分析.

5.1 實驗數(shù)據(jù)集及環(huán)境設(shè)置

實驗共采用了7個真實數(shù)據(jù)集和9個人工數(shù)據(jù)集.真實數(shù)據(jù)集來自美國斯坦福大學(xué)提供的社交網(wǎng)絡(luò)數(shù)據(jù)集(1)http://snap.stanford.edu/data/和密歇根大學(xué)Newman教授提供的社交網(wǎng)絡(luò)數(shù)據(jù)集(2)http://www-personal.umich.edu/～mejn/netdata/.表1展示了7個真實數(shù)據(jù)集的信息,包括節(jié)點(diǎn)、邊的含義和具體數(shù)量.

表1 真實數(shù)據(jù)集Table 1 Real datasets

本次實驗采用的人工數(shù)據(jù)集根據(jù)LFR基準(zhǔn)模型[25]生成,具體生成參數(shù)配置如下:節(jié)點(diǎn)總數(shù)N=10000,節(jié)點(diǎn)的最大度maxk=50,節(jié)點(diǎn)的平均度k=20,社區(qū)中節(jié)點(diǎn)數(shù)量的最大值maxc=100,社區(qū)中節(jié)點(diǎn)數(shù)量的最小值minc=20,μ值取從0.1開始按0.05遞增的9個值,共生成9個不同結(jié)構(gòu)的人工數(shù)據(jù)集,分別記為μ-0.1、μ-0.15、μ-0.2、μ-0.25、μ-0.3、μ-0.35、μ-0.4、μ-0.45和μ-0.5.

實驗采用了4項與模塊度相關(guān)的對比算法,分別是FN算法、FG算法.MSM算法和GD算法.實驗中采用的評價指標(biāo)有3項,分別是執(zhí)行時間、模塊度(Q)和標(biāo)準(zhǔn)互信息(NMI)[26].執(zhí)行時間和模塊度指標(biāo)適用于所有數(shù)據(jù)集,NMI只適用于人工數(shù)據(jù)集.所有的實驗項目均在相同的實驗平臺上進(jìn)行.該實驗平臺采用的處理器為Intel i7-7700K4.2GHz,內(nèi)存容量為32GB,操作系統(tǒng)為Ubuntu 20.04.2.所有算法均采用python語言實現(xiàn).為了更具一般性,所有算法在各數(shù)據(jù)集上都要獨(dú)立運(yùn)行100次,計算平均結(jié)果.

5.2 實驗結(jié)果分析

本文算法引入了可調(diào)合并閾值,利用可調(diào)合并閾值控制每輪迭代中可以合并的社區(qū)數(shù)量.因此,Mθ的設(shè)置對本文算法的性能至關(guān)重要.Mθ的值由調(diào)節(jié)參數(shù)θ和當(dāng)前迭代中模塊度的最大值決定,而后者與數(shù)據(jù)集和社區(qū)劃分共同決定.故而,對Mθ的調(diào)節(jié)要通過對θ的調(diào)節(jié)實現(xiàn).在當(dāng)前迭代中模塊度最大值一定的情況下,θ值越小,Mθ的值越小,每輪迭代中合并的社區(qū)數(shù)量就越多.所以,θ值設(shè)置的越小,算法的收斂速度相應(yīng)越快.為了在提高收斂速度的同時保證社區(qū)劃分的質(zhì)量,將θ設(shè)置為從0.1開始并以0.1遞增的9個不同的值,比較θ取不同值時本文算法在各數(shù)據(jù)集上劃分社區(qū)的質(zhì)量表2、圖4分別展示了本文算法在θ取上述不同值時在真實數(shù)據(jù)集和人工數(shù)據(jù)集上的社區(qū)劃分質(zhì)量.通過權(quán)衡算法的執(zhí)行時間和社區(qū)劃分T質(zhì)量,在Karate、Football、Physicians、Email、Facebook、CA以及PH共7個真實數(shù)據(jù)集上,θ的值分別設(shè)置為0.3、0.4、0.3、0.5、0.3、0.4和0.5;在9個人工數(shù)據(jù)集上,θ的值統(tǒng)一設(shè)置為0.2.

表2 本文算法在真實數(shù)據(jù)集獲得的模塊度值Table 2 Q of our method in the real datasets

圖4 本文算法在人工數(shù)據(jù)集獲得的模塊度值和NMI值Fig.4 Q and NMI of our method in the artificial datassets

提高社區(qū)劃分的速度是本文算法設(shè)計的一個重要目標(biāo).為了評估本文算法的社區(qū)劃分速度,以執(zhí)行時間為評價指標(biāo)比較了各算法在真實數(shù)據(jù)集和人工數(shù)據(jù)集上的性能,具體結(jié)果如圖5所示,本文算法的執(zhí)行時間較于其他對比算法都是最短的.在真實數(shù)據(jù)集上,本文算法的執(zhí)行時間平均是FN算法、FG算法、MSM算法和GD算法執(zhí)行時間的6.99%、20.99%、29.07%和34.24%.在從μ-0.1到μ-0.5的9個人工數(shù)據(jù)集上,本文算法的執(zhí)行時間平均是FN算法、FG算法、MSM算法和GD算法執(zhí)行時間的7.09%、17.39%、19.96%和21.01%.這些實驗結(jié)果表明,本文算法根據(jù)可調(diào)合并閾值動態(tài)調(diào)節(jié)合并社區(qū)數(shù)量的機(jī)制,可以加快算法收斂,提高算法的執(zhí)行速度.

圖5 算法執(zhí)行時間比較Fig.5 Running time comparison

保證并盡可能提高社區(qū)劃分的質(zhì)量是本文算法設(shè)計的另一個重要目標(biāo).為了評估本文算法的社區(qū)劃分質(zhì)量,以模塊度和NMI作為評價指標(biāo)比較了各算法在真實數(shù)據(jù)集和人工數(shù)據(jù)集上的社區(qū)劃分結(jié)果,結(jié)果如表3和圖6所示.表3展示了各算法在真實數(shù)據(jù)集上的模塊度值.由表可知,在真實數(shù)據(jù)集上,本文算法獲得的模塊度值均大于各對比算法獲得的模塊度值.在平均情況下,本文算法的模塊度值相比于FN算法、FG算法、MSM算法和GD算法的模塊度值分別提高了10.32%、10.32%、4.81%和3.96%.在最好情況下,本文算法獲得的模塊度值分別是這4個算法的 1.14倍、1.14倍、1.15倍和1.07倍.

表3 真實數(shù)據(jù)集模塊度值比較Table 3 Q comparison in the real datasets

圖6 算法在人工數(shù)據(jù)集下的模塊度和NMI值比較Fig.6 Q and NMI comparison in the artificial datasets

圖6(a)展示了各算法在人工數(shù)據(jù)集上的模塊度值.由圖可知,本文算法在人工數(shù)據(jù)集獲得的模塊度值也大于各對比算法.在平均情況下,本文算法的模塊度值相比于FN算法、FG算法、MSM算法和GD算法的模塊度值分別提高了18.73%、18.73%、7.51%和10.1%.圖6(b)展示了各算法在人工數(shù)據(jù)集上獲得NMI值.由圖可知,本文算法在人工數(shù)據(jù)集獲得的NMI值均大于各對比算法獲得的NMI值.在平均情況下,本文算法獲得NMI值與FN算法、FG算法、MSM算法和GD算法相比分別提高了27.54%、27.54%、24.92%和31.41%.

以上結(jié)果表明,在給定的真實數(shù)集和人工數(shù)據(jù)集上,本文算法引入的基于加權(quán)模塊度增量優(yōu)化的層次社區(qū)劃分策略可以達(dá)到保障并提高社區(qū)劃分質(zhì)量的目標(biāo).

6 總 結(jié)

本文主要關(guān)注基于模塊度優(yōu)化的層次社區(qū)劃分算法存在的收斂速度問題和劃分結(jié)果不合理問題.針對這兩個問題,提出了加權(quán)模塊度增量引導(dǎo)下的層次社區(qū)發(fā)現(xiàn)算法.該算法引入了可調(diào)合并閾值控制每輪迭代中可以合并的社區(qū)數(shù)量,以此來提高算法的收斂速度.該算法還定義了社區(qū)相似度權(quán)重,并結(jié)合模塊度增量構(gòu)建加權(quán)模塊度增量,通過優(yōu)化加權(quán)模塊度增量來發(fā)現(xiàn)層次社區(qū),以此來改善社區(qū)發(fā)現(xiàn)結(jié)果的合理性.在真實網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上的實驗結(jié)果驗證了本文方法的正確性和有效性.