楊思敏 魏文紅 張宇輝
(東莞理工學(xué)院 計(jì)算機(jī)科學(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é)點(diǎn)間連接緊密而社區(qū)間連接稀疏的特征[1]。社區(qū)檢測依照社區(qū)結(jié)構(gòu)特性,將整個復(fù)雜網(wǎng)絡(luò)劃分成幾組節(jié)點(diǎn)(即社區(qū)、模塊或者集群)[5],這有利于發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)潛在規(guī)律,解決生活實(shí)際問題。例如,要解決交通堵塞問題,需要了解交通網(wǎng)絡(luò)布局概況,獲取容易擁堵的關(guān)鍵區(qū)域;要阻斷網(wǎng)絡(luò)流言傳播,需要哪些群體更具有流言傳播快的特點(diǎn);要防止疫情蔓延,就要了解哪些人群更容易被感染等等。
為更好地研究復(fù)雜網(wǎng)絡(luò),科研人員相繼提出了許多社區(qū)檢測算法。Girvan和Newman提出基于最大邊介數(shù)算法(GN)[6],該算法依次刪除網(wǎng)絡(luò)中具有最大邊介數(shù)的邊,以達(dá)到社區(qū)劃分的目的,而該算法每次搜索都需要花費(fèi)大量的時間。為解決GN算法的時間消耗問題,Blondel等提出了一種基于層次聚類的快速模塊度優(yōu)化算法(BGLL)[7],該算法分成兩個階段不斷優(yōu)化模塊度Q[8],以最快時間達(dá)到最好分區(qū)效果,但該算法存在容易陷入局部最優(yōu)的現(xiàn)象。Pizzuti等利用具有超強(qiáng)隨機(jī)性的遺傳算法,以增加解的多樣性找到全局最優(yōu)解,提出了基于遺傳算法的社區(qū)檢測算法(GA-Net)[9]。前面所述算法皆為單目標(biāo)優(yōu)化算法,并不能同時優(yōu)化多個目標(biāo)條件。隨著多目標(biāo)算法應(yīng)用越來越廣泛,Pizzuti根據(jù)社區(qū)結(jié)構(gòu)的特征,將社區(qū)檢測問題建模成多目標(biāo)優(yōu)化問題,并提出了MOGA-NET算法[10]。雖然MOGA-NET可以得到一個較好的社區(qū)劃分,但由于采用鄰接軌跡的編碼方式,使存在種群多樣性不足,社區(qū)劃分準(zhǔn)確度不夠高的缺陷,特別是針對小型的網(wǎng)絡(luò),所以筆者提出ICDMOGA-NET算法應(yīng)用于社區(qū)檢測。
ICDMOGA-NET在編碼階段采用向量編碼方式,打破了基于鄰接軌跡編碼方式的約束,增加編碼多樣性從而增加種群多樣性。在進(jìn)化過程中,利用雙向交叉算子增加個體間信息的交流,并將統(tǒng)一變異方式作為變異策略,以增加節(jié)點(diǎn)與所屬社區(qū)間的粘合度,達(dá)到更好的社區(qū)劃分效果。經(jīng)過改進(jìn),該算法在空手道俱樂部真實(shí)網(wǎng)絡(luò)上的模塊度Q以及歸一互信息NMI分別提高約3.01%、12.63%,對海豚社交網(wǎng)絡(luò)的平均模塊度Q提高約11.3%。
通常社區(qū)被定義為社區(qū)內(nèi)部節(jié)點(diǎn)之間連接緊密,社區(qū)之間連接稀疏的一組節(jié)點(diǎn)[1]。而在更標(biāo)準(zhǔn)的定義中,社區(qū)又可以分為強(qiáng)社區(qū)和弱社區(qū),一個強(qiáng)社區(qū)一定是弱社區(qū)[11]。本文主要對弱社區(qū)的檢測。
選取Kernel K-means(KKM)[13]和Ratio Cut(RC)[14]為兩個目標(biāo)函數(shù)f1,f2,并最小化這兩個目標(biāo)函數(shù)。f1表示社區(qū)內(nèi)部的連接密度,f2反映社區(qū)外部的連接情況。這兩個目標(biāo)的目標(biāo)函數(shù)如下:
(1)
(2)
在社區(qū)檢測中,通常采用基于鄰接軌跡的編碼方式[12],而ICDMOGA-NET則采用向量編碼方式[2]。首先,將整個網(wǎng)絡(luò)編碼成一個整數(shù)串:X={x1,x2,…,xn},其中n是網(wǎng)絡(luò)節(jié)點(diǎn)的總數(shù)。xi表示第i個節(jié)點(diǎn)的社區(qū)標(biāo)識符(即基因),在[1,n]范圍內(nèi)隨機(jī)產(chǎn)生。ICDMOGA-NET算法將具有相同社區(qū)標(biāo)識符的節(jié)點(diǎn)劃分在同一個社區(qū)內(nèi),所以一個個體至多可以分解成n個社區(qū)。如圖1(a)表示由9個節(jié)點(diǎn)組成的網(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ò)編碼解碼
一般來說,染色體重組通常采用單點(diǎn)交叉方式,即隨機(jī)選擇兩個個體作為父代,并任意選擇一個位置編號作為開始交叉的起點(diǎn),從起點(diǎn)開始進(jìn)行個體間的基因交換,從而產(chǎn)生子代。在本文提出算法中,采用雙向交叉的方式[15]從種群中任意選取兩個個體a、b,并隨機(jī)選擇第i個位置。先以個體a為模板,獲取個體a第i個位置所對應(yīng)的社區(qū)標(biāo)識符label1,找到個體a中所有社區(qū)標(biāo)識符為label11的位置,將個體b在相應(yīng)位置上的標(biāo)識符替換成label1,從而產(chǎn)生新個體b1,然后以b為模板重復(fù)上述步驟,產(chǎn)生新個體a1,這樣就完成一次雙向交叉操作。如圖2,從a中隨機(jī)選擇第4個位置,a的第4個位置的標(biāo)識符為1,然后找到a中所有標(biāo)識符為1的位置編號,分別為2、4、6,再將b中位置編號為第2、4、6的標(biāo)識符全部更改為1,此時得到新個體b1;b的第4個位置編號對應(yīng)的基因?yàn)?,在b中找到標(biāo)識符為3的所有位置編號,分別為4、7,將a的第4、7位基因編號上的標(biāo)識符替換為3,得到新個體a1。
圖2 雙向交叉示意圖
不同的社區(qū)檢測算法,因?yàn)榫幋a方式的不同,會有不同的變異策略。由于本文采用向量編碼方式,所以使用統(tǒng)一變異算子策略,以增加種群多樣性。先從種群中隨機(jī)選擇需要突變的個體,并從突變個體中隨機(jī)選擇需要突變的第i個社區(qū)標(biāo)識符,將所有與第i個節(jié)點(diǎn)相鄰的其他節(jié)點(diǎn)所對應(yīng)的社區(qū)標(biāo)識符替換為節(jié)點(diǎn)i的社區(qū)標(biāo)識符。對圖1中的圖G變異過程如圖3所示,先從種群中隨機(jī)選擇變異個體如圖3(a);再從個體中隨機(jī)選擇第8個基因編號作為變異點(diǎn)如圖3(b),其對應(yīng)的標(biāo)識符為2;由圖1中的網(wǎng)絡(luò)N可知,第8個節(jié)點(diǎn)的鄰接節(jié)點(diǎn)是第5個節(jié)點(diǎn),所以將第5個節(jié)點(diǎn)的社區(qū)標(biāo)志符替換為2,如圖3(c)所示。
圖3 變異過程
將網(wǎng)絡(luò)N抽象成圖G=(V,E),其中V表示節(jié)點(diǎn)集合,E表示邊集合。隨機(jī)初始化種群,為每個個體隨機(jī)匹配社區(qū)標(biāo)識符。每個個體可以解碼生成多個圖結(jié)構(gòu),且每個圖均為圖G的子圖。利用多目標(biāo)算法對每個個體進(jìn)行評估,并根據(jù)Pareto優(yōu)勢為每個個體分配等級并進(jìn)行排序,再利用改進(jìn)后的交叉算子以及變異算子增加種群多樣性,產(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:目標(biāo)函數(shù)f1,f2,迭代次數(shù)t,規(guī)模POPOSIZE
1)隨機(jī)初始化種群,個體長度為|V|
2)Whilei 3) 解碼,分解個體。 4) 利用目標(biāo)函數(shù)評估個體 5) 非占優(yōu)排序 6) 選擇個體 7) 交叉產(chǎn)生新個體 8) 變異產(chǎn)生新個體 9)選擇性能指標(biāo)最好個體 10)return 最佳社區(qū)劃分 模塊度Q能夠評估網(wǎng)絡(luò)的社區(qū)劃分結(jié)果的好壞。它是一種內(nèi)部度量,可用于評估社區(qū)結(jié)構(gòu)偏離隨機(jī)性的程度[12]。其定義如下: (3) m是整個網(wǎng)絡(luò)的邊數(shù),Aij表示在鄰接矩陣中節(jié)點(diǎn)i與節(jié)點(diǎn)j是否存在邊,如果是,則Aij=1如果不是,則Aij=0。ki與kj分別表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的度。d(Vi,Vj)用來判斷節(jié)點(diǎn)i與節(jié)點(diǎn)j是否在同一個社區(qū)內(nèi),如果是,則d(Vi,Vj)=1,如果不是,則d(Vi,Vj)=0。 歸一化互信息(NMI)用以評估網(wǎng)絡(luò)真實(shí)劃分與網(wǎng)絡(luò)算法劃分之間的相似度[16]。如果兩個分區(qū)內(nèi)部社團(tuán)劃分越接近,則NMI得值越接近1。當(dāng)NMI的值等于1時,則算法劃分完全與真實(shí)網(wǎng)絡(luò)劃分一致。NMI定義如下: (4) T表示網(wǎng)絡(luò)的真實(shí)劃分情況,P表示利用算法劃分的網(wǎng)絡(luò)情況,則MT為網(wǎng)絡(luò)真實(shí)劃的社區(qū)個數(shù),MP為網(wǎng)絡(luò)算法劃分的社區(qū)個數(shù)。矩陣M是一個混淆矩陣,Mij表示節(jié)點(diǎn)既在分區(qū)T第i個社區(qū)又在分區(qū)P第j個社區(qū)的個數(shù)。Mi表示混淆矩陣M第i行的和,Mj表示混淆矩陣M第j列的和。 3.2 環(huán)境配置與實(shí)驗(yàn)配置 實(shí)驗(yàn)環(huán)境配置: 操作系統(tǒng):win10;內(nèi)存:8G;處理器:Intel(R) Core(TM) i5-8250U;主頻:1.60GHz。 實(shí)驗(yàn)配置: 獨(dú)立運(yùn)行次數(shù):20次;迭代次數(shù):100代;種群規(guī)模:200。 Lancichinetti[17]在2008年提出一種基準(zhǔn)測試網(wǎng)絡(luò)(LFR),該網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)和社區(qū)大小均服從指數(shù)分布。每個節(jié)點(diǎn)與其社區(qū)節(jié)點(diǎn)的連接比率為μ,而與其他社區(qū)頂點(diǎn)連接的比率為1-μ。μ是混合參數(shù)。通過控制μ可以控制社區(qū)的大小。本文將μ從0增加到0.8,每次增加0.1,生成8個合成網(wǎng)絡(luò)。圖5和圖6表示8個合成網(wǎng)絡(luò)通過ICDMOGA-NET獨(dú)立運(yùn)行20次后,所得到的最大NMI和Q的值。實(shí)驗(yàn)結(jié)果表明隨著μ的不斷增大,即合成網(wǎng)絡(luò)的復(fù)雜度增大,NMI和模塊度Q的值在不斷減小,并逐漸維持一個相對穩(wěn)定位置。 圖5 合成網(wǎng)絡(luò)NMI對比 圖6 合成網(wǎng)絡(luò)模塊度Q對比 本實(shí)驗(yàn)主要對空手道俱樂部關(guān)系網(wǎng)絡(luò)(Zachary’s Karate Club Network)[18]以及海豚社交網(wǎng)絡(luò)(Dolphin Social Network)[19]兩個真實(shí)網(wǎng)絡(luò)進(jìn)行測試??帐值谰銟凡筷P(guān)系網(wǎng)絡(luò)是對一個美國大學(xué)空手道俱樂部進(jìn)行觀察而構(gòu)建的真實(shí)的社會網(wǎng)絡(luò)。網(wǎng)絡(luò)包含34個節(jié)點(diǎn)和78條邊,其中節(jié)點(diǎn)表示俱樂部成員,邊表示成員之間存在關(guān)系。經(jīng)過觀察,該網(wǎng)絡(luò)在現(xiàn)實(shí)社會中被劃分為2個社區(qū)。實(shí)驗(yàn)是對無權(quán)重的空手道俱樂部關(guān)系網(wǎng)絡(luò)進(jìn)行測試。海豚社交關(guān)系網(wǎng)絡(luò)是通過觀察生活在新西蘭Doubtful Sound海峽的62只海豚群體的交流情況而形成。該網(wǎng)絡(luò)具有62個節(jié)點(diǎn),159條邊,節(jié)點(diǎn)表示海豚,而邊是指頻繁接觸的海豚。該圖為無權(quán)圖。 實(shí)驗(yàn)獨(dú)立運(yùn)行20次,每次迭代100代,種群規(guī)模為200。為比較算法性能,本文選擇MOGA-NET[10]、基于k值的多目標(biāo)聚類算法(MOCK)[20]、BGLL[7]以及多目標(biāo)集群算法(GraSC)[21]進(jìn)行比較。通過ICDMOGA-NET得到Pareto前沿如圖7所示。通過實(shí)驗(yàn),由表1可知,與MOGA-NET、MOCK、BGLL、GraSC相比,ICDMOGA-NET對空手道俱樂部關(guān)系網(wǎng)絡(luò)的社區(qū)檢測可以獲得更大的NMI和Q其社區(qū)劃分效果更好,對海豚社交關(guān)系網(wǎng)絡(luò)進(jìn)行社區(qū)檢測的時模塊度Q的值維持在0.4以上,說明ICDMOGA-NET具有一定的穩(wěn)定性。圖8、圖9分別表示ICDMOGA-NET對空手道俱樂部關(guān)系網(wǎng)和海豚社交網(wǎng)絡(luò)一次運(yùn)行時Q和NIM的變化,每隔5代記錄一次,由結(jié)果可知,在一次運(yùn)行中,ICDMOGA-NET可以加快收斂,更快接近最優(yōu)值。圖10、圖11為通過ICDMOGA-NET算法網(wǎng)絡(luò)劃分與真實(shí)網(wǎng)絡(luò)劃分對比,得到本文提出算法在空手道俱樂部關(guān)系網(wǎng)上有較好的社區(qū)劃分,而對海豚社交網(wǎng)絡(luò)所得到的社區(qū)個數(shù)大于真實(shí)社區(qū)劃分的個數(shù),可以細(xì)化社區(qū)劃分。 表1 ICMDGA-NET與其他算法對比結(jié)果 圖7 兩個真實(shí)網(wǎng)絡(luò)的Pareto前沿 圖8 ICDMOGA-NET與其他算法在空手道俱樂部關(guān)系網(wǎng)運(yùn)行一次的過程 圖9 ICDMOGA-NET與其他算法在海豚關(guān)系網(wǎng)一次運(yùn)行的過程 圖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)越性。因?yàn)镮CDMOGA-NET結(jié)合向量編碼方式,該編碼方式有比較強(qiáng)的隨機(jī)性,以至提高種群的多樣性,增大搜索最優(yōu)社區(qū)的可能性,且雙向交叉策略加強(qiáng)節(jié)點(diǎn)之間的信息交流,因此ICDMOGA-NET針對小型網(wǎng)絡(luò)可以有更好的效果。 本文提出一種基于MOGA-NET改進(jìn)的多目標(biāo)社區(qū)結(jié)構(gòu)檢測算法。該算法采用向量編碼方式、雙向交叉算子以及統(tǒng)一變異算子,以增大種群的多樣性,提高個體間信息交流。通過合成網(wǎng)絡(luò)實(shí)驗(yàn)可知,本文算法所得的結(jié)果隨著μ的增大而減小。說明網(wǎng)絡(luò)的復(fù)雜程度越大,ICDMOGA-NET的社區(qū)劃分難度也在增大。在真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)中,與MOGA-NET、MOCK、BGLL、GraSC相比,針對更小型的網(wǎng)絡(luò)ICDMOGA-NET具有更高的精確度。在今后研究中,可以從降低時間開銷、增加節(jié)點(diǎn)之間關(guān)聯(lián)性的搜索機(jī)制等,對ICDMOGA-NET進(jìn)行拓展。3 實(shí)驗(yàn)分析
3.1 性能指標(biāo)
3.3 合成網(wǎng)絡(luò)實(shí)驗(yàn)
3.4 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)
3 結(jié)語