改進多目標五行環優化的重疊社區發現算法

何烈芝，劉漫丹

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

0 引 言

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

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

1 相關描述

1.1 多目標優化問題

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

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

(1)

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

1.2 五行環模型

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

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

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

(2)

當i為1時，用L代替i-1，L-1代替i-2；當i為2時，用L代替i-2；當i為L-1時，i+2用1代替；當i為L時，i+1用1代替，i+2用2代替。

1.3 元素空間的建立與MOFECO-OCD算法的實現

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

(3)

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

2 改進的多目標五行環優化的重疊社區發現算法

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

2.1 目標函數

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

(4)

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

按照社區的劃分標準應使RA最大化同時使RC最小化。為了將這兩個目標轉換成最小化多目標問題，于是對RA取倒數得到式(5)的兩個目標函數

(5)

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

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

A

={v1,v2,…,vn}

(6)

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

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

(7)

α為正實數，可以控制社區的數目和大小，α較小時社區數目少，社區規模相對較大，α較大時社區數目多，社區規模相對較小。α的值通常情況下默認為1，但是當復雜網絡的社區結構非常模糊時，該算法就不能正常運行，因為解碼過程會把所有的節點都劃分到一個社區中，失去了社區劃分的意義，此時需要適當調高α的值以保證解碼過程的正常進行。解碼的具體步驟如算法1所示。

算法1： MEA_CDPs算法解碼過程

輸入： 初始解A

={v1,v2,…,vn}

輸出： 社區劃分G

G←Ф

//按照A

中的順序依次將節點加入到每個社區中

G1←v1

Fori=2 tondo

Forj=1 to |G| do

Iff(Gj)

Gj←Gj∪vi

End If

End For

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

G←G∪{vi}

End If

End For

//合并社區

End While

2.3 元素更新

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

(8)

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

(9)

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

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

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

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

2.4 算法流程

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

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

圖2 IMOFECO-OCD算法流程

3 實驗結果及分析

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

當然，在國家權力和政策調試下，適應政府治理需求只是網絡政治參與娛樂化產生的一個方面。相反，個體網絡行為的選擇首先是要滿足自我政治參與的需求，使得網絡政治參與成為個體表達訴求的有效渠道。而網絡政治參與娛樂化的靈活性與抗爭性優點，無疑為個體表達政治訴求提供了有效手段。

3.1 實驗設置

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

3.2 實驗數據集

為了驗證IMOFECO-OCD算法對復雜網絡重疊社區劃分的性能，實驗部分采用了兩種數據集，分別是人工合成的LFR基準網絡數據集和真實社會網絡數據集。

3.2.1 LFR基準網絡數據集

LFR網絡生成重疊社區數據集中的參數是可以根據需求進行調節的，可調節參數分別有節點數n，節點平均度avgk和節點最大度maxk，最小和最大社區規模minc、maxc，重疊節點個數on，重疊節點所屬社區數om和網絡混合參數μ。實驗中對on，om和μ進行調節，其它參數取相同值分別為n=200、avgk=10、maxk=20、minc=10和maxc=30，生成了12個不同的網絡，具體參數設置見表1。

表1 LFR網絡參數設置

3.2.2 真實社會網絡數據集

實驗中涉及到5個真實網絡數據集，分別是Karate、Dolphins、Lesmis、Poolbooks和Football數據集，每個網絡的基本統計特征記錄在表2中。

表2 真實網絡數據集

3.3 評價指標

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

(10)

其中，m表示網絡中總的連接邊數，Ci表示劃分到的第i個重疊社區，Ox代表節點vx所屬的社區個數，Axy是節點vx和vy的鄰接矩陣，Kx表示節點vx的度。EQ的值在[0,1]區間內，并且值越大說明算法劃分的質量越好。

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

(11)

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

(12)

3.4 實驗結果

3.4.1 人工合成網絡實驗

網絡混合參數μ的值越大，表示該網絡中包含的社區之間的連接邊也就越多，網絡的社區結構也就越不明顯，μ取0.1和0.2分別代表兩種模糊程度不同的社區結構。

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

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

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

表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網絡上運行30次得到的平均EQ值和平均ENMI值，其中，LFM和DEMON是在對應最優參數下運行30次得到的平均值，IMOFECO-OCD算法和MOFECO-OCD算法是分別記錄每次運行得到的最大值，再累計30次求平均值。

圖3 4種重疊社區發現算法在LFR網絡上的平均EQ值

圖4 4種重疊社區發現算法在LFR網絡上的平均ENMI值

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

所以總的來說，與LFM算法，DEMON算法和MOFECO-OCD算法相比，IMOFECO-OCD算法在大部分LFR網絡上能夠獲得最優的EQ值，重疊節點數較小時的ENMI值接近DEMON算法但遜于LFM算法，重疊節點數增大時ENMI值勝于LFM算法反而遜于DEMON算法。

3.4.2 真實社會網絡實驗

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

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

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

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

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

表6 不同算法在真實社會網絡中的EQ值

表7 不同算法在真實社會網絡中的ENMI值

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

4 結束語

本文在MOFECO-OCD算法的基礎上，采用MEA_CDPs算法的個體表達方式與解碼方式代替原來的基于鄰接邊的編碼和解碼方式，采用部分匹配交叉算子和基本位變異算子代替標準均勻交叉算子和單點變異算子，進而提出一種改進多目標五行環優化的重疊社區發現算法IMOFECO-OCD。在不同參數的LFR網絡上以及真實社會網絡上的實驗結果表明，與其它多種不同的重疊社區發現算法相比，IMOFECO-OCD算法能夠得到結構強度較好的重疊社區劃分，同時也有較好的準確率。