何烈芝，劉漫丹

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

0 引 言

現(xiàn)代生活中存在許多復(fù)雜系統(tǒng)，如電力系統(tǒng)、交通系統(tǒng)等，可以通過(guò)建模將這些復(fù)雜系統(tǒng)轉(zhuǎn)變成復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)具有重要的社區(qū)結(jié)構(gòu)特性，即復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)通常表現(xiàn)出集群特性，同一社區(qū)內(nèi)的節(jié)點(diǎn)連接相對(duì)緊密，不同社區(qū)內(nèi)的節(jié)點(diǎn)連接相對(duì)稀疏[1]，復(fù)雜網(wǎng)絡(luò)的社區(qū)往往存在一定程度的重疊，重疊社區(qū)的廣泛存在引起了不同領(lǐng)域研究人員的關(guān)注，重疊社區(qū)發(fā)現(xiàn)方法主要有派系過(guò)濾法、線圖劃分法、標(biāo)簽傳播法、局部擴(kuò)張法等。近年來(lái)越來(lái)越多的改進(jìn)算法被提出，如基于派系過(guò)濾和標(biāo)簽傳播的在線算法OLCPM(online label clique percolation method)[2]，其中在線CPM能夠?qū)崟r(shí)識(shí)別核心節(jié)點(diǎn)，標(biāo)簽傳播解決了CPM的覆蓋問(wèn)題，局部社區(qū)結(jié)構(gòu)更新減少計(jì)算時(shí)間，但OLCPM對(duì)參數(shù)K有著顯著依賴性；SAoLG(spectral analysis into line graphs)[3]算法結(jié)合線圖與譜分析實(shí)現(xiàn)重疊和層次間的平衡，但該算法更適合規(guī)模小且稀疏的網(wǎng)絡(luò)；Ahajjam等[4]提出LCDA(leader-community detection approach)算法，檢測(cè)具有高傳播影響力網(wǎng)絡(luò)中的領(lǐng)導(dǎo)節(jié)點(diǎn)并按節(jié)點(diǎn)間的相似度進(jìn)行社區(qū)劃分，其適用于大規(guī)模的未知網(wǎng)絡(luò)，但具有相對(duì)較高的復(fù)雜度。由于重疊社區(qū)的評(píng)價(jià)指標(biāo)不唯一，為盡量滿足多個(gè)評(píng)價(jià)指標(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作為一種新算法還存在許多改進(jìn)的空間，以提高社區(qū)劃分質(zhì)量，該算法采用基于鄰接邊[5]的編碼方式，不適合處理節(jié)點(diǎn)間含有大量連接邊的網(wǎng)絡(luò)，使用的進(jìn)化算子也難以保證基因位得到充分改變。本文對(duì)其個(gè)體表達(dá)方式、編碼方式和進(jìn)化算子進(jìn)行改進(jìn)得到IMOFECO-OCD算法(improved MOFECO-OCD)。IMOFECO-OCD算法解碼時(shí)依據(jù)“局部模塊度”[7]來(lái)提高解碼時(shí)得到的重疊社區(qū)質(zhì)量，進(jìn)化算子采用部分匹配交叉[8]和基本位變異算子以保證能夠充分挖掘新個(gè)體。

1 相關(guān)描述

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

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

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

(1)

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

1.2 五行環(huán)模型

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

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

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

(2)

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

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

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

(3)

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

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

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

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

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

(4)

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

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

(5)

2.2 個(gè)體表達(dá)方式與解碼方式

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

A

={v1,v2,…,vn}

(6)

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

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

(7)

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

算法1： MEA_CDPs算法解碼過(guò)程

輸入： 初始解A

={v1,v2,…,vn}

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

G←Ф

//按照A

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

G1←v1

Fori=2 tondo

Forj=1 to |G| do

Iff(Gj)

Gj←Gj∪vi

End If

End For

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

G←G∪{vi}

End If

End For

//合并社區(qū)

End While

2.3 元素更新

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

(8)

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

(9)

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

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

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

變異算子fMutation是比較常用的基本位變異，達(dá)到變異概率時(shí)，該算子隨機(jī)在排序中選取兩個(gè)基因位，交換二者的位置。

2.4 算法流程

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

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

圖2 IMOFECO-OCD算法流程

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

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

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

3.1 實(shí)驗(yàn)設(shè)置

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

3.2 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證IMOFECO-OCD算法對(duì)復(fù)雜網(wǎng)絡(luò)重疊社區(qū)劃分的性能，實(shí)驗(yàn)部分采用了兩種數(shù)據(jù)集，分別是人工合成的LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集和真實(shí)社會(huì)網(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ù)需求進(jìn)行調(diào)節(jié)的，可調(diào)節(jié)參數(shù)分別有節(jié)點(diǎn)數(shù)n，節(jié)點(diǎn)平均度avgk和節(jié)點(diǎn)最大度maxk，最小和最大社區(qū)規(guī)模minc、maxc，重疊節(jié)點(diǎn)個(gè)數(shù)on，重疊節(jié)點(diǎn)所屬社區(qū)數(shù)om和網(wǎng)絡(luò)混合參數(shù)μ。實(shí)驗(yàn)中對(duì)on，om和μ進(jìn)行調(diào)節(jié)，其它參數(shù)取相同值分別為n=200、avgk=10、maxk=20、minc=10和maxc=30，生成了12個(gè)不同的網(wǎng)絡(luò)，具體參數(shù)設(shè)置見(jiàn)表1。

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

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

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

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

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

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

(10)

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

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

(11)

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

(12)

3.4 實(shí)驗(yàn)結(jié)果

3.4.1 人工合成網(wǎng)絡(luò)實(shí)驗(yàn)

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

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

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

表3 μ=0.1時(shí)MOFECO-OCD和IMOFECO-OCD所有個(gè)體的平均EQ值

表4 μ=0.2時(shí)MOFECO-OCD和IMOFECO-OCD所有個(gè)體的平均EQ值

圖3和圖4是IMOFECO-OCD算法、MOFECO-OCD算法、LFM算法和DEMON算法在LFR網(wǎng)絡(luò)上運(yùn)行30次得到的平均EQ值和平均ENMI值，其中，LFM和DEMON是在對(duì)應(yīng)最優(yōu)參數(shù)下運(yùn)行30次得到的平均值，IMOFECO-OCD算法和MOFECO-OCD算法是分別記錄每次運(yùn)行得到的最大值，再累計(jì)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ù)一定時(shí)，因?yàn)榫W(wǎng)絡(luò)混合參數(shù)μ，重疊社區(qū)數(shù)om和重疊節(jié)點(diǎn)數(shù)on的增大導(dǎo)致LFR網(wǎng)絡(luò)的結(jié)構(gòu)變得更加復(fù)雜，所以整體上4種算法計(jì)算得到的平均EQ值和平均ENMI值都隨之減小。在EQ值上，IMOFECO-OCD算法在4組網(wǎng)絡(luò)上的下降趨勢(shì)都比較平緩，除了在om=2，μ=0.2網(wǎng)絡(luò)上的表現(xiàn)略差于LFM算法外，其它3組網(wǎng)絡(luò)上的表現(xiàn)幾乎都是最優(yōu)的。在ENMI值上，當(dāng)om=2時(shí)，IMOFECO-OCD算法和DEMON算法的值比較接近但是劣于LFM算法；當(dāng)om=3時(shí)，DEMON算法的值取得最優(yōu)且IMOFECO-OCD算法的值要?jiǎng)儆贚FM算法；另外，當(dāng)om=3，μ=0.1時(shí)，隨著om的增大，LFM算法的EQ值和ENMI值都呈現(xiàn)大幅度的下降趨勢(shì)，大部分的值都劣于IMOFECO-OCD算法和DEMON算法；當(dāng)om=3，μ=0.2時(shí)，LFM算法的EQ值和ENMI值都僅僅優(yōu)于MOFECO-OCD算法；MOFECO-OCD算法無(wú)論是EQ值的表現(xiàn)還是ENMI值的表現(xiàn)都不如其它3個(gè)算法。

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

3.4.2 真實(shí)社會(huì)網(wǎng)絡(luò)實(shí)驗(yàn)

針對(duì)真實(shí)社會(huì)網(wǎng)絡(luò)，將IMOFECO-OCD算法與MOFECO-OCD和其它經(jīng)典重疊社區(qū)劃分算法進(jìn)行對(duì)比。IMOQPSO算法的粒子群和外部存儲(chǔ)庫(kù)大小都為20，收縮-膨脹系數(shù)線性的從1降低到0.5，迭代次數(shù)為100；為了與IMOQPSO算法在同等條件下對(duì)比，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之間取值，步長(zhǎng)為0.1；SLPA算法的r值在0.1～0.5之間選取，步長(zhǎng)為0.05，迭代次數(shù)為100；DEMON算法的參數(shù)e在0.1～0.5之間選取，步長(zhǎng)為0.1，迭代次數(shù)為100。LFM算法的參數(shù)取值范圍與LFR網(wǎng)絡(luò)的參數(shù)取值范圍一致。

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

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

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

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

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

表7 不同算法在真實(shí)社會(huì)網(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的角度來(lái)看，IMOFECO-OCD算法在表2列出的5種真實(shí)網(wǎng)絡(luò)中都得到了較好的社區(qū)劃分。

4 結(jié)束語(yǔ)

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