基于多目標(biāo)自適應(yīng)Memetic算法的復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)

梁世嬌,柴爭(zhēng)義

(天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,天津 300387)

許多現(xiàn)實(shí)世界的復(fù)雜系統(tǒng)都可以表示為網(wǎng)絡(luò)，例如：萬(wàn)維網(wǎng)、科學(xué)家協(xié)作網(wǎng)、蛋白質(zhì)生物網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等[1].復(fù)雜網(wǎng)絡(luò)有很多特性，比如：小世界特性、無(wú)標(biāo)度特性[2].但近幾年的研究表明，除了上述2個(gè)特性以外，社區(qū)結(jié)構(gòu)成為另一個(gè)重要的揭示網(wǎng)絡(luò)復(fù)雜結(jié)構(gòu)的特性[3].一般來(lái)說(shuō)，在社區(qū)內(nèi)部，節(jié)點(diǎn)與節(jié)點(diǎn)的連接較為緊密，而在社區(qū)之間，節(jié)點(diǎn)的連接就相對(duì)稀疏[4].對(duì)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的研究，主要是利用各種社區(qū)檢測(cè)方法，挖掘出復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，分析出網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特性，從而更好地理解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能.

很多研究領(lǐng)域的學(xué)者對(duì)復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)進(jìn)行大量深入的研究，一些經(jīng)典高效的網(wǎng)絡(luò)社區(qū)檢測(cè)算法被相繼提出，主要有2大類[5]：① 基于啟發(fā)式的網(wǎng)絡(luò)社區(qū)檢測(cè)方法，該方法是將社區(qū)檢測(cè)問(wèn)題定義為啟發(fā)式規(guī)則的設(shè)計(jì)問(wèn)題，具有代表性的是Girvan-Newman(GN)算法[6]、Newman貪婪算法(CNM)[7]等；② 基于優(yōu)化策略的社區(qū)檢測(cè)方法，相比于第1類，該類方法在社區(qū)檢測(cè)速度和精度上有了很大的提高，得到了研究者更廣泛的關(guān)注[5]，其核心思想是將網(wǎng)絡(luò)社區(qū)檢測(cè)問(wèn)題抽象成一個(gè)優(yōu)化問(wèn)題，最具代表性的是基于模塊度的優(yōu)化[6].

模塊度函數(shù)本身存在分辨率限制問(wèn)題[3].即當(dāng)網(wǎng)絡(luò)社區(qū)的規(guī)模小到一定程度時(shí)，只是單純的優(yōu)化模塊度函數(shù)無(wú)法發(fā)現(xiàn)潛在的社區(qū)結(jié)構(gòu)，也就不能得到穩(wěn)定高效的網(wǎng)絡(luò)劃分.為了解決多分辨率問(wèn)題，研究者分別提出了多尺度模塊度[7]、模塊度密度[8]和擴(kuò)展的模塊度密度[9]等優(yōu)化目標(biāo).擴(kuò)展的模塊度密度通過(guò)調(diào)節(jié)參數(shù)λ的值實(shí)現(xiàn)對(duì)不同分辨率下的網(wǎng)絡(luò)社區(qū)的檢測(cè)，取得了較好的檢測(cè)效果，但需要不斷地調(diào)節(jié)參數(shù)，多次運(yùn)行程序.為了更有效地表征社區(qū)結(jié)構(gòu)，研究者將多目標(biāo)引入到網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測(cè)中，將社區(qū)劃分問(wèn)題看成是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，并從中找到目標(biāo)間的折中解，每個(gè)解代表著一種網(wǎng)絡(luò)社區(qū)劃分結(jié)果.從而達(dá)到一次運(yùn)行程序，便可得到網(wǎng)絡(luò)的多分辨結(jié)構(gòu).比較有代表性的算法有MOCD[8],MOGA-Net[8],Meme-Net[9]等.

為了進(jìn)一步提高社區(qū)檢測(cè)的精準(zhǔn)度，筆者提出一種基于自適應(yīng)Memetic算法的復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)算法(A-Meme)，充分利用進(jìn)化算法全局搜索和Memetic算法局部搜索的優(yōu)勢(shì)，并設(shè)計(jì)一種改進(jìn)的動(dòng)態(tài)自適應(yīng)策略調(diào)整交叉和變異概率，將其應(yīng)用于人工合成和真實(shí)網(wǎng)絡(luò)上，驗(yàn)證該算法的高效性.

1 多目標(biāo)復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)問(wèn)題建模

1.1 社區(qū)的定義

把復(fù)雜網(wǎng)絡(luò)建模為一個(gè)無(wú)向圖(graph)，表示為G=(V,E)，其中：V為節(jié)點(diǎn)的集合；E為邊的集合.在無(wú)向圖中，節(jié)點(diǎn)i的度表示為與其相連的邊數(shù)，并記作ki.用鄰接矩陣去存儲(chǔ)網(wǎng)絡(luò)的真實(shí)拓?fù)浣Y(jié)構(gòu)，其鄰接矩陣A是一個(gè)元素取值僅為0和1的對(duì)稱網(wǎng)絡(luò).當(dāng)元素aij取值為0時(shí)，表示兩節(jié)點(diǎn)間不存在連接；當(dāng)aij取值為1時(shí)，表示兩節(jié)點(diǎn)間存在邊連接.

1.2 目標(biāo)函數(shù)

M.GIRVEN等[6]提出了一個(gè)衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)模塊度(Q)的概念，給出了模塊度的一般定義形式：

(1)

式中：m為社區(qū)個(gè)數(shù)；li為i所在社區(qū)所有節(jié)點(diǎn)間的總的邊數(shù)；L為整個(gè)網(wǎng)絡(luò)中所有邊的數(shù)量；di為i所在社區(qū)內(nèi)所有節(jié)點(diǎn)的度之和.

對(duì)于模塊度Q來(lái)說(shuō)，Q值越大，劃分的社區(qū)結(jié)構(gòu)越好.但已有研究表明模塊度優(yōu)化存在分辨率限制問(wèn)題，對(duì)揭示復(fù)雜網(wǎng)絡(luò)的多分辨結(jié)構(gòu)，模塊度密度這一指標(biāo)要優(yōu)于模塊度.模塊度密度定義為

(2)

另外，為了更好地揭示網(wǎng)絡(luò)的多分辨結(jié)構(gòu)，還定義了一個(gè)擴(kuò)展的模塊度密度指標(biāo)Dλ.λ作為一個(gè)調(diào)節(jié)參數(shù)，可以得到網(wǎng)絡(luò)的多分辨結(jié)構(gòu).擴(kuò)展的模塊度密度一般定義為

(3)

式中：λ的取值范圍是[0,1].

通常，當(dāng)λ減小時(shí)，優(yōu)化Dλ趨向于將網(wǎng)絡(luò)劃分為小的社區(qū)結(jié)構(gòu)，當(dāng)λ的值增加時(shí)，優(yōu)化Dλ趨向于將網(wǎng)絡(luò)劃分為較大的社區(qū)結(jié)構(gòu).通過(guò)不斷地對(duì)參數(shù)λ進(jìn)行調(diào)節(jié)，得到不同分辨率下的網(wǎng)絡(luò)社區(qū)劃分結(jié)構(gòu).將復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)劃分看作是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，可以實(shí)現(xiàn)在一次程序運(yùn)行的情況下，無(wú)需調(diào)節(jié)控制參數(shù)，便可得到不同分辨率下的網(wǎng)絡(luò)劃分結(jié)果.因此，根據(jù)已有的研究[5]，將其建模為一個(gè)多目標(biāo)優(yōu)化問(wèn)題，即優(yōu)化其中一個(gè)目標(biāo)趨向于將網(wǎng)絡(luò)劃分為較大的社區(qū)結(jié)構(gòu)，優(yōu)化另一個(gè)目標(biāo)趨向于將網(wǎng)絡(luò)劃分為較小的社區(qū)結(jié)構(gòu).

目標(biāo)函數(shù)選取λ=0.5時(shí)，Dλ的形式為

(4)

引入函數(shù)RA(ratio association)[10]，該函數(shù)可表示為

(5)

從式(5)可以看出：RA值越大，表明社區(qū)內(nèi)部的連接越緊密，因此，最大化RA是最大化社區(qū)內(nèi)部的連接.引入另一個(gè)目標(biāo)函數(shù)RC(ratio cut)[10]，主要針對(duì)的是社區(qū)間的連接情況，該函數(shù)可表示為

(6)

式(6)表示每個(gè)社區(qū)同網(wǎng)絡(luò)中其他節(jié)點(diǎn)的平均連接密度之和，社區(qū)檢測(cè)的目標(biāo)是為了減小不同社區(qū)之間的連接代價(jià).從式(6)可以看出：RC值越小，社區(qū)間的連接越稀疏，因此，需要最小化RC來(lái)減少社區(qū)間連接代價(jià).由上可見(jiàn)，RA和RC是2個(gè)相互沖突的目標(biāo)函數(shù)，為了方便描述，將RA的指標(biāo)MRA(modified ratio association)[10]定義如下：

(7)

式中：n為網(wǎng)絡(luò)頂點(diǎn)總數(shù).

綜上，該算法的多目標(biāo)優(yōu)化的2個(gè)目標(biāo)函數(shù)定義為

(8)

2 動(dòng)態(tài)自適應(yīng)Memetic(A-Meme)算法

2.1 算法框架

動(dòng)態(tài)自適應(yīng)Memetic算法(A-Meme)如下：

輸入：Gmax,Spop,Spool,Pc,Pm

Step1：P←GenerateInitalPopulation(Spop)

Step2：repeat

Step3:Pparent←Selection(Spool)

Step4:Pchild←GeneticOperation(Pparent,Pc,Pm)

Step5:Pnew←LocalSearch(Pchild)

Step6:P←UpdatePopulation(P,Pnew)

Step7：untilTerminationCriterion(Gmax)

輸出：P，通過(guò)對(duì)個(gè)體的解碼，得到不同分辨率下的網(wǎng)絡(luò)劃分結(jié)構(gòu).

其中：Gmax為種群最大迭代次數(shù)；Spop為種群規(guī)模；Spool為交配種群；Pc為交叉概率；Pm為變異概率；GenerateInitialPopulation()函數(shù)負(fù)責(zé)種群初始化；Selection()函數(shù)負(fù)責(zé)選擇種群交配的父代個(gè)體；GeneticOperation()函數(shù)負(fù)責(zé)執(zhí)行交叉和變異操作；Loca-lSearch()函數(shù)負(fù)責(zé)執(zhí)行局部搜索操作；UpdatePopulation()函數(shù)負(fù)責(zé)更新種群；TerminationCriterion()函數(shù)負(fù)責(zé)計(jì)算種群迭代次數(shù)；Pparent，Pchild，Pnew分別為父代、子代、新種群劃分.

2.2 種群初始化

社區(qū)檢測(cè)算法大多采用基于鄰域的個(gè)體表示方式，種群中每個(gè)個(gè)體包含n個(gè)基因(g1,g2,…，gn)，并且每個(gè)gi可以取其鄰域內(nèi)的頂點(diǎn)作為它的值.如果頂點(diǎn)k被連接到第i個(gè)基因位，那么它可以被解釋為頂點(diǎn)i和k之間有邊連接.這就意味著，在個(gè)體解碼的過(guò)程中，這2個(gè)頂點(diǎn)會(huì)被解碼到同一個(gè)社區(qū)中.而在真實(shí)的環(huán)境中，網(wǎng)絡(luò)的社會(huì)關(guān)系受網(wǎng)絡(luò)本身的擴(kuò)散信息的影響，對(duì)這些信息進(jìn)行整理和排序，將能更好地理解用戶之間的信息交流.

對(duì)網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)處理時(shí)，采用隨機(jī)游走(Random-walker)初始化策略[8]，增強(qiáng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的同時(shí)可以更好地挖掘網(wǎng)絡(luò)內(nèi)在結(jié)構(gòu)和特性，提高初始解的精度.隨機(jī)選擇一個(gè)頂點(diǎn)作為起始點(diǎn)，根據(jù)轉(zhuǎn)移概率矩陣Pt，一個(gè)walker將隨機(jī)移動(dòng)到其鄰域內(nèi)的一個(gè)頂點(diǎn).轉(zhuǎn)移矩陣中的元素Pij表示邊(i,j)的權(quán)重值和頂點(diǎn)i相關(guān)聯(lián)的所有邊的權(quán)重總值之比.轉(zhuǎn)移概率可以表示為Pij=1/di，其中，di為節(jié)點(diǎn)i的度.對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)i，假定j是其鄰域內(nèi)的一個(gè)節(jié)點(diǎn)，如果滿足條件Pij≥Pik，?k∈Neighbor(i)，則?稱j為頂點(diǎn)i的一個(gè)緊密連接點(diǎn).在最后的解碼過(guò)程中，這兩個(gè)頂點(diǎn)被劃到同一個(gè)社區(qū)的幾率就會(huì)很大.

采用Random-walker初始化策略的流程如下：

輸入：A

Step1：計(jì)算Pt

Step2：fori=1→ndo

forj=1→ndo

Pj,Neighbor(j)=sort(Pj,Neighbor(j))

m←max(Pj,Neighbor(j))

Population(i,j)←m

end for

end for

輸出：更新種群

其中：A為網(wǎng)絡(luò)的鄰接矩陣；Neighbor(j)為節(jié)點(diǎn)j的鄰域.

2.3 交叉和變異

2.3.1交叉操作

傳統(tǒng)的單點(diǎn)交叉會(huì)造成父代個(gè)體X和Y中的元素重復(fù)，對(duì)此，作了如下變化，對(duì)種群中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)，依照設(shè)定的交叉概率Pc，對(duì)每一對(duì)相互配對(duì)的父代個(gè)體X和Y，按照下面的公式進(jìn)行算術(shù)交叉操作，產(chǎn)生2個(gè)新的個(gè)體X′和Y′，即

X′=rX+(1-r)Y,

(9)

Y′=rY+(1-r)X,

(10)

式中：X′和Y′為新產(chǎn)生的子代個(gè)體；r為(0,1)之間的隨機(jī)數(shù).

假設(shè)隨機(jī)數(shù)r為0.5，交叉算子具體操作如表1所示.

表1 交叉算子具體操作表

個(gè)體x,y在第5處單點(diǎn)交叉產(chǎn)生X,Y，造成X中第3處和第9處元素相同，Y中第5處和第7處元素相同.然后根據(jù)式(9)，(10)和隨機(jī)數(shù)r，得到子代X′和Y′，保證候選解中的元素彼此不同.

2.3.2變異操作

進(jìn)化種群保持多樣性是遺傳算法有效運(yùn)行的前提條件，為了保持群體有足夠多的不同個(gè)體，并且保證較快的收斂速度，這就要求種群的個(gè)體盡快向最優(yōu)的方向靠攏，但這樣會(huì)不可避免地降低種群的多樣性，使種群陷入局部最優(yōu)，因此選擇理想的變異方式對(duì)種群來(lái)說(shuō)至關(guān)重要[10].文獻(xiàn)[11]提出了一種自適應(yīng)變異策略，將交叉概率和變異概率改為在個(gè)體的平均適應(yīng)度值和最大適應(yīng)度值之間去調(diào)整，但這個(gè)策略的缺陷就是考慮了適應(yīng)度值較差的個(gè)體(此類個(gè)體大多將被淘汰)，并不能真正反映優(yōu)秀個(gè)體的趨同程度.因此筆者將變異概率改為種群最大適應(yīng)度值fmax與超過(guò)平均適應(yīng)度值的所有個(gè)體的適應(yīng)度值的平均值maxfAvg的差值，即

Δf=fmax-maxfAvg.

(11)

式(11)可以實(shí)時(shí)監(jiān)控種群個(gè)體的趨同程度，動(dòng)態(tài)自適應(yīng)調(diào)整交叉和變異概率.在進(jìn)化開(kāi)始階段，交叉概率需要選大一些，變異概率選小一些，這樣的粗略搜索過(guò)程有利于保持種群的多樣性.而在進(jìn)化后期，則需要進(jìn)行細(xì)致搜索，防止破壞最優(yōu)解，加快收斂速度，這時(shí)交叉概率應(yīng)該選小一些，變異概率應(yīng)該大一些.這種分階段動(dòng)態(tài)變化趨勢(shì)與Logistic函數(shù)的變化趨勢(shì)相似[11].所以，基于Logistic函數(shù)，對(duì)種群的交叉和變異概率作了調(diào)整.相應(yīng)的動(dòng)態(tài)自適應(yīng)交叉和變異概率分別定義為

(12)

(13)

式中：k1,k2≥0.

由式(12)，(13)得0.5≤Pc≤1.0，0

2.4 局部搜索

Memetic算法是一種將進(jìn)化算法和局部搜索相結(jié)合的混合算法，提出的是一種框架，在這個(gè)框架下，采用不同的搜索策略能夠得到不同的Memetic算法，是當(dāng)前進(jìn)化算法中發(fā)展非?？斓囊粋€(gè)算法[10].Memetic算法搜索的精準(zhǔn)度相比傳統(tǒng)算法快幾個(gè)數(shù)量級(jí)，且能克服傳統(tǒng)遺傳算法收斂速度慢，容易陷入局部最優(yōu)的缺陷.局部搜索是在種群全局搜索之后進(jìn)行的搜索操作，以適應(yīng)度值作為優(yōu)化函數(shù)進(jìn)行局部?jī)?yōu)化.

局部搜索策略中采用爬山法，首先在搜索空間隨機(jī)選取一個(gè)點(diǎn)作為迭代的初始點(diǎn)，然后在其鄰域內(nèi)隨機(jī)產(chǎn)生一點(diǎn)，計(jì)算其函數(shù)值，若該點(diǎn)函數(shù)值優(yōu)于當(dāng)前點(diǎn)，則用當(dāng)前點(diǎn)替換初始點(diǎn)作為新的初始點(diǎn)繼續(xù)在鄰域內(nèi)搜索，否則繼續(xù)在鄰域隨機(jī)產(chǎn)生另一個(gè)點(diǎn)與初始點(diǎn)進(jìn)行比較，直到找到比其優(yōu)秀的點(diǎn)則終止搜索的過(guò)程.

A-Meme中多目標(biāo)優(yōu)化算法的局部搜索采用權(quán)重和的方式將2個(gè)不同的目標(biāo)函數(shù)構(gòu)成局部搜索的優(yōu)化函數(shù)，進(jìn)行如下變換：

F=θ1f1(x)+θ2f2(x),

(14)

式中：θ1=I/N，I為個(gè)體在種群中的序號(hào)，N為初始種群規(guī)模；θ2=1-θ1；f1(x)為目標(biāo)函數(shù)MRA；f2(x)為目標(biāo)函數(shù)RC.

2.5 種群更新

對(duì)初始種群P進(jìn)行初始化、交叉變異后，再進(jìn)行局部搜索選取得到新的子代種群Pnew，利用UpdatePopulation()函數(shù)更新種群，確保了最終種群的良好分布性，很好地保存了種群的多樣性.

3 試驗(yàn)評(píng)估

3.1 評(píng)價(jià)指標(biāo)

將A-Meme算法應(yīng)用到計(jì)算機(jī)合成網(wǎng)絡(luò)和4個(gè)真實(shí)網(wǎng)絡(luò)上，將其與不同算法得到的檢測(cè)結(jié)果相比較，說(shuō)明提出算法的優(yōu)越性.為了評(píng)價(jià)網(wǎng)絡(luò)劃分結(jié)果的好壞，應(yīng)用上文提到的模塊度(Q)作為評(píng)價(jià)標(biāo)準(zhǔn)的同時(shí)，采用另外一個(gè)非常有效的評(píng)價(jià)指標(biāo)NMI(normalized mutual information)[12]作為社區(qū)檢測(cè)的重要衡量指標(biāo)，可以比較客觀地評(píng)價(jià)一個(gè)社區(qū)劃分與標(biāo)準(zhǔn)劃分之間相比的準(zhǔn)確度.NMI的值域是0到1，越大代表劃分越準(zhǔn)確.對(duì)于給定的2個(gè)網(wǎng)絡(luò)劃分S1和S2，假定C表示混合矩陣，其元素值Cij表示在劃分S1社區(qū)i的同時(shí)也屬于劃分S2社區(qū)j中的節(jié)點(diǎn)個(gè)數(shù)，則劃分S1和S2的NMI可以定義為

(15)

式中：CS1，CS2分別為劃分S1，S2中的社區(qū)數(shù)目；Ci，Cj分別為C中第i行、第j列元素之和.

如果S1=S2，則NMI=1；如果S1和S2完全不同，則NMI=0.NMI越接近于1，表示2種網(wǎng)絡(luò)劃分越相似.

3.2 參數(shù)設(shè)置

A-Meme算法參數(shù)設(shè)置如下：種群最大迭代次數(shù)Gmax為50次；種群規(guī)模Spop為450個(gè)；交配種群規(guī)模Spool為Spop/2；交叉概率Pc和變異概率Pm自適應(yīng)調(diào)整.

3.3 人工合成的網(wǎng)絡(luò)

使用A.LANCICHINETTI等[13]提出的基準(zhǔn)測(cè)試網(wǎng)絡(luò).該網(wǎng)絡(luò)含有128個(gè)節(jié)點(diǎn)、4個(gè)社區(qū)，每個(gè)社區(qū)分別包含32個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的平均度為16.定義一個(gè)混合參數(shù)μ，用來(lái)控制社區(qū)外的節(jié)點(diǎn)占社區(qū)內(nèi)節(jié)點(diǎn)的比例，μ值越大，表示社區(qū)內(nèi)的節(jié)點(diǎn)和社區(qū)外其他節(jié)點(diǎn)的連接越緊密，社區(qū)結(jié)構(gòu)也就越模糊.

將μ值設(shè)置為0到0.5之間，通過(guò)調(diào)節(jié)μ值的變化生成11個(gè)網(wǎng)絡(luò)，然后使用社區(qū)劃分標(biāo)準(zhǔn)NMI來(lái)衡量真實(shí)網(wǎng)絡(luò)劃分和檢測(cè)結(jié)果之間的相似性.采用CNM，MOCD，MOGA-Net和Meme-Net算法作為比較算法.其中CNM是一個(gè)優(yōu)化模塊度指標(biāo)的經(jīng)典算法，將其變異概率設(shè)置為0.01，另外3個(gè)算法交叉和變異概率均設(shè)為0.80和0.01.將各個(gè)網(wǎng)絡(luò)進(jìn)行10次獨(dú)立試驗(yàn)，運(yùn)行結(jié)果的NMI值如圖1所示.

從圖1可以看出：當(dāng)μ≤0.2時(shí)，網(wǎng)絡(luò)結(jié)構(gòu)比較清晰，所以這5種算法都可以比較真實(shí)地反映網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)劃分；當(dāng)0.2<μ≤0.3時(shí)，MOCD，MOGA-Net和Meme-Net算法的NMI值都出現(xiàn)比較明顯的下降，不能很好反映真實(shí)的網(wǎng)絡(luò)劃分，而CNM算法和A-Meme算法仍然保持較高的NMI值；當(dāng)μ>0.4時(shí)，隨著網(wǎng)絡(luò)結(jié)構(gòu)越來(lái)越模糊，5種算法的NMI值都出現(xiàn)不同程度的下降，但相比其他算法，A-Meme算法在網(wǎng)絡(luò)結(jié)構(gòu)相對(duì)模糊時(shí)，對(duì)真實(shí)網(wǎng)絡(luò)劃分情況的反映最好.充分說(shuō)明了A-Meme算法在揭示復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)時(shí)的優(yōu)勢(shì).

3.4 真實(shí)的網(wǎng)絡(luò)

將A-Meme算法應(yīng)用到空手道俱樂(lè)部網(wǎng)絡(luò)(Karate)、期刊索引網(wǎng)絡(luò)(Journal)、海豚社交網(wǎng)絡(luò)(Dolphin)、美國(guó)足球聯(lián)盟網(wǎng)絡(luò)(Football)這4個(gè)真實(shí)的網(wǎng)絡(luò)上，將其與上述基于EA(evolutionary algorithm)算法[8-9]得到的檢測(cè)結(jié)果進(jìn)行對(duì)比.A-Meme算法在各個(gè)數(shù)據(jù)集上的試驗(yàn)結(jié)果如表2所示.表2展示了不同分辨率下的解的數(shù)量，模塊度平均值(QAvg)的最大值，NMI平均值(NMIAvg)的最大值，以及最大的Q值對(duì)應(yīng)的社區(qū)數(shù)量的平均值.從表2可以看出：對(duì)于3個(gè)網(wǎng)絡(luò)，A-Meme可以得到真實(shí)的網(wǎng)絡(luò)劃分結(jié)果(NMIAvg的最大值為1.000)，同時(shí)可以得到不同分辨率下的網(wǎng)絡(luò)劃分結(jié)構(gòu)；對(duì)于Football網(wǎng)絡(luò)，基本可以反映真實(shí)的網(wǎng)絡(luò)劃分(NMIAvg的最大值為0.976，接近1.000).

表2 真實(shí)網(wǎng)絡(luò)中A-Meme算法相關(guān)試驗(yàn)結(jié)果

基于上述試驗(yàn)數(shù)據(jù)，圖2列出了海豚社交網(wǎng)絡(luò)(Dolphin)在一次程序運(yùn)行情況下產(chǎn)生的解集，展示A-Meme算法在揭示網(wǎng)絡(luò)多分辨結(jié)構(gòu)上有著很好的效果的同時(shí)，驗(yàn)證了采用進(jìn)化多目標(biāo)求解復(fù)雜網(wǎng)絡(luò)的優(yōu)勢(shì).

圖2 海豚社交網(wǎng)絡(luò)的試驗(yàn)結(jié)果

從圖2可以看出，A-Meme算法產(chǎn)生了22個(gè)解，解2將網(wǎng)絡(luò)劃分為2個(gè)社區(qū)，解3將網(wǎng)絡(luò)劃分為3個(gè)社區(qū)，解4將網(wǎng)絡(luò)劃分為4個(gè)社區(qū)，以此類推.對(duì)于海豚社交網(wǎng)絡(luò)來(lái)說(shuō)，解2為最佳劃分，其相應(yīng)的NMI值為1.000.

為了更好地驗(yàn)證提出的算法，將A-Meme算法同上文提到的3種多目標(biāo)復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)算法(MOCD，MOGA-Net，Meme-Net)進(jìn)行對(duì)比，這3種算法同樣可以產(chǎn)生一些解集.對(duì)比算法的參數(shù)設(shè)置同上文一致，每個(gè)算法對(duì)于每個(gè)數(shù)據(jù)集都單獨(dú)運(yùn)行30次.表3給出了各個(gè)算法的執(zhí)行結(jié)果，統(tǒng)計(jì)了不同分辨率下NMI平均值的最大值(NMIAvgmax)和Q平均值的最大值(QAvgmax).從表3可以看出：對(duì)于前3個(gè)真實(shí)網(wǎng)絡(luò)(Karate，Journal，Dolphin)、A-Meme和MOGA-Net得到的NMIAvgmax均為1.000，而MOCD不能得到網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu)；對(duì)于Football網(wǎng)絡(luò)，所有方法都不能得到真實(shí)的網(wǎng)絡(luò)結(jié)構(gòu)，但是A-Meme的結(jié)果最好(NMIAvgmax=0.976)；4種算法得到的QAvgmax中，A-Meme在真實(shí)數(shù)據(jù)集上都有最好的劃分結(jié)果，從而也驗(yàn)證了算法的有效性.

表3 真實(shí)網(wǎng)絡(luò)中4種算法對(duì)比試驗(yàn)結(jié)果

4 結(jié) 論

提出的A-Meme算法利用Logistic曲線預(yù)測(cè)模型，引入動(dòng)態(tài)自適應(yīng)策略，結(jié)合適應(yīng)度函數(shù)，通過(guò)對(duì)交叉和變異概率做動(dòng)態(tài)的調(diào)整，保持種群多樣性的同時(shí)減少搜索空間和提高算法效率.優(yōu)化MRA和RC這2個(gè)目標(biāo)函數(shù)來(lái)尋找最優(yōu)解集，利用隨機(jī)游走(Random-Walker)初始化策略，提高初始解的精度，并在局部搜索中加入爬山策略增強(qiáng)解的精準(zhǔn)度.最后在真實(shí)和人工合成的2種網(wǎng)絡(luò)環(huán)境中驗(yàn)證了提出算法的高效性.