基于融合嵌入向量的多目標優化社區發現

韓存鴿, 陳展鴻, 郭 昆*

(1.武夷學院 數學與計算機學院 福建省茶產業大數據應用與智能化重點實驗室, 福建 武夷山 354300; 2.福州大學 計算機與大數據學院, 福建 福州 350108)

0 引言

現實世界中的許多復雜系統都可以建模為網絡,如生物網絡、社交網絡、科學合作網絡等.在這些網絡中,節點之間的連接關系非常復雜,節點的度、聚集系數、連通性等屬性也各不相同.社區發現[1]是復雜網絡研究中的一個重要領域,其主要目的是發現網絡中的社區結構.社區發現可以從節點屬性角度進行分類,分為無屬性網絡和屬性網絡的社區發現.在過去,許多社區發現算法僅考慮網絡結構,忽略了節點間的屬性信息.然而,現實世界中許多網絡都具有屬性,如社交網絡中的個人資料信息、科學合作網絡中的學科領域等.

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

目前,基于屬性網絡多目標優化進化社區發現算法(MOEAs)主要面臨兩個挑戰:(1)編碼方式都直接或間接使用鄰接編碼策略,使得算法的搜索能力易受網絡結構限制,社區劃分的質量不高;(2)進化算法容易陷入局部最優,導致社區發現的精度不高.

針對以上問題,本文提出一種基于融合嵌入向量的多目標優化社區發現算法FEV-MOEA(Fusion Embedding Vector MOEA),首先,設計一種基于融合系數的編解碼方案,通過利用每個節點的屬性與結構嵌入向量,以克服算法對網絡結構的限制,提高社區劃分質量.其次,提出一種后處理節點修正策略,通過該策略對社區劃分結果進行修正,提高社區劃分的精度.主要創新點如下:

(1)通過設計融合系數編解碼方案,充分利用節點屬性、結構嵌入向量.編碼時,采用連續值編碼方式,將每個節點編碼成一個基因位,每個基因值表示該節點結構、屬性嵌入向量的融合程度,避免了傳統編碼方案中丟失節點間連續信息的問題.解碼時,根據融合嵌入向量結合聚類算法,使得解碼方式不受網絡結構的限制,以提升社區發現的質量.

(2)通過設計后處理節點修正策略,不斷優化新社區的模塊度與社區內屬性相似度,使得算法的解能夠克服陷入局部最優的問題,提高社區發現的精度.

(3)通過在真實和人工數據集上實驗,驗證了FEV-MOEA算法能夠有效提高社區發現的精度.

1 FEV-MOEA算法

1.1 基本概念

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

定義2節點嵌入向量:節點嵌入向量是指將網絡中的每個節點表示為一個低維的實數向量,它們可以將節點間的拓撲與屬性結構信息轉換為低維向量空間中的向量,從而可以在向量空間中進行節點的聚類操作.

定義3模塊度Q:模塊度Q是復雜網絡中用于衡量社區結構的一種指標,通常用符號Q表示.它衡量了某種分割方式下,網絡中的節點分配到社區的緊密程度與該分割方式隨機下產生的網絡中的節點分配到社區的緊密程度之差.

(1)

式(1)中:1=

定義4節點屬性相似度s(i,j):節點屬性相似度用來刻畫兩個節點關于屬性上的相似情況,兩個節點越相似,則兩節點的屬性相似度越高.

s(i,j)定義為:

(2)

定義5社區內屬性相似度SA.社區內屬性相似度SA是社區發現中用于衡量在屬性上劃分社區的質量.當同一個社區內的節點屬性越相似,則社區內屬性相似度SA越高.

(3)

式(3)中:c是劃分社區的總數,ck表示第k個社區的節點集合,s(i,j)定義節點間的屬性相似度,rk為第k個社區的節點個數.

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

1.2 FEV-MOEA算法框架

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

圖1 FEV-MOEA算法框架

1.3 圖增強、嵌入向量生成及種群初始化

1.3.1 圖增強

圖2表示k=2時,節點5的圖增強示意圖.

圖2 圖增強示意圖

在屬性網絡中,存在著一類結構與屬性信息不一致的社區,即在社區內的節點在結構上并沒有明顯的社區邊界,甚至出現隸屬于同一個社區的節點在不同的連通分支,但它們的屬性相類似.這種結構與屬性信息不一致的網絡會導致算法精度降低,為了更好地識別節點之間的潛在關系,需要根據節點間的屬性對原始圖結構進行增強,通過增強的圖結構,可以更準確地識別節點之間的社區,從而更好地理解復雜系統中節點之間的相互作用.具體圖增強策略如下:對于每個節點V,計算出前k個與其節點屬性相似度最大的節點集合,將V與節點集合里的每個節點新增一條邊完成圖增強.

1.3.2 嵌入向量生成

FEV-MOEA解碼時需要結合結構、屬性嵌入向量得到最終的社區劃分,因此需要生成對應的結構、屬性嵌入向量用于后續個體的解碼.FEV-MOEA采用DeepWalk[9]算法分別生成結構、屬性嵌入向量.DeepWalk是一種基于隨機游走的網絡嵌入方法,用于將節點映射到低維向量空間中,它通過捕捉節點在網絡中的局部鄰域來捕捉節點的相似性,并將其表示為低維向量,DeepWalk由隨機游走與Skip-gram模型兩個關鍵步驟組成,隨機游走生成了大量的遍歷序列,而Skip-gram模型將這些序列看作自然語言中的句子,并通過最大化預測周圍節點出現概率的目標函數來學習節點向量表示.圖3展示了結構嵌入向量與屬性嵌入向量的生成例子.針對結構嵌入向量初始化,游走序列采取原始圖上的隨機游走,而針對屬性嵌入向量初始化,游走序列采取增強圖上的隨機游走.

圖3 結合DeepWalk生成嵌入向量

1.3.3 種群初始化

在進化計算的社區發現算法中,傳統的編碼方案分基于節點標簽的編碼方案(Label-based)與基于鄰居節點的編碼方案(Locus-based)兩種.Label-based編碼將每個節點編碼成一個基因位,每個基因位的值表示節點所屬的社區,解碼時每個基因的值就代表著該節點隸屬的社區.該編碼方案需要將編碼進行離散化編碼,會丟失節點之間的連續性信息,可能會導致進化失去部分信息.

而Locus-based是將每個節點編碼成一個基因位,每個基因位的值標識該節點的某個鄰居節點的編號,解碼時將該節點與其基因值對應的鄰居節點劃分為同一個社區.現有編碼方案難以克服局部最優,比如,若一個節點在進化過程中被分配到一個錯誤的標簽時,其周圍的節點也可能被分配到相同的錯誤標簽,可能會導致算法陷入局部最優,同時因受到網絡結構的影響,劃分社區的節點必須在同一個連通分支.

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

圖4 基于融合系數的編碼方案

圖5 基于融合系數的解碼示例

1.4 種群更新

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

1.5 后處理節點修正

復雜網絡結構與屬性的復雜性和規模會影響算法的效果,當社交網絡結構較為復雜時,算法容易出現局部最優解.為避免算法陷入局部最優,提出一種基于目標函數最優的節點修正策略,策略將帕累托解集中的邊緣節點所屬社區進行修正,使得修正后的社區劃分結果具有更高的模塊度Q與社區內屬性相似度SA,以克服局部最優的問題,提高社區劃分的精度.

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

圖6 后處理修正

1.6 算法偽代碼

FEV-MOEA算法基于NSGA-II進化框架進行實現.(Non-dominated Sorting Genetic Algorithm II,NSGA-II):NSGA-II是一種常用的多目標進化計算方法,它是基于遺傳算法的一種擴展,能夠同時優化多個目標函數.以下是FEV-MOEA的算法偽代碼:

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

enhance( )函數對原始圖進行增強,偽代碼如下:

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

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

InitialPopu算法偽代碼輸入:G=(V,E,A); // 屬性網絡,種群規模 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個個體節點i的融合系數 5. P←Xk6.Return P

2 實驗結果與分析

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

2.1 實驗數據集

2.1.1 真實網絡數據集

表1給出了以上6個真實網絡的具體參數信息.

表1 真實網絡參數

在真實網絡數據集實驗上,本文選擇了6個數據集進行實驗以驗證FEV-MOEA算法的有效性,分別包含:WebKB[15]中四個美國大學的計算機交流網絡Cornell、Texas、Washington、Wisconsin與兩個科學引用網絡Cora[16]、Citeseer[16].

2.1.2 人工網絡數據集

實驗采用LFR[17]網絡生成工具生成只包含結構信息的人工網絡,利用文獻[18]的方案為每個節點生成對應的屬性信息.兩組具有不同參數設置的人工網絡D1、D2用于驗證算法的有效性,具體參數及設置如表2所示,其余未說明的參數設置為LFR工具的默認值.D1網絡側重于實驗不同的μ值對算法精度的影響,μ值代表社區的混合程度,μ值越大,則社區結構越模糊,算法越難劃分出正確的社區.而D2網絡側重于實驗不同網絡規模變化對算法精度的影響,N值越大,則網絡規模越大.

表2 人工網絡D1、D2的參數設置

2.2 評價指標

采用標準互信息NMI[19]與平衡分數F1[20]

對算法的結果進行評價.NMI定義如下:

(4)

NMI度量兩個聚類結果相似程度的指標,其值在 [0,1] 之間,數值越大表示聚類結果越相似.其中,CA、CB分別表示真實社區劃分與預測的社區劃分結果;Nij表示同時被分配到CA中第i個社區與CB中第j個社區的節點數量,Ni表示CA中第i個社區的節點數量,Nj表示CB中第j個社區的節點數量.

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

(5)

(6)

(7)

式(7)中:F1值在 [0,1]之間,數值越大表示算法性能越好.TP表示在同一真實社區的節點被劃分到相同社區的節點對個數,TN表示在不同真實社區的節點被劃分到不同社區的節點對個數,FP表示在不同真實社區的節點被劃分到相同社區的節點對個數,FN表示在相同真實社區的節點被劃分到不同社區的節點對個數.

2.3 真實網絡數據集實驗結果

圖7、圖8分別為FEV-MOEA與其它6種對比算法在不同真實網絡數據集下的精度實驗,其中圖7為NMI精度實驗,圖8為F1精度實驗.實驗結果表明,FEV-MOEA在各個真實網絡數據集上的精度效果最佳,說明FEV-MOEA算法相較于傳統的社區發現算法在屬性網絡社區發現上具有更好的精度,這是因為FEV-MOEA算法的編碼方案能夠有效提取每個節點的屬性與結構信息,并通過后處理修正的策略,提高社區發現的精度.其中,DeepWalk、Node2Vec、RMOEA與VGraph算法只考慮了結構信息,因此在各個數據集上的效果不佳.而SCI與RWECD算法雖然考慮了屬性信息,但是沒有考慮到網絡中可能存在著屬性信息與結構信息不匹配的問題,因此雖然精度有所提升,但是也沒有達到較高的精度.

圖7 真實網絡數據集NMI實驗

圖8 真實網絡數據集F1實驗

2.4 人工網絡數據集實驗結果

圖9顯示了FEV-MOEA算法與其它6種對比算法在D1網絡組上關于社區混合參數μ的精度實驗.從圖9可以看出,所有算法的NMI值都隨著社區混合參數μ的增加而減少,這是因為社區混合參數μ值越大,說明社區結構越模糊,算法越難檢測到正確的社區劃分.FEV-MOEA算法的精度雖然隨著μ值的增加而降低,但是相較于其它比較算法,其精度下降的較為平緩,這是因為即使在面對社區結構模糊的網絡時,FEV-MOEA算法通過綜合考慮網絡中的屬性信息來彌補結構信息的不足,進而提高社區劃分的精度.

圖9 不同混合參數μ的實驗結果

圖10、圖11顯示了FEV-MOEA算法與其它6種對比算法在D2網絡組上的精度實驗,其中圖10為NMI精度實驗,圖11為F1精度實驗.實驗結果表明,在各個規模的數據集下,FEV-MOEA算法都保持著最高的精度.網絡規模越大意味著網絡的結構會更加復雜,而FEV-MOEA算法通過融合節點的屬性信息與后處理修正策略,能夠在不同規模的網絡下保持良好的魯棒性與準確性.

圖10 人工網絡數據集NMI實驗

因此,FEV-MOEA算法隨著網絡規模的增加,其精度一直保持在較高的水平并且沒有較大的波動.而其余6種對比算法隨著網絡規模的增加,精度波動的幅度較大,說明其魯棒性較差,無法在不同規模網絡下進行有效的社區發現.

3 結論

本文提出了一種基于融合嵌入向量的多目標優化社區發現算法FEV-MOEA.與傳統編解碼方案不同,該算法的編解碼方案能夠利用到每個節點的屬性與結構嵌入向量,使得算法能夠不受到網絡結構的限制繼而發現高質量的社區.同時,設計一個后處理社區修正的策略,使得算法的解能夠克服陷入局部最優的問題,提高社區發現的精度.通過在真實網絡和人工網絡數據集上實驗,驗證了FEV-MOEA算法能夠在復雜屬性網絡上進行高精度的社區發現.未來,在現有工作基礎上,針對異構網絡社區發現展開探索,將異構網絡中不同類型的信息與進化計算相結合以檢測高質量的社區.