一種改進的多目標社區(qū)結(jié)構(gòu)檢測算法

楊思敏 魏文紅 張宇輝

(東莞理工學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，廣東東莞 523808)

隨著網(wǎng)絡(luò)科學(xué)的發(fā)展，復(fù)雜網(wǎng)絡(luò)所代表的各種復(fù)雜系統(tǒng)已廣泛應(yīng)用于許多領(lǐng)域，例如生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò)以及交通網(wǎng)絡(luò)等[1-3]。復(fù)雜網(wǎng)絡(luò)具有許多重要特性，社區(qū)結(jié)構(gòu)就是其重要特性之一[4]。一般而言，社區(qū)結(jié)構(gòu)具有內(nèi)部節(jié)點間連接緊密而社區(qū)間連接稀疏的特征[1]。社區(qū)檢測依照社區(qū)結(jié)構(gòu)特性，將整個復(fù)雜網(wǎng)絡(luò)劃分成幾組節(jié)點(即社區(qū)、模塊或者集群)[5]，這有利于發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)潛在規(guī)律，解決生活實際問題。例如，要解決交通堵塞問題，需要了解交通網(wǎng)絡(luò)布局概況，獲取容易擁堵的關(guān)鍵區(qū)域；要阻斷網(wǎng)絡(luò)流言傳播，需要哪些群體更具有流言傳播快的特點；要防止疫情蔓延，就要了解哪些人群更容易被感染等等。

為更好地研究復(fù)雜網(wǎng)絡(luò)，科研人員相繼提出了許多社區(qū)檢測算法。Girvan和Newman提出基于最大邊介數(shù)算法(GN)[6]，該算法依次刪除網(wǎng)絡(luò)中具有最大邊介數(shù)的邊，以達到社區(qū)劃分的目的，而該算法每次搜索都需要花費大量的時間。為解決GN算法的時間消耗問題，Blondel等提出了一種基于層次聚類的快速模塊度優(yōu)化算法(BGLL)[7]，該算法分成兩個階段不斷優(yōu)化模塊度Q[8]，以最快時間達到最好分區(qū)效果，但該算法存在容易陷入局部最優(yōu)的現(xiàn)象。Pizzuti等利用具有超強隨機性的遺傳算法，以增加解的多樣性找到全局最優(yōu)解，提出了基于遺傳算法的社區(qū)檢測算法(GA-Net)[9]。前面所述算法皆為單目標優(yōu)化算法，并不能同時優(yōu)化多個目標條件。隨著多目標算法應(yīng)用越來越廣泛，Pizzuti根據(jù)社區(qū)結(jié)構(gòu)的特征，將社區(qū)檢測問題建模成多目標優(yōu)化問題，并提出了MOGA-NET算法[10]。雖然MOGA-NET可以得到一個較好的社區(qū)劃分，但由于采用鄰接軌跡的編碼方式，使存在種群多樣性不足，社區(qū)劃分準確度不夠高的缺陷，特別是針對小型的網(wǎng)絡(luò)，所以筆者提出ICDMOGA-NET算法應(yīng)用于社區(qū)檢測。

ICDMOGA-NET在編碼階段采用向量編碼方式，打破了基于鄰接軌跡編碼方式的約束，增加編碼多樣性從而增加種群多樣性。在進化過程中，利用雙向交叉算子增加個體間信息的交流，并將統(tǒng)一變異方式作為變異策略，以增加節(jié)點與所屬社區(qū)間的粘合度，達到更好的社區(qū)劃分效果。經(jīng)過改進，該算法在空手道俱樂部真實網(wǎng)絡(luò)上的模塊度Q以及歸一互信息NMI分別提高約3.01%、12.63%，對海豚社交網(wǎng)絡(luò)的平均模塊度Q提高約11.3%。

1 問題描述

通常社區(qū)被定義為社區(qū)內(nèi)部節(jié)點之間連接緊密，社區(qū)之間連接稀疏的一組節(jié)點[1]。而在更標準的定義中，社區(qū)又可以分為強社區(qū)和弱社區(qū)，一個強社區(qū)一定是弱社區(qū)[11]。本文主要對弱社區(qū)的檢測。

選取Kernel K-means(KKM)[13]和Ratio Cut(RC)[14]為兩個目標函數(shù)f1,f2，并最小化這兩個目標函數(shù)。f1表示社區(qū)內(nèi)部的連接密度，f2反映社區(qū)外部的連接情況。這兩個目標的目標函數(shù)如下：

(1)

(2)

2 算法描述

2.1 個體表示

在社區(qū)檢測中，通常采用基于鄰接軌跡的編碼方式[12]，而ICDMOGA-NET則采用向量編碼方式[2]。首先，將整個網(wǎng)絡(luò)編碼成一個整數(shù)串：X={x1,x2,…,xn}，其中n是網(wǎng)絡(luò)節(jié)點的總數(shù)。xi表示第i個節(jié)點的社區(qū)標識符(即基因)，在[1,n]范圍內(nèi)隨機產(chǎn)生。ICDMOGA-NET算法將具有相同社區(qū)標識符的節(jié)點劃分在同一個社區(qū)內(nèi)，所以一個個體至多可以分解成n個社區(qū)。如圖1(a)表示由9個節(jié)點組成的網(wǎng)絡(luò)N，圖1(b)圖G是由網(wǎng)絡(luò)N抽象出來的圖，經(jīng)向量編碼后產(chǎn)生形成個體圖1(c)，再經(jīng)過解碼后分解成兩個社區(qū)圖1(d)。

圖1 網(wǎng)絡(luò)編碼解碼

2.2 交叉算子

一般來說，染色體重組通常采用單點交叉方式，即隨機選擇兩個個體作為父代，并任意選擇一個位置編號作為開始交叉的起點，從起點開始進行個體間的基因交換，從而產(chǎn)生子代。在本文提出算法中，采用雙向交叉的方式[15]從種群中任意選取兩個個體a、b，并隨機選擇第i個位置。先以個體a為模板，獲取個體a第i個位置所對應(yīng)的社區(qū)標識符label1，找到個體a中所有社區(qū)標識符為label11的位置，將個體b在相應(yīng)位置上的標識符替換成label1，從而產(chǎn)生新個體b1，然后以b為模板重復(fù)上述步驟，產(chǎn)生新個體a1，這樣就完成一次雙向交叉操作。如圖2，從a中隨機選擇第4個位置，a的第4個位置的標識符為1，然后找到a中所有標識符為1的位置編號，分別為2、4、6，再將b中位置編號為第2、4、6的標識符全部更改為1，此時得到新個體b1；b的第4個位置編號對應(yīng)的基因為3，在b中找到標識符為3的所有位置編號，分別為4、7，將a的第4、7位基因編號上的標識符替換為3，得到新個體a1。

圖2 雙向交叉示意圖

2.3 變異算子

不同的社區(qū)檢測算法，因為編碼方式的不同，會有不同的變異策略。由于本文采用向量編碼方式，所以使用統(tǒng)一變異算子策略，以增加種群多樣性。先從種群中隨機選擇需要突變的個體，并從突變個體中隨機選擇需要突變的第i個社區(qū)標識符，將所有與第i個節(jié)點相鄰的其他節(jié)點所對應(yīng)的社區(qū)標識符替換為節(jié)點i的社區(qū)標識符。對圖1中的圖G變異過程如圖3所示，先從種群中隨機選擇變異個體如圖3(a)；再從個體中隨機選擇第8個基因編號作為變異點如圖3(b)，其對應(yīng)的標識符為2；由圖1中的網(wǎng)絡(luò)N可知，第8個節(jié)點的鄰接節(jié)點是第5個節(jié)點，所以將第5個節(jié)點的社區(qū)標志符替換為2，如圖3(c)所示。

圖3 變異過程

2.4 算法步驟

將網(wǎng)絡(luò)N抽象成圖G=(V,E)，其中V表示節(jié)點集合，E表示邊集合。隨機初始化種群，為每個個體隨機匹配社區(qū)標識符。每個個體可以解碼生成多個圖結(jié)構(gòu)，且每個圖均為圖G的子圖。利用多目標算法對每個個體進行評估，并根據(jù)Pareto優(yōu)勢為每個個體分配等級并進行排序，再利用改進后的交叉算子以及變異算子增加種群多樣性，產(chǎn)生新的種群。ICDMOGA-NET具體算法構(gòu)造如算法1，圖4為ICDMOGA-NET算法流程。

圖4 ICDMOGA-NET算法流程

算法1 ICDMOGA-NET算法

Input:網(wǎng)絡(luò)N，并建模成圖為G=(V,E)

Input:目標函數(shù)f1,f2，迭代次數(shù)t，規(guī)模POPOSIZE

1)隨機初始化種群，個體長度為|V|

2)Whilei

3) 解碼，分解個體。

4) 利用目標函數(shù)評估個體

5) 非占優(yōu)排序

6) 選擇個體

7) 交叉產(chǎn)生新個體

8) 變異產(chǎn)生新個體

9)選擇性能指標最好個體

10)return 最佳社區(qū)劃分

3 實驗分析

3.1 性能指標

模塊度Q能夠評估網(wǎng)絡(luò)的社區(qū)劃分結(jié)果的好壞。它是一種內(nèi)部度量，可用于評估社區(qū)結(jié)構(gòu)偏離隨機性的程度[12]。其定義如下：

(3)

m是整個網(wǎng)絡(luò)的邊數(shù)，Aij表示在鄰接矩陣中節(jié)點i與節(jié)點j是否存在邊，如果是，則Aij=1如果不是，則Aij=0。ki與kj分別表示節(jié)點i與節(jié)點j的度。d(Vi,Vj)用來判斷節(jié)點i與節(jié)點j是否在同一個社區(qū)內(nèi)，如果是，則d(Vi,Vj)=1，如果不是，則d(Vi,Vj)=0。

歸一化互信息(NMI)用以評估網(wǎng)絡(luò)真實劃分與網(wǎng)絡(luò)算法劃分之間的相似度[16]。如果兩個分區(qū)內(nèi)部社團劃分越接近，則NMI得值越接近1。當(dāng)NMI的值等于1時，則算法劃分完全與真實網(wǎng)絡(luò)劃分一致。NMI定義如下：

(4)

T表示網(wǎng)絡(luò)的真實劃分情況，P表示利用算法劃分的網(wǎng)絡(luò)情況，則MT為網(wǎng)絡(luò)真實劃的社區(qū)個數(shù)，MP為網(wǎng)絡(luò)算法劃分的社區(qū)個數(shù)。矩陣M是一個混淆矩陣，Mij表示節(jié)點既在分區(qū)T第i個社區(qū)又在分區(qū)P第j個社區(qū)的個數(shù)。Mi表示混淆矩陣M第i行的和，Mj表示混淆矩陣M第j列的和。

3.2 環(huán)境配置與實驗配置

實驗環(huán)境配置：

操作系統(tǒng)：win10；內(nèi)存：8G；處理器：Intel(R) Core(TM) i5-8250U；主頻：1.60GHz。

實驗配置：

獨立運行次數(shù)：20次；迭代次數(shù)：100代；種群規(guī)模：200。

3.3 合成網(wǎng)絡(luò)實驗

Lancichinetti[17]在2008年提出一種基準測試網(wǎng)絡(luò)(LFR)，該網(wǎng)絡(luò)節(jié)點度數(shù)和社區(qū)大小均服從指數(shù)分布。每個節(jié)點與其社區(qū)節(jié)點的連接比率為μ，而與其他社區(qū)頂點連接的比率為1-μ。μ是混合參數(shù)。通過控制μ可以控制社區(qū)的大小。本文將μ從0增加到0.8，每次增加0.1，生成8個合成網(wǎng)絡(luò)。圖5和圖6表示8個合成網(wǎng)絡(luò)通過ICDMOGA-NET獨立運行20次后，所得到的最大NMI和Q的值。實驗結(jié)果表明隨著μ的不斷增大，即合成網(wǎng)絡(luò)的復(fù)雜度增大，NMI和模塊度Q的值在不斷減小，并逐漸維持一個相對穩(wěn)定位置。

圖5 合成網(wǎng)絡(luò)NMI對比

圖6 合成網(wǎng)絡(luò)模塊度Q對比

3.4 真實網(wǎng)絡(luò)實驗

本實驗主要對空手道俱樂部關(guān)系網(wǎng)絡(luò)(Zachary’s Karate Club Network)[18]以及海豚社交網(wǎng)絡(luò)(Dolphin Social Network)[19]兩個真實網(wǎng)絡(luò)進行測試?？帐值谰銟凡筷P(guān)系網(wǎng)絡(luò)是對一個美國大學(xué)空手道俱樂部進行觀察而構(gòu)建的真實的社會網(wǎng)絡(luò)。網(wǎng)絡(luò)包含34個節(jié)點和78條邊，其中節(jié)點表示俱樂部成員，邊表示成員之間存在關(guān)系。經(jīng)過觀察，該網(wǎng)絡(luò)在現(xiàn)實社會中被劃分為2個社區(qū)。實驗是對無權(quán)重的空手道俱樂部關(guān)系網(wǎng)絡(luò)進行測試。海豚社交關(guān)系網(wǎng)絡(luò)是通過觀察生活在新西蘭Doubtful Sound海峽的62只海豚群體的交流情況而形成。該網(wǎng)絡(luò)具有62個節(jié)點，159條邊，節(jié)點表示海豚，而邊是指頻繁接觸的海豚。該圖為無權(quán)圖。

實驗獨立運行20次，每次迭代100代，種群規(guī)模為200。為比較算法性能，本文選擇MOGA-NET[10]、基于k值的多目標聚類算法(MOCK)[20]、BGLL[7]以及多目標集群算法(GraSC)[21]進行比較。通過ICDMOGA-NET得到Pareto前沿如圖7所示。通過實驗,由表1可知，與MOGA-NET、MOCK、BGLL、GraSC相比，ICDMOGA-NET對空手道俱樂部關(guān)系網(wǎng)絡(luò)的社區(qū)檢測可以獲得更大的NMI和Q其社區(qū)劃分效果更好，對海豚社交關(guān)系網(wǎng)絡(luò)進行社區(qū)檢測的時模塊度Q的值維持在0.4以上，說明ICDMOGA-NET具有一定的穩(wěn)定性。圖8、圖9分別表示ICDMOGA-NET對空手道俱樂部關(guān)系網(wǎng)和海豚社交網(wǎng)絡(luò)一次運行時Q和NIM的變化，每隔5代記錄一次，由結(jié)果可知，在一次運行中，ICDMOGA-NET可以加快收斂，更快接近最優(yōu)值。圖10、圖11為通過ICDMOGA-NET算法網(wǎng)絡(luò)劃分與真實網(wǎng)絡(luò)劃分對比，得到本文提出算法在空手道俱樂部關(guān)系網(wǎng)上有較好的社區(qū)劃分，而對海豚社交網(wǎng)絡(luò)所得到的社區(qū)個數(shù)大于真實社區(qū)劃分的個數(shù),可以細化社區(qū)劃分。

表1 ICMDGA-NET與其他算法對比結(jié)果

圖7 兩個真實網(wǎng)絡(luò)的Pareto前沿

圖8 ICDMOGA-NET與其他算法在空手道俱樂部關(guān)系網(wǎng)運行一次的過程

圖9 ICDMOGA-NET與其他算法在海豚關(guān)系網(wǎng)一次運行的過程

圖10 由ICDMOGA-NET檢測到空手道俱樂部關(guān)系網(wǎng)分區(qū)

圖11 由ICDMOGA-NET檢測到海豚社交關(guān)系網(wǎng)分區(qū)

總體而言，ICDMOGA-NET相較于MOGA-NET在空手道俱樂部關(guān)系網(wǎng)絡(luò)上Q以及NMI分別提高約3.01%、12.63%，在海豚社交網(wǎng)絡(luò)上的平均模塊度Q提高約11.3%，并且與MOCK、BGLL以及GraSC相比，ICDMOGA-NET具有較大的優(yōu)越性。因為ICDMOGA-NET結(jié)合向量編碼方式，該編碼方式有比較強的隨機性，以至提高種群的多樣性，增大搜索最優(yōu)社區(qū)的可能性，且雙向交叉策略加強節(jié)點之間的信息交流，因此ICDMOGA-NET針對小型網(wǎng)絡(luò)可以有更好的效果。

3 結(jié)語

本文提出一種基于MOGA-NET改進的多目標社區(qū)結(jié)構(gòu)檢測算法。該算法采用向量編碼方式、雙向交叉算子以及統(tǒng)一變異算子，以增大種群的多樣性，提高個體間信息交流。通過合成網(wǎng)絡(luò)實驗可知，本文算法所得的結(jié)果隨著μ的增大而減小。說明網(wǎng)絡(luò)的復(fù)雜程度越大，ICDMOGA-NET的社區(qū)劃分難度也在增大。在真實網(wǎng)絡(luò)實驗中,與MOGA-NET、MOCK、BGLL、GraSC相比，針對更小型的網(wǎng)絡(luò)ICDMOGA-NET具有更高的精確度。在今后研究中，可以從降低時間開銷、增加節(jié)點之間關(guān)聯(lián)性的搜索機制等，對ICDMOGA-NET進行拓展。