韓存鴿, 陳展鴻, 郭 昆*

(1.武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院 福建省茶產(chǎn)業(yè)大數(shù)據(jù)應(yīng)用與智能化重點(diǎn)實(shí)驗(yàn)室, 福建 武夷山 354300; 2.福州大學(xué) 計(jì)算機(jī)與大數(shù)據(jù)學(xué)院, 福建 福州 350108)

0 引言

現(xiàn)實(shí)世界中的許多復(fù)雜系統(tǒng)都可以建模為網(wǎng)絡(luò),如生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、科學(xué)合作網(wǎng)絡(luò)等.在這些網(wǎng)絡(luò)中,節(jié)點(diǎn)之間的連接關(guān)系非常復(fù)雜,節(jié)點(diǎn)的度、聚集系數(shù)、連通性等屬性也各不相同.社區(qū)發(fā)現(xiàn)[1]是復(fù)雜網(wǎng)絡(luò)研究中的一個(gè)重要領(lǐng)域,其主要目的是發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu).社區(qū)發(fā)現(xiàn)可以從節(jié)點(diǎn)屬性角度進(jìn)行分類(lèi),分為無(wú)屬性網(wǎng)絡(luò)和屬性網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn).在過(guò)去,許多社區(qū)發(fā)現(xiàn)算法僅考慮網(wǎng)絡(luò)結(jié)構(gòu),忽略了節(jié)點(diǎn)間的屬性信息.然而,現(xiàn)實(shí)世界中許多網(wǎng)絡(luò)都具有屬性,如社交網(wǎng)絡(luò)中的個(gè)人資料信息、科學(xué)合作網(wǎng)絡(luò)中的學(xué)科領(lǐng)域等.

基于進(jìn)化計(jì)算的社區(qū)發(fā)現(xiàn)早期應(yīng)用于無(wú)屬性網(wǎng)絡(luò).2008年,Pizzuti[2]首次提出了GA-Net,該算法采用鄰位編碼的遺傳算法搜索社區(qū),是最早的基于進(jìn)化的社區(qū)發(fā)現(xiàn)方法.隨后,一些基于多目標(biāo)優(yōu)化的進(jìn)化算法被應(yīng)用于社區(qū)發(fā)現(xiàn).2009年,Pizzuti[3]提出了基于多目標(biāo)優(yōu)化的進(jìn)化計(jì)算社區(qū)發(fā)現(xiàn)算法MOGA-Net,算法通過(guò)優(yōu)化社區(qū)得分和社區(qū)適應(yīng)度來(lái)完成無(wú)屬性網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn).2013年,Gong等[4]提出的MODPSO結(jié)合粒子群算法,對(duì)核k均值(KKM)和比率割(RC)這兩個(gè)目標(biāo)進(jìn)行優(yōu)化,提高了社區(qū)發(fā)現(xiàn)的精度.2018年,Zhang等[5]提出了一種在大規(guī)模圖上進(jìn)化計(jì)算進(jìn)行社區(qū)發(fā)現(xiàn)的算法RMOEA,采用了一種節(jié)點(diǎn)規(guī)約策略來(lái)將同社區(qū)的節(jié)點(diǎn)合并成一個(gè)超級(jí)節(jié)點(diǎn)進(jìn)行迭代,提高了算法的收斂速度與精度.此后,一些基于屬性網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法被相繼提出.2017年,Li等[6]提出了MOEA-SA的多目標(biāo)優(yōu)化社區(qū)檢測(cè)算法,通過(guò)優(yōu)化模塊度和屬性相似性來(lái)進(jìn)行社區(qū)發(fā)現(xiàn),使得社區(qū)內(nèi)的節(jié)點(diǎn)間的邊密集并且屬性相似,提高了社區(qū)劃分的正確性.2019年,Pizzuti等[7]提出了MOGA-@Net算法,它嘗試對(duì)多種目標(biāo)函數(shù)進(jìn)行優(yōu)化,并通過(guò)合并社區(qū)的方式來(lái)提高社區(qū)發(fā)現(xiàn)的精度.2021年,Sun等[8]提出了CE-MOEA,其利用圖神經(jīng)網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)的邊進(jìn)行編碼,每條邊都對(duì)應(yīng)著一個(gè)連續(xù)變量,最后通過(guò)邊的非線性變換來(lái)生成社區(qū)劃分.

目前,基于屬性網(wǎng)絡(luò)多目標(biāo)優(yōu)化進(jìn)化社區(qū)發(fā)現(xiàn)算法(MOEAs)主要面臨兩個(gè)挑戰(zhàn):(1)編碼方式都直接或間接使用鄰接編碼策略,使得算法的搜索能力易受網(wǎng)絡(luò)結(jié)構(gòu)限制,社區(qū)劃分的質(zhì)量不高;(2)進(jìn)化算法容易陷入局部最優(yōu),導(dǎo)致社區(qū)發(fā)現(xiàn)的精度不高.

針對(duì)以上問(wèn)題,本文提出一種基于融合嵌入向量的多目標(biāo)優(yōu)化社區(qū)發(fā)現(xiàn)算法FEV-MOEA(Fusion Embedding Vector MOEA),首先,設(shè)計(jì)一種基于融合系數(shù)的編解碼方案,通過(guò)利用每個(gè)節(jié)點(diǎn)的屬性與結(jié)構(gòu)嵌入向量,以克服算法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的限制,提高社區(qū)劃分質(zhì)量.其次,提出一種后處理節(jié)點(diǎn)修正策略,通過(guò)該策略對(duì)社區(qū)劃分結(jié)果進(jìn)行修正,提高社區(qū)劃分的精度.主要?jiǎng)?chuàng)新點(diǎn)如下:

(1)通過(guò)設(shè)計(jì)融合系數(shù)編解碼方案,充分利用節(jié)點(diǎn)屬性、結(jié)構(gòu)嵌入向量.編碼時(shí),采用連續(xù)值編碼方式,將每個(gè)節(jié)點(diǎn)編碼成一個(gè)基因位,每個(gè)基因值表示該節(jié)點(diǎn)結(jié)構(gòu)、屬性嵌入向量的融合程度,避免了傳統(tǒng)編碼方案中丟失節(jié)點(diǎn)間連續(xù)信息的問(wèn)題.解碼時(shí),根據(jù)融合嵌入向量結(jié)合聚類(lèi)算法,使得解碼方式不受網(wǎng)絡(luò)結(jié)構(gòu)的限制,以提升社區(qū)發(fā)現(xiàn)的質(zhì)量.

(2)通過(guò)設(shè)計(jì)后處理節(jié)點(diǎn)修正策略,不斷優(yōu)化新社區(qū)的模塊度與社區(qū)內(nèi)屬性相似度,使得算法的解能夠克服陷入局部最優(yōu)的問(wèn)題,提高社區(qū)發(fā)現(xiàn)的精度.

(3)通過(guò)在真實(shí)和人工數(shù)據(jù)集上實(shí)驗(yàn),驗(yàn)證了FEV-MOEA算法能夠有效提高社區(qū)發(fā)現(xiàn)的精度.

1 FEV-MOEA算法

1.1 基本概念

定義1復(fù)雜網(wǎng)絡(luò):復(fù)雜網(wǎng)絡(luò)可以被建模三元組G=(V,E,A),其中V={v1,v2,…,vn}表示節(jié)點(diǎn)集合,n代表網(wǎng)絡(luò)節(jié)點(diǎn)數(shù).E={(vi,vj)|vi,vj∈V,i≠j},表示網(wǎng)絡(luò)邊的集合,A=[a1,a2,…,an]T∈R|v|×m表示節(jié)點(diǎn)的屬性矩陣.

定義2節(jié)點(diǎn)嵌入向量:節(jié)點(diǎn)嵌入向量是指將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)表示為一個(gè)低維的實(shí)數(shù)向量,它們可以將節(jié)點(diǎn)間的拓?fù)渑c屬性結(jié)構(gòu)信息轉(zhuǎn)換為低維向量空間中的向量,從而可以在向量空間中進(jìn)行節(jié)點(diǎn)的聚類(lèi)操作.

定義3模塊度Q:模塊度Q是復(fù)雜網(wǎng)絡(luò)中用于衡量社區(qū)結(jié)構(gòu)的一種指標(biāo),通常用符號(hào)Q表示.它衡量了某種分割方式下,網(wǎng)絡(luò)中的節(jié)點(diǎn)分配到社區(qū)的緊密程度與該分割方式隨機(jī)下產(chǎn)生的網(wǎng)絡(luò)中的節(jié)點(diǎn)分配到社區(qū)的緊密程度之差.

(1)

式(1)中:1=

定義4節(jié)點(diǎn)屬性相似度s(i,j):節(jié)點(diǎn)屬性相似度用來(lái)刻畫(huà)兩個(gè)節(jié)點(diǎn)關(guān)于屬性上的相似情況,兩個(gè)節(jié)點(diǎn)越相似,則兩節(jié)點(diǎn)的屬性相似度越高.

s(i,j)定義為:

(2)

定義5社區(qū)內(nèi)屬性相似度SA.社區(qū)內(nèi)屬性相似度SA是社區(qū)發(fā)現(xiàn)中用于衡量在屬性上劃分社區(qū)的質(zhì)量.當(dāng)同一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)屬性越相似,則社區(qū)內(nèi)屬性相似度SA越高.

(3)

式(3)中:c是劃分社區(qū)的總數(shù),ck表示第k個(gè)社區(qū)的節(jié)點(diǎn)集合,s(i,j)定義節(jié)點(diǎn)間的屬性相似度,rk為第k個(gè)社區(qū)的節(jié)點(diǎn)個(gè)數(shù).

多目標(biāo)優(yōu)化:多目標(biāo)優(yōu)化研究如何在具有多個(gè)目標(biāo)的優(yōu)化問(wèn)題中找到一組最優(yōu)解.在傳統(tǒng)的單目標(biāo)優(yōu)化問(wèn)題中,目標(biāo)函數(shù)單一,優(yōu)化目標(biāo)是最小化或最大化一個(gè)特定的目標(biāo).而在多目標(biāo)優(yōu)化問(wèn)題中,存在多個(gè)目標(biāo)函數(shù),無(wú)法簡(jiǎn)單地將它們歸納為單一目標(biāo)函數(shù).在多目標(biāo)優(yōu)化理論中,存在解支配關(guān)系.在兩解x,y中,如果x在所有目標(biāo)上優(yōu)于y,則稱(chēng)解x支配解y,x為非支配解.支配關(guān)系表示解之間的優(yōu)劣關(guān)系.而帕累托解集是一組非支配解的集合,表示了多目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解的信息,多目標(biāo)優(yōu)化算法旨在搜索并逼近帕累托解集.在基于多目標(biāo)的屬性網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中,研究重點(diǎn)在于如何利用蘊(yùn)含在節(jié)點(diǎn)中的屬性信息以及節(jié)點(diǎn)間的結(jié)構(gòu)關(guān)系,去檢測(cè)潛在的社區(qū):(1)在結(jié)構(gòu)上,檢測(cè)出的社區(qū)內(nèi)部節(jié)點(diǎn)的邊較為密集,而社區(qū)間節(jié)點(diǎn)的邊較為稀疏;(2)在屬性上,同一個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)屬性相似度較高.因此基于多目標(biāo)優(yōu)化的屬性網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題可以建模為:min{Q,SA}.

1.2 FEV-MOEA算法框架

FEV-MOEA 的算法框架如圖1所示,由三個(gè)階段構(gòu)成,分別為圖增強(qiáng)、嵌入向量生成以及個(gè)體初始化階段、種群與帕累托前沿的更新階段、以及后處理修正階段.在階段一中,首先,將原始圖根據(jù)屬性信息構(gòu)造增強(qiáng)圖,使得圖上的屬性信息更加豐富.接著,利用DeepWalk分別獲得結(jié)構(gòu)、屬性上的嵌入向量.最后,根據(jù)嵌入向量初始化個(gè)體.階段二將個(gè)體進(jìn)行交叉、變異與選擇操作來(lái)更新種群在解空間搜尋優(yōu)秀個(gè)體.階段三將帕累托解集進(jìn)行后處理修正,使得可行解能夠避免陷入局部最優(yōu)的問(wèn)題.

圖1 FEV-MOEA算法框架

1.3 圖增強(qiáng)、嵌入向量生成及種群初始化

1.3.1 圖增強(qiáng)

圖2表示k=2時(shí),節(jié)點(diǎn)5的圖增強(qiáng)示意圖.

圖2 圖增強(qiáng)示意圖

在屬性網(wǎng)絡(luò)中,存在著一類(lèi)結(jié)構(gòu)與屬性信息不一致的社區(qū),即在社區(qū)內(nèi)的節(jié)點(diǎn)在結(jié)構(gòu)上并沒(méi)有明顯的社區(qū)邊界,甚至出現(xiàn)隸屬于同一個(gè)社區(qū)的節(jié)點(diǎn)在不同的連通分支,但它們的屬性相類(lèi)似.這種結(jié)構(gòu)與屬性信息不一致的網(wǎng)絡(luò)會(huì)導(dǎo)致算法精度降低,為了更好地識(shí)別節(jié)點(diǎn)之間的潛在關(guān)系,需要根據(jù)節(jié)點(diǎn)間的屬性對(duì)原始圖結(jié)構(gòu)進(jìn)行增強(qiáng),通過(guò)增強(qiáng)的圖結(jié)構(gòu),可以更準(zhǔn)確地識(shí)別節(jié)點(diǎn)之間的社區(qū),從而更好地理解復(fù)雜系統(tǒng)中節(jié)點(diǎn)之間的相互作用.具體圖增強(qiáng)策略如下:對(duì)于每個(gè)節(jié)點(diǎn)V,計(jì)算出前k個(gè)與其節(jié)點(diǎn)屬性相似度最大的節(jié)點(diǎn)集合,將V與節(jié)點(diǎn)集合里的每個(gè)節(jié)點(diǎn)新增一條邊完成圖增強(qiáng).

1.3.2 嵌入向量生成

FEV-MOEA解碼時(shí)需要結(jié)合結(jié)構(gòu)、屬性嵌入向量得到最終的社區(qū)劃分,因此需要生成對(duì)應(yīng)的結(jié)構(gòu)、屬性嵌入向量用于后續(xù)個(gè)體的解碼.FEV-MOEA采用DeepWalk[9]算法分別生成結(jié)構(gòu)、屬性嵌入向量.DeepWalk是一種基于隨機(jī)游走的網(wǎng)絡(luò)嵌入方法,用于將節(jié)點(diǎn)映射到低維向量空間中,它通過(guò)捕捉節(jié)點(diǎn)在網(wǎng)絡(luò)中的局部鄰域來(lái)捕捉節(jié)點(diǎn)的相似性,并將其表示為低維向量,DeepWalk由隨機(jī)游走與Skip-gram模型兩個(gè)關(guān)鍵步驟組成,隨機(jī)游走生成了大量的遍歷序列,而Skip-gram模型將這些序列看作自然語(yǔ)言中的句子,并通過(guò)最大化預(yù)測(cè)周?chē)?jié)點(diǎn)出現(xiàn)概率的目標(biāo)函數(shù)來(lái)學(xué)習(xí)節(jié)點(diǎn)向量表示.圖3展示了結(jié)構(gòu)嵌入向量與屬性嵌入向量的生成例子.針對(duì)結(jié)構(gòu)嵌入向量初始化,游走序列采取原始圖上的隨機(jī)游走,而針對(duì)屬性嵌入向量初始化,游走序列采取增強(qiáng)圖上的隨機(jī)游走.

圖3 結(jié)合DeepWalk生成嵌入向量

1.3.3 種群初始化

在進(jìn)化計(jì)算的社區(qū)發(fā)現(xiàn)算法中,傳統(tǒng)的編碼方案分基于節(jié)點(diǎn)標(biāo)簽的編碼方案(Label-based)與基于鄰居節(jié)點(diǎn)的編碼方案(Locus-based)兩種.Label-based編碼將每個(gè)節(jié)點(diǎn)編碼成一個(gè)基因位,每個(gè)基因位的值表示節(jié)點(diǎn)所屬的社區(qū),解碼時(shí)每個(gè)基因的值就代表著該節(jié)點(diǎn)隸屬的社區(qū).該編碼方案需要將編碼進(jìn)行離散化編碼,會(huì)丟失節(jié)點(diǎn)之間的連續(xù)性信息,可能會(huì)導(dǎo)致進(jìn)化失去部分信息.

而Locus-based是將每個(gè)節(jié)點(diǎn)編碼成一個(gè)基因位,每個(gè)基因位的值標(biāo)識(shí)該節(jié)點(diǎn)的某個(gè)鄰居節(jié)點(diǎn)的編號(hào),解碼時(shí)將該節(jié)點(diǎn)與其基因值對(duì)應(yīng)的鄰居節(jié)點(diǎn)劃分為同一個(gè)社區(qū).現(xiàn)有編碼方案難以克服局部最優(yōu),比如,若一個(gè)節(jié)點(diǎn)在進(jìn)化過(guò)程中被分配到一個(gè)錯(cuò)誤的標(biāo)簽時(shí),其周?chē)墓?jié)點(diǎn)也可能被分配到相同的錯(cuò)誤標(biāo)簽,可能會(huì)導(dǎo)致算法陷入局部最優(yōu),同時(shí)因受到網(wǎng)絡(luò)結(jié)構(gòu)的影響,劃分社區(qū)的節(jié)點(diǎn)必須在同一個(gè)連通分支.

在FEV-MOEA中,設(shè)計(jì)一個(gè)基于融合系數(shù)的編碼及解碼方案,圖4為基于融合系數(shù)的編碼示意圖.如圖4所示,增強(qiáng)圖共有8個(gè)節(jié)點(diǎn),編碼時(shí)將每個(gè)節(jié)點(diǎn)編碼成一個(gè)基因位,每個(gè)基因值代表著該節(jié)點(diǎn)關(guān)于結(jié)構(gòu)、屬性嵌入向量的融合程度,具體基因值的初始化詳見(jiàn)InitialPopu偽代碼.圖5為基于融合系數(shù)的解碼示意圖,其中,gen(i)表示i節(jié)點(diǎn)對(duì)應(yīng)的融合系數(shù),Si表示i節(jié)點(diǎn)的結(jié)構(gòu)嵌入向量,Ai表示i節(jié)點(diǎn)的屬性嵌入向量.結(jié)合Si與Ai,可以通過(guò)公式gen(i)*Si+(1-gen(i))*Ai計(jì)算加權(quán)后節(jié)點(diǎn)i的融合嵌入向量Fi.當(dāng)節(jié)點(diǎn)1的結(jié)構(gòu)嵌入向量S1為[40,50],屬性嵌入向量A1為[80,60]時(shí),則融合嵌入向量F1=0.63*[40,50]+0.37*[80,60]=[55,54].計(jì)算所有節(jié)點(diǎn)的融合嵌入向量F后,結(jié)合Kmeans[10]聚類(lèi)算法得到最終的社區(qū)劃分.

圖4 基于融合系數(shù)的編碼方案

圖5 基于融合系數(shù)的解碼示例

1.4 種群更新

種群初始化后需要經(jīng)過(guò)多次選擇、交叉與變異算子使得種群逼近全局最優(yōu)解.為了適配提出的基于融合系數(shù)的編碼方案,本文的選擇算子為錦標(biāo)賽選擇算子,錦標(biāo)賽選擇算子是一種常用的選擇算子,其思想是隨機(jī)選擇一定數(shù)量的個(gè)體作為競(jìng)爭(zhēng)者,從中隨機(jī)選擇若干個(gè)非支配解,作為下一代的子種群的父代.而交叉算子采取模擬二進(jìn)制交叉,模擬二進(jìn)制交叉是一種常用的交叉算子,其主要過(guò)程是先選擇倆個(gè)父代個(gè)體,再對(duì)于每對(duì)等位基因確定其交叉概率和分布指數(shù),計(jì)算最終交叉的中間變量得到子代交叉后的基因值.而變異算子采用多項(xiàng)式變異,多項(xiàng)式變異可以用于連續(xù)值編碼的變異操作,增加搜索空間的探索能力,其主要思想是對(duì)于每一個(gè)基因,計(jì)算其變異區(qū)間,再根據(jù)變異區(qū)間的范圍對(duì)基因值進(jìn)行變異操作,變異區(qū)間的大小會(huì)受到變異概率的影響.父種群經(jīng)過(guò)多次的選擇、交叉與變異操作后得到子種群,接著通過(guò)父、子種群的目標(biāo)函數(shù)值選出帕累托解集,從帕累托解集中選擇若干個(gè)個(gè)體參與下輪種群的更新迭代,直至迭代次數(shù)達(dá)到最大次數(shù).

1.5 后處理節(jié)點(diǎn)修正

復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)與屬性的復(fù)雜性和規(guī)模會(huì)影響算法的效果,當(dāng)社交網(wǎng)絡(luò)結(jié)構(gòu)較為復(fù)雜時(shí),算法容易出現(xiàn)局部最優(yōu)解.為避免算法陷入局部最優(yōu),提出一種基于目標(biāo)函數(shù)最優(yōu)的節(jié)點(diǎn)修正策略,策略將帕累托解集中的邊緣節(jié)點(diǎn)所屬社區(qū)進(jìn)行修正,使得修正后的社區(qū)劃分結(jié)果具有更高的模塊度Q與社區(qū)內(nèi)屬性相似度SA,以克服局部最優(yōu)的問(wèn)題,提高社區(qū)劃分的精度.

在后處理節(jié)點(diǎn)修正方案中,首先,計(jì)算出社區(qū)劃分的目標(biāo)函數(shù)模塊度Q1與社區(qū)內(nèi)屬性相似度SA1.其次,找到與其他社區(qū)有連接邊的節(jié)點(diǎn), 稱(chēng)之為邊緣節(jié)點(diǎn).接著,將這些邊緣節(jié)點(diǎn)嘗試加入到相鄰社區(qū),重新計(jì)算目標(biāo)函數(shù)模塊度Q2與社區(qū)內(nèi)屬性相似度SA2.最后,當(dāng)Q2>Q1且SA2>SA1時(shí),則將這些邊緣節(jié)點(diǎn)加入到相鄰社區(qū),否則不加入.圖6為后處理修正的例子,其中修正前節(jié)點(diǎn)1、3、5為邊緣節(jié)點(diǎn),當(dāng)邊緣節(jié)點(diǎn)1和3嘗試加入到相鄰社區(qū)時(shí),模塊度Q與社區(qū)內(nèi)屬性相似度SA并不會(huì)提高,因此邊緣節(jié)點(diǎn)1和3的社區(qū)標(biāo)簽并不進(jìn)行修正,而邊緣節(jié)點(diǎn)5嘗試加入到相鄰社區(qū)時(shí),模塊度Q與社區(qū)內(nèi)屬性相似度SA都會(huì)提高,因此將邊緣節(jié)點(diǎn)5加入到鄰近社區(qū),社區(qū)標(biāo)簽進(jìn)行修正.修正后,邊緣節(jié)點(diǎn)為5、7,而節(jié)點(diǎn)5、7嘗試加入到鄰近社區(qū)都不會(huì)使模塊度Q與社區(qū)內(nèi)屬性相似度SA提高,后處理修正結(jié)束.

圖6 后處理修正

1.6 算法偽代碼

FEV-MOEA算法基于NSGA-II進(jìn)化框架進(jìn)行實(shí)現(xiàn).(Non-dominated Sorting Genetic Algorithm II,NSGA-II):NSGA-II是一種常用的多目標(biāo)進(jìn)化計(jì)算方法,它是基于遺傳算法的一種擴(kuò)展,能夠同時(shí)優(yōu)化多個(gè)目標(biāo)函數(shù).以下是FEV-MOEA的算法偽代碼:

FEV-MOEA算法偽代碼輸入:G=(V,E,A); // 屬性網(wǎng)絡(luò)圖增強(qiáng)條數(shù)k;種群規(guī)模n;最大迭代次數(shù)T;交叉概率pc;變異概率pm;輸出:社區(qū)劃分集合 C// 階段一 圖增強(qiáng)、嵌入向量生成以及種群初始化1.t=1;2.G'←enhance(G,k) //根據(jù)1.3節(jié)對(duì)原始圖G進(jìn)行增強(qiáng),生成增強(qiáng)圖G'3.SV←DeepWalk(G) //根據(jù)原始圖G利用DeepWalk算法生成結(jié)構(gòu)嵌入向量SV4.AV←DeepWalk(G') //根據(jù)增強(qiáng)圖G'利用DeepWalk算法生成屬性嵌入向量AV5.Pt←InitialPopu() //進(jìn)行種群的初始化// 階段二 種群更新6.While t < T do7.Set Qt={}//子種群Qt8.While |Qt| < n do9.X1,X2←TournamentSelection(Pt); //競(jìng)標(biāo)賽選擇10.X1,X2←SBX(X1,X2,pc); //模擬二進(jìn)制交叉11.X1,X2←PolynomialMutate(X1,X2,pm); //多項(xiàng)式變異12.Qt=Qt∪{X1,X2};13.End 14.Pt+1=Pt∪Qt //將子種群和父種群融合15.F=(Q(Pt+1),SA(Pt+1)) //Fc 計(jì)算子代的目標(biāo)函數(shù)值16.PS←ParetoSet(Pt+1,F) // 根據(jù)目標(biāo)函數(shù)值F獲得帕累托解集17.Pt+1←SelectN(PS,n); // 選擇前n個(gè)非支配解集進(jìn)行下一代種群的更新18.t=t+119.End // 階段三 帕累托解集的后處理得到社區(qū)劃分集合C20.Set C={}//社區(qū)劃分結(jié)果 21.For ind in PS:22.com=decode(ind,SV,AV); //根據(jù)1.5節(jié)對(duì)個(gè)體進(jìn)行解碼獲得社區(qū)劃分com23.com=PostProcess(com); // 根據(jù)1.6節(jié)對(duì)個(gè)體進(jìn)行后處理修正24.C=C ∪ com25.Return C

enhance( )函數(shù)對(duì)原始圖進(jìn)行增強(qiáng),偽代碼如下:

enhance()函數(shù)偽代碼輸入:G=(V,E,A); // 屬性網(wǎng)絡(luò)原始圖,圖增強(qiáng)條數(shù) k;輸出:增強(qiáng)圖G' 1. G'=G 2. For i=1 to |N| do:3. sim=[] //節(jié)點(diǎn)i的屬性相似度列表4. For j=1 to |N| do:5. sim .add(s(i,j) ) // 節(jié)點(diǎn)屬性相似度s(i,j)6. similar_nodes=sort(sim) //根據(jù)屬性相似度降序排序,得到對(duì)應(yīng)的節(jié)點(diǎn)列表7. For n in similar_nodes:8. G'.addEdge(i,n) //添加一條從節(jié)點(diǎn)i到相似節(jié)點(diǎn)n的邊 Return G'

InitialPopu( )函數(shù)用于種群初始化,其偽代碼為:

InitialPopu算法偽代碼輸入:G=(V,E,A); // 屬性網(wǎng)絡(luò),種群規(guī)模 n;輸出:P //初始種群1.P={}2.For k=1 to n do:3. For i=1 to |N| do:4. Xk(gen(i))=1-s(i,j) //第k個(gè)個(gè)體節(jié)點(diǎn)i的融合系數(shù) 5. P←Xk6.Return P

2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證FEV-MOEA算法的性能,本文選擇6個(gè)對(duì)比算法在真實(shí)數(shù)據(jù)集與人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).其中,DeepWalk與Node2Vec[11]是基于隨機(jī)游走的算法, SCI[12]與VGraph[13]是基于模型的算法,而RMOEA[5]與RWECD[14]是基于進(jìn)化計(jì)算的算法.所有對(duì)比算法的參數(shù)都與原論文保持一致.

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

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

表1給出了以上6個(gè)真實(shí)網(wǎng)絡(luò)的具體參數(shù)信息.

表1 真實(shí)網(wǎng)絡(luò)參數(shù)

在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)上,本文選擇了6個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)以驗(yàn)證FEV-MOEA算法的有效性,分別包含:WebKB[15]中四個(gè)美國(guó)大學(xué)的計(jì)算機(jī)交流網(wǎng)絡(luò)Cornell、Texas、Washington、Wisconsin與兩個(gè)科學(xué)引用網(wǎng)絡(luò)Cora[16]、Citeseer[16].

2.1.2 人工網(wǎng)絡(luò)數(shù)據(jù)集

實(shí)驗(yàn)采用LFR[17]網(wǎng)絡(luò)生成工具生成只包含結(jié)構(gòu)信息的人工網(wǎng)絡(luò),利用文獻(xiàn)[18]的方案為每個(gè)節(jié)點(diǎn)生成對(duì)應(yīng)的屬性信息.兩組具有不同參數(shù)設(shè)置的人工網(wǎng)絡(luò)D1、D2用于驗(yàn)證算法的有效性,具體參數(shù)及設(shè)置如表2所示,其余未說(shuō)明的參數(shù)設(shè)置為L(zhǎng)FR工具的默認(rèn)值.D1網(wǎng)絡(luò)側(cè)重于實(shí)驗(yàn)不同的μ值對(duì)算法精度的影響,μ值代表社區(qū)的混合程度,μ值越大,則社區(qū)結(jié)構(gòu)越模糊,算法越難劃分出正確的社區(qū).而D2網(wǎng)絡(luò)側(cè)重于實(shí)驗(yàn)不同網(wǎng)絡(luò)規(guī)模變化對(duì)算法精度的影響,N值越大,則網(wǎng)絡(luò)規(guī)模越大.

表2 人工網(wǎng)絡(luò)D1、D2的參數(shù)設(shè)置

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

采用標(biāo)準(zhǔn)互信息NMI[19]與平衡分?jǐn)?shù)F1[20]

對(duì)算法的結(jié)果進(jìn)行評(píng)價(jià).NMI定義如下:

(4)

NMI度量?jī)蓚€(gè)聚類(lèi)結(jié)果相似程度的指標(biāo),其值在 [0,1] 之間,數(shù)值越大表示聚類(lèi)結(jié)果越相似.其中,CA、CB分別表示真實(shí)社區(qū)劃分與預(yù)測(cè)的社區(qū)劃分結(jié)果;Nij表示同時(shí)被分配到CA中第i個(gè)社區(qū)與CB中第j個(gè)社區(qū)的節(jié)點(diǎn)數(shù)量,Ni表示CA中第i個(gè)社區(qū)的節(jié)點(diǎn)數(shù)量,Nj表示CB中第j個(gè)社區(qū)的節(jié)點(diǎn)數(shù)量.

F1 用于衡量算法精確性和召回率的指標(biāo),F1定義如下:

(5)

(6)

(7)

式(7)中:F1值在 [0,1]之間,數(shù)值越大表示算法性能越好.TP表示在同一真實(shí)社區(qū)的節(jié)點(diǎn)被劃分到相同社區(qū)的節(jié)點(diǎn)對(duì)個(gè)數(shù),TN表示在不同真實(shí)社區(qū)的節(jié)點(diǎn)被劃分到不同社區(qū)的節(jié)點(diǎn)對(duì)個(gè)數(shù),FP表示在不同真實(shí)社區(qū)的節(jié)點(diǎn)被劃分到相同社區(qū)的節(jié)點(diǎn)對(duì)個(gè)數(shù),FN表示在相同真實(shí)社區(qū)的節(jié)點(diǎn)被劃分到不同社區(qū)的節(jié)點(diǎn)對(duì)個(gè)數(shù).

2.3 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖7、圖8分別為FEV-MOEA與其它6種對(duì)比算法在不同真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集下的精度實(shí)驗(yàn),其中圖7為NMI精度實(shí)驗(yàn),圖8為F1精度實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,FEV-MOEA在各個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的精度效果最佳,說(shuō)明FEV-MOEA算法相較于傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法在屬性網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)上具有更好的精度,這是因?yàn)镕EV-MOEA算法的編碼方案能夠有效提取每個(gè)節(jié)點(diǎn)的屬性與結(jié)構(gòu)信息,并通過(guò)后處理修正的策略,提高社區(qū)發(fā)現(xiàn)的精度.其中,DeepWalk、Node2Vec、RMOEA與VGraph算法只考慮了結(jié)構(gòu)信息,因此在各個(gè)數(shù)據(jù)集上的效果不佳.而SCI與RWECD算法雖然考慮了屬性信息,但是沒(méi)有考慮到網(wǎng)絡(luò)中可能存在著屬性信息與結(jié)構(gòu)信息不匹配的問(wèn)題,因此雖然精度有所提升,但是也沒(méi)有達(dá)到較高的精度.

圖7 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集NMI實(shí)驗(yàn)

圖8 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集F1實(shí)驗(yàn)

2.4 人工網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖9顯示了FEV-MOEA算法與其它6種對(duì)比算法在D1網(wǎng)絡(luò)組上關(guān)于社區(qū)混合參數(shù)μ的精度實(shí)驗(yàn).從圖9可以看出,所有算法的NMI值都隨著社區(qū)混合參數(shù)μ的增加而減少,這是因?yàn)樯鐓^(qū)混合參數(shù)μ值越大,說(shuō)明社區(qū)結(jié)構(gòu)越模糊,算法越難檢測(cè)到正確的社區(qū)劃分.FEV-MOEA算法的精度雖然隨著μ值的增加而降低,但是相較于其它比較算法,其精度下降的較為平緩,這是因?yàn)榧词乖诿鎸?duì)社區(qū)結(jié)構(gòu)模糊的網(wǎng)絡(luò)時(shí),FEV-MOEA算法通過(guò)綜合考慮網(wǎng)絡(luò)中的屬性信息來(lái)彌補(bǔ)結(jié)構(gòu)信息的不足,進(jìn)而提高社區(qū)劃分的精度.

圖9 不同混合參數(shù)μ的實(shí)驗(yàn)結(jié)果

圖10、圖11顯示了FEV-MOEA算法與其它6種對(duì)比算法在D2網(wǎng)絡(luò)組上的精度實(shí)驗(yàn),其中圖10為NMI精度實(shí)驗(yàn),圖11為F1精度實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,在各個(gè)規(guī)模的數(shù)據(jù)集下,FEV-MOEA算法都保持著最高的精度.網(wǎng)絡(luò)規(guī)模越大意味著網(wǎng)絡(luò)的結(jié)構(gòu)會(huì)更加復(fù)雜,而FEV-MOEA算法通過(guò)融合節(jié)點(diǎn)的屬性信息與后處理修正策略,能夠在不同規(guī)模的網(wǎng)絡(luò)下保持良好的魯棒性與準(zhǔn)確性.

圖10 人工網(wǎng)絡(luò)數(shù)據(jù)集NMI實(shí)驗(yàn)

因此,FEV-MOEA算法隨著網(wǎng)絡(luò)規(guī)模的增加,其精度一直保持在較高的水平并且沒(méi)有較大的波動(dòng).而其余6種對(duì)比算法隨著網(wǎng)絡(luò)規(guī)模的增加,精度波動(dòng)的幅度較大,說(shuō)明其魯棒性較差,無(wú)法在不同規(guī)模網(wǎng)絡(luò)下進(jìn)行有效的社區(qū)發(fā)現(xiàn).

3 結(jié)論

本文提出了一種基于融合嵌入向量的多目標(biāo)優(yōu)化社區(qū)發(fā)現(xiàn)算法FEV-MOEA.與傳統(tǒng)編解碼方案不同,該算法的編解碼方案能夠利用到每個(gè)節(jié)點(diǎn)的屬性與結(jié)構(gòu)嵌入向量,使得算法能夠不受到網(wǎng)絡(luò)結(jié)構(gòu)的限制繼而發(fā)現(xiàn)高質(zhì)量的社區(qū).同時(shí),設(shè)計(jì)一個(gè)后處理社區(qū)修正的策略,使得算法的解能夠克服陷入局部最優(yōu)的問(wèn)題,提高社區(qū)發(fā)現(xiàn)的精度.通過(guò)在真實(shí)網(wǎng)絡(luò)和人工網(wǎng)絡(luò)數(shù)據(jù)集上實(shí)驗(yàn),驗(yàn)證了FEV-MOEA算法能夠在復(fù)雜屬性網(wǎng)絡(luò)上進(jìn)行高精度的社區(qū)發(fā)現(xiàn).未來(lái),在現(xiàn)有工作基礎(chǔ)上,針對(duì)異構(gòu)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)展開(kāi)探索,將異構(gòu)網(wǎng)絡(luò)中不同類(lèi)型的信息與進(jìn)化計(jì)算相結(jié)合以檢測(cè)高質(zhì)量的社區(qū).