改進多目標(biāo)五行環(huán)優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法

何烈芝，劉漫丹

(華東理工大學(xué) 信息科學(xué)與工程學(xué)院，上海 200237)

0 引 言

現(xiàn)代生活中存在許多復(fù)雜系統(tǒng)，如電力系統(tǒng)、交通系統(tǒng)等，可以通過建模將這些復(fù)雜系統(tǒng)轉(zhuǎn)變成復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)具有重要的社區(qū)結(jié)構(gòu)特性，即復(fù)雜網(wǎng)絡(luò)中的節(jié)點通常表現(xiàn)出集群特性，同一社區(qū)內(nèi)的節(jié)點連接相對緊密，不同社區(qū)內(nèi)的節(jié)點連接相對稀疏[1]，復(fù)雜網(wǎng)絡(luò)的社區(qū)往往存在一定程度的重疊，重疊社區(qū)的廣泛存在引起了不同領(lǐng)域研究人員的關(guān)注，重疊社區(qū)發(fā)現(xiàn)方法主要有派系過濾法、線圖劃分法、標(biāo)簽傳播法、局部擴張法等。近年來越來越多的改進算法被提出，如基于派系過濾和標(biāo)簽傳播的在線算法OLCPM(online label clique percolation method)[2]，其中在線CPM能夠?qū)崟r識別核心節(jié)點，標(biāo)簽傳播解決了CPM的覆蓋問題，局部社區(qū)結(jié)構(gòu)更新減少計算時間，但OLCPM對參數(shù)K有著顯著依賴性；SAoLG(spectral analysis into line graphs)[3]算法結(jié)合線圖與譜分析實現(xiàn)重疊和層次間的平衡，但該算法更適合規(guī)模小且稀疏的網(wǎng)絡(luò)；Ahajjam等[4]提出LCDA(leader-community detection approach)算法，檢測具有高傳播影響力網(wǎng)絡(luò)中的領(lǐng)導(dǎo)節(jié)點并按節(jié)點間的相似度進行社區(qū)劃分，其適用于大規(guī)模的未知網(wǎng)絡(luò)，但具有相對較高的復(fù)雜度。由于重疊社區(qū)的評價指標(biāo)不唯一，為盡量滿足多個評價指標(biāo)，多目標(biāo)優(yōu)化被應(yīng)用其中，如Zhao等[5]結(jié)合多目標(biāo)優(yōu)化和遺傳算法提出MOEA-OCD算法(overlapping community detection algorithm based on multi-objective evolutionary algorithm)；張[6]提出基于多目標(biāo)五行環(huán)優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法MOFECO-OCD (multi-objective five-elements cycle optimization for overlapping community detection)。

MOFECO-OCD作為一種新算法還存在許多改進的空間，以提高社區(qū)劃分質(zhì)量，該算法采用基于鄰接邊[5]的編碼方式，不適合處理節(jié)點間含有大量連接邊的網(wǎng)絡(luò)，使用的進化算子也難以保證基因位得到充分改變。本文對其個體表達方式、編碼方式和進化算子進行改進得到IMOFECO-OCD算法(improved MOFECO-OCD)。IMOFECO-OCD算法解碼時依據(jù)“局部模塊度”[7]來提高解碼時得到的重疊社區(qū)質(zhì)量，進化算子采用部分匹配交叉[8]和基本位變異算子以保證能夠充分挖掘新個體。

1 相關(guān)描述

1.1 多目標(biāo)優(yōu)化問題

一個無約束的多目標(biāo)優(yōu)化問題MOP(multi-objective optimization problem)[9]可用式(1)表示

minF(x)=[f1(x),f2(x),…,fl(x)]T

(1)

其中，l為總的目標(biāo)函數(shù)個數(shù)，x=[x1,x2,…,xD]∈Ω表示D維的決策向量，Ω表示可行域。

1.2 五行環(huán)模型

五行元素分別指的是金、木、水、火、土，這5個元素之間存在著相生相克的關(guān)系，每個元素都會受到其它4個元素的作用。以金元素為例，土生金，金生水，火克金，金克木，金元素與剩下的4個元素之間都存在著相生或者相克的關(guān)系，這樣五行元素在自然界中就建立了一種動態(tài)平衡[10]。

根據(jù)上述動態(tài)平衡可以建立五行環(huán)模型，并將五行環(huán)模型FECM(five-elements cycle model)中的五行元素推廣至L元素[11]。

假設(shè)一個動態(tài)系統(tǒng)中存在L個元素，元素i在k時刻的質(zhì)量用mi(k),i=1,2,…,L表示，受力為Fi(k)，F(xiàn)i(k) 由4部分組成，第一部分是母元素的“生”力Fi-1(k)， 它會使元素i變得強大所以是正值，表示為Fi-1(k)=In[mi-1(k)/mi(k)]， 其中mi-1(k)為母元素的質(zhì)量；第二部分是祖輩元素的“克”力Fi-2(k)， 它會使元素i受到約束而變得衰弱，所以Fi-2(k) 為負值，表示為Fi-2(k)=-In[mi-2(k)/mi(k)]，mi-2(k) 為祖輩元素質(zhì)量；第三部分和第四部分是元素i施加給其子元素的“生”力Fi-3(k) 和孫輩元素的“克”力Fi-4(k)， 這兩部分力都是i通過消耗自身來強壯其子元素或削弱孫輩元素的，所以都應(yīng)為負值，分別為Fi-3(k)=-In[mi(k)/mi+1(k)]，F(xiàn)i-4(k)=-In[mi(k)/mi+2(k)]，mi+1(k) 和mi+2(k) 表示元素i的子元素和孫輩元素的質(zhì)量。所以得到五行環(huán)模型FECM的表達式如式(2)所示

(2)

當(dāng)i為1時，用L代替i-1，L-1代替i-2；當(dāng)i為2時，用L代替i-2；當(dāng)i為L-1時，i+2用1代替；當(dāng)i為L時，i+1用1代替，i+2用2代替。

1.3 元素空間的建立與MOFECO-OCD算法的實現(xiàn)

MOFECO-OCD算法建立了一個元素空間，目的是將五行環(huán)模型與進化算法的種群空間關(guān)聯(lián)起來。元素空間中包含q個環(huán)，每個環(huán)上L個元素，xij(k) 為第k次迭代時第j個環(huán)上的第i個元素，代表社區(qū)發(fā)現(xiàn)問題的一種可行的社區(qū)劃分方案。結(jié)合式(1)的多目標(biāo)優(yōu)化問題表達式，用mij,r(r=1,2,…,l) 表示元素xij(k) 的質(zhì)量，即第r個目標(biāo)函數(shù)。類比FECM模型，xij(k) 元素受到環(huán)上其它元素的作用力Fij,r(k) 可用式(3)來表示

(3)

MOFECO-OCD算法首先把重疊社區(qū)發(fā)現(xiàn)問題建模成無約束的多目標(biāo)優(yōu)化問題，基于鄰接邊的編碼方式生成初始解，構(gòu)建元素空間，然后在五行環(huán)模型的基礎(chǔ)上，采用全局最優(yōu)解和局部最優(yōu)解來更新元素，同時在更新策略中引入標(biāo)準(zhǔn)均勻交叉算子和單點變異算子，最終利用非支配排序[12]得到最優(yōu)的重疊社區(qū)劃分集合。

2 改進的多目標(biāo)五行環(huán)優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法

在原有的MOFECO-OCD算法的基礎(chǔ)上，本文提出一種改進算法IMOFECO-OCD，具體改進的方面為個體表達方式和解碼方式，交叉算子和變異算子。

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

網(wǎng)絡(luò)社區(qū)一般用圖G=(V,E) 來表示，V={v1,v2,…,vn} 表示G中的n個節(jié)點集合，E={e1,e2,…,em} 表示G中的m條邊集合。給定一個無權(quán)無向的網(wǎng)絡(luò)G=(V,E)， 其節(jié)點vi的度可表示為式(4)

(4)

其中，Aij表示節(jié)點vi和節(jié)點vj的鄰接矩陣，若vi和vj之間有連接邊，則Aij為1，否則為0。

按照社區(qū)的劃分標(biāo)準(zhǔn)應(yīng)使RA最大化同時使RC最小化。為了將這兩個目標(biāo)轉(zhuǎn)換成最小化多目標(biāo)問題，于是對RA取倒數(shù)得到式(5)的兩個目標(biāo)函數(shù)

(5)

2.2 個體表達方式與解碼方式

針對社區(qū)結(jié)構(gòu)的檢測問題，Liu等[13]提出了一種基于多目標(biāo)的重疊社區(qū)檢測算法MEA_CDPs，該算法能同時發(fā)現(xiàn)分離社區(qū)結(jié)構(gòu)和重疊社區(qū)結(jié)構(gòu)。本文借鑒了其中的個體表達方式和解碼過程。假定網(wǎng)絡(luò)圖G=(V,E) 包含n個節(jié)點，算法先隨機生成一個如式(6)所示的初始解，記其排序為A

A

={v1,v2,…,vn}

(6)

其中，V={v1,v2,…,vn} 表示n個節(jié)點的隨機排列，A

可以通過特定的方法解碼為A， 其中G={G1,G2,…,GP}。 解碼時算法應(yīng)用了“局部模塊度”的概念，這是一種可以評價包含重復(fù)節(jié)點的社區(qū)的函數(shù)。給定一個社區(qū)Gi，其局部模塊度的表示如式(7)所示

(7)

α為正實數(shù)，可以控制社區(qū)的數(shù)目和大小，α較小時社區(qū)數(shù)目少，社區(qū)規(guī)模相對較大，α較大時社區(qū)數(shù)目多，社區(qū)規(guī)模相對較小。α的值通常情況下默認(rèn)為1，但是當(dāng)復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)非常模糊時，該算法就不能正常運行，因為解碼過程會把所有的節(jié)點都劃分到一個社區(qū)中，失去了社區(qū)劃分的意義，此時需要適當(dāng)調(diào)高α的值以保證解碼過程的正常進行。解碼的具體步驟如算法1所示。

算法1： MEA_CDPs算法解碼過程

輸入： 初始解A

={v1,v2,…,vn}

輸出： 社區(qū)劃分G

G←Ф

//按照A

中的順序依次將節(jié)點加入到每個社區(qū)中

G1←v1

Fori=2 tondo

Forj=1 to |G| do

Iff(Gj)

Gj←Gj∪vi

End If

End For

If (vi沒有被加入到任何一個社區(qū)中) then

G←G∪{vi}

End If

End For

//合并社區(qū)

End While

2.3 元素更新

IMOFECO-OCD算法在進行第k次迭代時需要先計算出目標(biāo)函數(shù)值，即元素xij(k) 的質(zhì)量mij,r(k)， 然后計算出xij(k) 的受力Fij,r(k)，xij(k) 的更新策略將由Fij,r(k) 的值來決定。根據(jù)式(3)的表達可以看出，mij,r(k) 越小時得到的Fij,r(k) 值越大，所以Fij,r(k) (?r=1,2,…,l) 的值都大于0時表明對應(yīng)的xij(k)是一個相對較好的元素，在當(dāng)前的種群中保留該元素，反之Fij,r(k) (?r=1,2,…,l) 小于等于0表明xij(k)受力為負值，該元素在系統(tǒng)中是日漸衰弱的，所以xij(k)有可能不是一個較好的元素，需要在xij(k)基礎(chǔ)上產(chǎn)生新的元素來替代xij(k)，新元素的生成策略如式(8)和式(9)所示，其中rc是0到1間的一個隨機數(shù)，pc是算法給定的概率值，xi*j(k) 是局部最優(yōu)解，表示第k次迭代時第j個環(huán)上最好的元素，xgbest(k) 是全局最優(yōu)解。fCrossover和fMutation分別為交叉算子和變異算子

(8)

xmij(k)=fMutation(xcij_1(k))

(9)

全局最優(yōu)解和局部最優(yōu)解是通過對所有可行劃分方案(可行解)進行快速非支配排序[12]得到的，隨機的從所有可行解組成的集合中挑選一個排序等級最高的解即為全局最優(yōu)解xgbest(k)，局部最優(yōu)解xi*j(k)為第j個環(huán)上擁有最大擁擠度[14]和最高排序等級的可行解。

IMOFECO-OCD算法的fCrossover采用部分匹配交叉算子[8]，這是一種專門用于排序的交叉算子，可以確保網(wǎng)絡(luò)中所有基因位都得到充分改變。該方法先隨機在兩個父代排序中分別選取兩個交叉節(jié)點，子代依據(jù)父代的交叉節(jié)點的中間部分來生成。以圖1為示例(節(jié)點數(shù)n=9)，父代為P1和P2，先隨機選兩個交叉節(jié)點用“|”分隔開，如圖1(a)所示。接著交換兩個父代交叉節(jié)點的中間部分，得到圖2(b)中的兩個子代，其中T表示暫未定義的節(jié)點，可以看出中間部分節(jié)點的映射關(guān)系表示為：4?1,5?8,6?7,7?6。接著在子代中對兩個父代中間部分未出現(xiàn)的節(jié)點2、節(jié)點3和節(jié)點9進行保留，如圖1(c)所示。最后對照映射關(guān)系，對圖1(c)中子代O1的第一個T節(jié)點，用父代P1的第一個節(jié)點1的映射節(jié)點4來代替，O1的第二個T節(jié)點，用P1的第8個節(jié)點8的映射節(jié)點5來代替，O2的第一個T節(jié)點，用P2的第一個節(jié)點4的映射節(jié)點1來代替，O2的第二個T節(jié)點，用P2的第二個節(jié)點5的映射節(jié)點8來代替，最終得到如圖1(d)所示的子代個體。

圖1 部分匹配交叉算子示例

變異算子fMutation是比較常用的基本位變異，達到變異概率時，該算子隨機在排序中選取兩個基因位，交換二者的位置。

2.4 算法流程

首先需要對參數(shù)設(shè)值，包括L，q，pc以及最大迭代次數(shù)maxiter，當(dāng)?shù)螖?shù)k為0時，先生成L*q個初始元素xij(0) (i=1,2,…,L;j=1,2,…,q)， 然后計算對應(yīng)的mij,r(0) (r=1,2,…,l) 并把相應(yīng)的Fij,r(0) (r=1,2,…,l) 都賦值為0，接著對得到的mij,r(0) 進行快速非支配排序，全局最優(yōu)解集為排序等級最高的初始元素xij(0) 的集合。

當(dāng)k≥1時，依次計算出元素xij(k)的質(zhì)量mij,r(k) 和受力Fij,r(k)， 若Fij,r(k)>0 (?r=1,2,…,l)， 則將對應(yīng)元素xij(k)保留，反之根據(jù)式(8)和式(9)，采用局部最優(yōu)解或全局最優(yōu)解交叉變異生成新元素。將父代種群和新生成的元素合并，對合并后的元素進行非支配排序，選取L*q個排序等級最高，擁擠度較大的元素組成第k+1代的種群，其中的元素為xij(k+1)，用xij(k+1)中排序等級最高的元素集合中的任意一個代替原來的全局最優(yōu)解。重復(fù)上述操作直到達到最大迭代次數(shù)。IMOFECO-OCD算法的具體流程如圖2所示。

圖2 IMOFECO-OCD算法流程

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

IMOFECO-OCD算法分別在人工合成數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗，并與其它算法進行分析比較。其中，人工合成網(wǎng)絡(luò)上的對比算法有LFM(latent factor model)算法、DEMON(democratic estimate of the modular organization of a network)算法和MOFECO-OCD算法，真實網(wǎng)絡(luò)上的對比算法分別為CPM算法、Link算法、LFM算法、SLPA(speaker-listener label propagation algorithm)算法、DEMON算法、IMOQPSO算法和MOFECO-OCD算法。其中CPM是基于團過濾的算法，Link是基于邊聚類的算法[15]，LFM是基于局部擴展與優(yōu)化的算法[7]，SLPA[16]和DEMON[14]是基于標(biāo)簽傳播的算法，IMOQPSO是基于多目標(biāo)的粒子群算法[17]。

當(dāng)然，在國家權(quán)力和政策調(diào)試下，適應(yīng)政府治理需求只是網(wǎng)絡(luò)政治參與娛樂化產(chǎn)生的一個方面。相反，個體網(wǎng)絡(luò)行為的選擇首先是要滿足自我政治參與的需求，使得網(wǎng)絡(luò)政治參與成為個體表達訴求的有效渠道。而網(wǎng)絡(luò)政治參與娛樂化的靈活性與抗?fàn)幮詢?yōu)點，無疑為個體表達政治訴求提供了有效手段。

3.1 實驗設(shè)置

本文中的IMOFECO-OCD算法和MOFECO-OCD算法的實驗環(huán)境為MATLAB R2017a，LFM算法和DEMON算法的實驗環(huán)境為Python 3.6.5。

3.2 實驗數(shù)據(jù)集

為了驗證IMOFECO-OCD算法對復(fù)雜網(wǎng)絡(luò)重疊社區(qū)劃分的性能，實驗部分采用了兩種數(shù)據(jù)集，分別是人工合成的LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集和真實社會網(wǎng)絡(luò)數(shù)據(jù)集。

3.2.1 LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集

LFR網(wǎng)絡(luò)生成重疊社區(qū)數(shù)據(jù)集中的參數(shù)是可以根據(jù)需求進行調(diào)節(jié)的，可調(diào)節(jié)參數(shù)分別有節(jié)點數(shù)n，節(jié)點平均度avgk和節(jié)點最大度maxk，最小和最大社區(qū)規(guī)模minc、maxc，重疊節(jié)點個數(shù)on，重疊節(jié)點所屬社區(qū)數(shù)om和網(wǎng)絡(luò)混合參數(shù)μ。實驗中對on，om和μ進行調(diào)節(jié)，其它參數(shù)取相同值分別為n=200、avgk=10、maxk=20、minc=10和maxc=30，生成了12個不同的網(wǎng)絡(luò)，具體參數(shù)設(shè)置見表1。

表1 LFR網(wǎng)絡(luò)參數(shù)設(shè)置

3.2.2 真實社會網(wǎng)絡(luò)數(shù)據(jù)集

實驗中涉及到5個真實網(wǎng)絡(luò)數(shù)據(jù)集，分別是Karate、Dolphins、Lesmis、Poolbooks和Football數(shù)據(jù)集，每個網(wǎng)絡(luò)的基本統(tǒng)計特征記錄在表2中。

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

3.3 評價指標(biāo)

實驗中用到的評價指標(biāo)有兩種，分別為重疊模塊度EQ值[18]和重疊標(biāo)準(zhǔn)化互信息ENMI值[7]。模塊度Q[19]是一種廣泛應(yīng)用于社區(qū)劃分的評價指標(biāo)，但它衡量的是非重疊社區(qū)質(zhì)量，并不適用于重疊社區(qū)。重疊模塊度EQ是一種將模塊度Q擴展到重疊社區(qū)劃分的指標(biāo)，定義如式(10)所示

(10)

其中，m表示網(wǎng)絡(luò)中總的連接邊數(shù)，Ci表示劃分到的第i個重疊社區(qū)，Ox代表節(jié)點vx所屬的社區(qū)個數(shù)，Axy是節(jié)點vx和vy的鄰接矩陣，Kx表示節(jié)點vx的度。EQ的值在[0,1]區(qū)間內(nèi)，并且值越大說明算法劃分的質(zhì)量越好。

重疊標(biāo)準(zhǔn)化互信息ENMI是一種將標(biāo)準(zhǔn)化互信息NMI(normalized mutual information)[19]擴展到重疊社區(qū)的指標(biāo)，用于衡量算法劃分得到的重疊社區(qū)與真實社區(qū)之間的相似度，與EQ一樣，ENMI的值也在[0,1]范圍內(nèi)，越接近1說明與真實網(wǎng)絡(luò)社區(qū)的相似度越高。ENMI的定義如式(11)所示

(11)

其中， |C| 表示劃分的重疊社區(qū)數(shù)之和，H(Ci) 為社區(qū)Ci的熵[20]，H(Ci|C*) 為Ci真實社區(qū)C*的熵，其定義如式(12)所示

(12)

3.4 實驗結(jié)果

3.4.1 人工合成網(wǎng)絡(luò)實驗

網(wǎng)絡(luò)混合參數(shù)μ的值越大，表示該網(wǎng)絡(luò)中包含的社區(qū)之間的連接邊也就越多，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)也就越不明顯，μ取0.1和0.2分別代表兩種模糊程度不同的社區(qū)結(jié)構(gòu)。

IMOFECO-OCD算法和MOFECO-OCD算法是分別記錄每次運行得到的最大值，再累計30次求平均值。IMOFECO-OCD算法和MOFECO-OCD算法均取環(huán)數(shù)q=20，環(huán)上元素個數(shù)L=5，即種群規(guī)模為100，元素更新概率pc=0.9，迭代次數(shù)為500，另外，IMOFECO-OCD算法的α值取1；LFM算法的參數(shù)α在0.7～1.2之間選取，步長為0.05；DEMON算法的e值在0.1～0.5之間選取，步長為0.1，迭代次數(shù)為500。

表3和表4分別為混合參數(shù)μ=0.1和μ=0.2時，IMOFECO-OCD算法和MOFECO-OCD算法在不同的LFR網(wǎng)絡(luò)上運行30次得到的種群所有個體的平均EQ值，因為MOFECO-OCD算法在LFR網(wǎng)絡(luò)上得不到種群所有個體的平均ENMI值，所以這里只列出aveEQ值。

根據(jù)表3和表4中的數(shù)據(jù)可以看出，在表1列出的12個不同參數(shù)的LFR網(wǎng)絡(luò)上，IMOFECO-OCD算法的所有個體平均EQ值都遠勝于原算法，表明改進的個體表達方式，解碼方式和進化算子是有效果的，在一定程度上可以提高重疊社區(qū)劃分的質(zhì)量。

表3 μ=0.1時MOFECO-OCD和IMOFECO-OCD所有個體的平均EQ值

表4 μ=0.2時MOFECO-OCD和IMOFECO-OCD所有個體的平均EQ值

圖3和圖4是IMOFECO-OCD算法、MOFECO-OCD算法、LFM算法和DEMON算法在LFR網(wǎng)絡(luò)上運行30次得到的平均EQ值和平均ENMI值，其中，LFM和DEMON是在對應(yīng)最優(yōu)參數(shù)下運行30次得到的平均值，IMOFECO-OCD算法和MOFECO-OCD算法是分別記錄每次運行得到的最大值，再累計30次求平均值。

圖3 4種重疊社區(qū)發(fā)現(xiàn)算法在LFR網(wǎng)絡(luò)上的平均EQ值

圖4 4種重疊社區(qū)發(fā)現(xiàn)算法在LFR網(wǎng)絡(luò)上的平均ENMI值

在圖3和圖4中，其它參數(shù)一定時，因為網(wǎng)絡(luò)混合參數(shù)μ，重疊社區(qū)數(shù)om和重疊節(jié)點數(shù)on的增大導(dǎo)致LFR網(wǎng)絡(luò)的結(jié)構(gòu)變得更加復(fù)雜，所以整體上4種算法計算得到的平均EQ值和平均ENMI值都隨之減小。在EQ值上，IMOFECO-OCD算法在4組網(wǎng)絡(luò)上的下降趨勢都比較平緩，除了在om=2，μ=0.2網(wǎng)絡(luò)上的表現(xiàn)略差于LFM算法外，其它3組網(wǎng)絡(luò)上的表現(xiàn)幾乎都是最優(yōu)的。在ENMI值上，當(dāng)om=2時，IMOFECO-OCD算法和DEMON算法的值比較接近但是劣于LFM算法；當(dāng)om=3時，DEMON算法的值取得最優(yōu)且IMOFECO-OCD算法的值要勝于LFM算法；另外，當(dāng)om=3，μ=0.1時，隨著om的增大，LFM算法的EQ值和ENMI值都呈現(xiàn)大幅度的下降趨勢，大部分的值都劣于IMOFECO-OCD算法和DEMON算法；當(dāng)om=3，μ=0.2時，LFM算法的EQ值和ENMI值都僅僅優(yōu)于MOFECO-OCD算法；MOFECO-OCD算法無論是EQ值的表現(xiàn)還是ENMI值的表現(xiàn)都不如其它3個算法。

所以總的來說，與LFM算法，DEMON算法和MOFECO-OCD算法相比，IMOFECO-OCD算法在大部分LFR網(wǎng)絡(luò)上能夠獲得最優(yōu)的EQ值，重疊節(jié)點數(shù)較小時的ENMI值接近DEMON算法但遜于LFM算法，重疊節(jié)點數(shù)增大時ENMI值勝于LFM算法反而遜于DEMON算法。

3.4.2 真實社會網(wǎng)絡(luò)實驗

針對真實社會網(wǎng)絡(luò)，將IMOFECO-OCD算法與MOFECO-OCD和其它經(jīng)典重疊社區(qū)劃分算法進行對比。IMOQPSO算法的粒子群和外部存儲庫大小都為20，收縮-膨脹系數(shù)線性的從1降低到0.5，迭代次數(shù)為100；為了與IMOQPSO算法在同等條件下對比，IMOFECO-OCD算法和MOFECO-OCD算法均取q=4，L=5，即種群規(guī)模為20，迭代次數(shù)為100，另外IMOFECO-OCD算法的α取1；CPM算法的k為3～8之間的整數(shù)值；Link算法的變量在0.1～0.9之間取值，步長為0.1；SLPA算法的r值在0.1～0.5之間選取，步長為0.05，迭代次數(shù)為100；DEMON算法的參數(shù)e在0.1～0.5之間選取，步長為0.1，迭代次數(shù)為100。LFM算法的參數(shù)取值范圍與LFR網(wǎng)絡(luò)的參數(shù)取值范圍一致。

實驗數(shù)據(jù)記錄在表5～表7中，其中“—”表示相應(yīng)算法沒有得出在對應(yīng)數(shù)據(jù)集下的劃分結(jié)果。表5為IMOFECO-OCD算法和MOFECO-OCD算法在真實數(shù)據(jù)集上運行30次，種群所有個體的平均EQ值，因為MOFECO-OCD算法在大多數(shù)真實社會網(wǎng)絡(luò)上得不到種群所有個體的平均ENMI值，所以只給出aveEQ值。

表5 MOFECO-OCD和IMOFECO-OCD算法所有個體的平均EQ值

由表5可以看到，與MOFECO-OCD算法相比，IMOFECO-OCD算法在5種真實社會網(wǎng)絡(luò)中得到的所有個體的平均EQ值都是最優(yōu)的，并且要明顯優(yōu)于MOFECO-OCD算法，從而驗證了改進算法的有效性。

表6和表7分別為IMOFECO-OCD算法和其它對比算法在真實網(wǎng)絡(luò)上得到的EQ值和ENMI值對比，因為Lesmis網(wǎng)絡(luò)未獲取真實社區(qū)劃分，所以表7中未列各個算法在該社區(qū)上的ENMI值。其中，LFM和DEMON是在對應(yīng)最優(yōu)參數(shù)下運行30次得到的平均值，IMOFECO-OCD和MOFECO-OCD是分別記錄每次運行得到的最大值，再累計30次求平均值。CPM、Link和SLPA這3種算法的結(jié)果來自文獻[6]，IMOQPSO算法的結(jié)果來自文獻[17]和文獻[6]。

表6 不同算法在真實社會網(wǎng)絡(luò)中的EQ值

表7 不同算法在真實社會網(wǎng)絡(luò)中的ENMI值

由表6可以看出，與其它算法相比，IMOFECO-OCD算法在Karate、Lesmis、Poolbooks和Football網(wǎng)絡(luò)上獲得的EQ值都是最優(yōu)的，僅在Dolphins網(wǎng)絡(luò)上的EQ值略差于IMOQPSO算法，表7中IMOFECO-OCD算法僅在Football網(wǎng)絡(luò)上獲得的ENMI值是次優(yōu)的，其它網(wǎng)絡(luò)上都是最優(yōu)的。所以從重疊模塊度EQ和重疊標(biāo)準(zhǔn)化互信息ENMI的角度來看，IMOFECO-OCD算法在表2列出的5種真實網(wǎng)絡(luò)中都得到了較好的社區(qū)劃分。

4 結(jié)束語

本文在MOFECO-OCD算法的基礎(chǔ)上，采用MEA_CDPs算法的個體表達方式與解碼方式代替原來的基于鄰接邊的編碼和解碼方式，采用部分匹配交叉算子和基本位變異算子代替標(biāo)準(zhǔn)均勻交叉算子和單點變異算子，進而提出一種改進多目標(biāo)五行環(huán)優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法IMOFECO-OCD。在不同參數(shù)的LFR網(wǎng)絡(luò)上以及真實社會網(wǎng)絡(luò)上的實驗結(jié)果表明，與其它多種不同的重疊社區(qū)發(fā)現(xiàn)算法相比，IMOFECO-OCD算法能夠得到結(jié)構(gòu)強度較好的重疊社區(qū)劃分，同時也有較好的準(zhǔn)確率。