一種融合評價指標相關性的多目標社區檢測算法

易鑫睿，陳 昊1，，蘭金明

1(南昌航空大學 無損檢測技術教育部重點實驗室，南昌 330063)2(南昌航空大學 信息工程學院，南昌 330063)

E-mail：18397509886@163.com

1 引 言

復雜網絡將實體對象的交互關系抽象為一組頂點的連邊關系，檢測復雜網絡的社區結構對網絡犯罪、癌癥監測、產品營銷等現實問題具有重要意義[1，2].設計合適的社區質量評價指標是社區檢測的核心問題之一.用于評價社區質量的指標，根據描述社區結構質量的角度，可以分為：基于網絡拓撲特性的評價指標、基于模塊度擴展的評價指標、基于節點情景特征的評價指標三類，如表1所示.

基于網絡拓撲特性的評價指標，從網絡內、外部連邊結構對網絡質量進行度量，簡單易計算，包括：內部密度、平均內度、切割比、標準切割比、平均外度分數等[3]；Newman等人設計的模塊度指標通過網絡結構強度來評價社區質量[4]，至今仍是應用最廣泛的指標，可以推廣到無向加權網絡，有向無權網絡和有向加權的網絡[5]，之后為改進模塊度存在的分辨率限制問題，擴展了包括：局部模塊度函數[6]、懲罰模塊密度函數[7]、Z模塊度函數[8]等評價指標.第三類指標結合節點在網絡圖中的情景特征對社區結構進行評價，包括：單獨針對網絡中的頂點，量化一個頂點在分配它的社區中停留的概率，以及它被臨近社區拉扯的程度的持久性指標[9]、從社區層面，考慮社區規模中每個節點和其相連的二級節點對社區貢獻度的結構劃分適應度[10]以及信息傳播到社區內全部節點的速度為標準的緊湊度指標[11]等.

表1 社區質量評價指標Table 1 Indicators for assessing community quality

傳統單目標優化的社區檢測算法，檢測結果受限于單一的社區結構屬性.多目標社區檢測算法同時選擇多個評價指標，與單目標相比可以更為全面的評價社區質量，通過目標之間的權衡可以獲得一組更為準確的社區檢測結果.現有多目標社區檢測算法有很多，其中有包括基于進化算法的MOGA-Net[12]、MOEA/D-Net[13]、NNIA-Net[14]等；基于粒子群算法的MOCD-PSO[15]、MOPSO-Net[16]等.盡管已有多種指標可供選擇，但現有算法中的評價函數多依賴主觀判斷，嚴重制約社區檢測的準確性與穩定性.針對這一問題，本文對社區質量評價指標間的相關性進行定義與度量，在分析目標間相關關系的基礎上，構建一種新的融合評價指標相關性分析的多目標社區檢測算法.

2 多目標社區檢測Pareto最優解集

多目標社區檢測通過優化多個度量社區結構質量的指標，以獲得復雜網絡中更合理的社區檢測結果，其定義如下[17]：

F(Ω)=min(f1(Ω),f2(Ω),…,fr(Ω))

(1)

式中，f(·)表示第i個目標函數，Ω為已知網絡G(V,E)的一種可行社區檢測結果，當且僅當Ω在所有目標函數上獲得最優值時，Ω被稱為已知網絡的絕對最優解.而在實際情況中，一般無法獲得絕對最優解，通常會根據Pareto支配關系獲得一組Pareto最優解.

在網絡G(V,E)中，存在兩種可行社區檢測結果ΩA，ΩB，當滿足式(2)時，稱ΩA支配ΩB，記為ΩAΩB.

?i:fi(ΩA)≤fi(ΩB)∧?j:fj(ΩA)

(2)

3 評價指標間的相關性分析

相關關系一般用于描述兩個事物間存在相互作用、相互影響的關系[18].在社區檢測研究中，對評價指標間存在相關關系給出如下定義.

定義1.在已知網絡G(V,E)情況下，評價指標X，Y對N種不同社區結構度量結果的隨機樣本為(x1,y1),…,(xN,yN)，如果隨機變量y的取值受x的取值變化而在一定范圍變化，則稱Y和X之間存在相關關系.

(3)

從表1中篩選部分指標，選擇3個真實網絡數據集驗證基于Spearman系數的評價指標相關性度量方法的有效性.數據集上的隨機樣本數目為2000，度量結果如圖1所示.

圖1 評價指標之間相關性度量結果Fig.1 Correlation measurement results between evaluation indicators

觀察熱力圖上的分布，在單個網絡結構上，不同評價指標之間的相關性各不相同；在不同網絡結構上，同一評價指標間的相關性存在差異.在圖1(a)中，橫軸上前4個評價指標與豎直方向上9個評價指標的相關性出現了較明顯的分區，在分區中，Expansion等4個指標與Ncut和GS兩個的相關性程度相對較低且屬于正向相關影響，與CF、Q和CS則屬于反向相關影響.在縱軸上，Idensity和CutRatio指標在水平方向上灰度出現漸變，其中，與橫軸前6個指標屬于正向相關影響，相關性逐漸減弱，與后3個指標是逐漸增強的反向相關影響.不管指標之間相關性是正向影響還是反向影響，目標函數間相關性越小，指標才能滿足不同的特定目標.

比較圖1(a)與圖1(b)、圖1(c)之間的差距.在圖1(b)中，橫軸上前3個度量指標在豎直方向上的分區出現了不同情況，整體呈現相關性減弱.在局部Idensity/CutRatio/Ncut與Expansion/Conductance/AODF/Ncut的相關性為1，說明指標之間在Football網絡上具有等效度量能力.CF/Q兩項與彼此之外的其他指標關聯耦合程度相比圖1(a)有所下降，平均相關性在0.18.而在圖1(c)中，對比差異更加明顯，相同區域評價指標之間的相關程度出現較大變化.通過以上對比實驗分析說明不同的評價指標之間存在不同程度相關性，在具體多目標社區檢測優化算法中，合理的選擇目標函數才能保證算法獲得最優解.

4 結合評價指標相關性分析的多目標社區檢測算法

對以上利用Spearman相關系數度量評價指標間的相關性方法驗證分析后，提出一種利用評價指標相關性模型引導求解社區檢測問題的多目標社區檢測算法，該算法首先利用備選評價指標間Spearman相關關系構建相似矩陣，其次，采用譜聚類算法處理相似矩陣，獲得備選評價指標分類簇集，依據優選準則建模多目標社區檢測問題，最后，將多目標社區檢測問題與檢測算法結合獲得社區檢測Pareto解集，通過不同準則決策獲得最終社區檢測結果.

4.1 評價指標組合聚類

多目標社區檢測算法的各子目標從不同方面評價社區質量，相關性高的子目標之間實際具有等效的評價標準，按照相關性對備選評價指標分類后，更有利于選擇多個不同評價標準的指標.利用譜聚類算法對備選評價指標進行分類，通過構建評價指標間的相似矩陣Wm×m，對相似矩陣進行處理，達到滿足類內相似度最大，類間相似度最小劃分的目的.傳統相似度的計算公式以任意兩樣本點間的距離度量，但本文提出采用Spearman相關系數作為衡量評價指標相似度標準.

具體而言，采用第3節所提出的相關性度量方法獲得備選評價指標間相關關系，將所有結果組成相關矩陣Pm×m，m是備選評價指標數目.矩陣Pm×m為對稱矩陣，矩陣元素ρij的符號表示子目標i與子目標j的相關方向，數值表示子目標i與子目標j的相關性.

(4)

4.2 評價指標優選準則與方法描述

按照評價指標組合聚類的簇類數目，提出以下兩條優選準則選擇評價指標，構建社區檢測的多目標問題.

準則1.在任一簇內，如果當前備選評價指標與簇內其他備選評價指標之間的相關性均值fI最大，則當前備選評價指標作為目標之一被選擇.

準則2.在任一簇內，如果最大相關性均值存在多個備選評價指標，則備選評價指標與簇外其他備選評價指標之間的相關性均值fII最小者被選擇作為目標之一.關于相關性均值計算公式如(5)所示.

(5)

根據前面組合聚類與優選準則從備選評價指標集構建多目標社區檢測問題的方法流程偽代碼如下所示：

方法.多目標社區檢測問題構建方法MOCDP

輸入：網絡G(V,E)，備選評價指標集合f={fi,i=1,…,m}，優選評價指標數目r

輸出：優選評價指標集合f′={fi,i∈1,…,m;|f′|=r}

1.初始化可行社區檢測結果數據集Set={Ω1,Ω2,…,ΩN}；

2.fort=1:mdo

3.計算產生備選評價指標ft的隨機樣本點Ft={ft(Ω1),ft(Ω2),…,ft(ΩN)}；

4.F=F∪Ft；//F是由樣本點組成的隨機變量空間

5.endfor

6.fort1,t2=1:mdo

8.endfor

9.計算度矩陣D；

10.計算拉普拉斯矩陣Lm×m=D-P′；

11.計算Lm×m的k個特征向量組成Vm×k={v1,…,vk}；

12.(c1,…,cr)=Kmeans(Vm×k,r)； //相關性聚類

13.forj=1:rdo

14.ifmax(fI(i),i∈cj)==1then

15.f=f∪fi; //按照準則1選擇fi作為目標函數

16.else

17.fi=min(fII(i),i∈cj);

18.f=f∪fi; //按照準則2選擇fi作為目標函數

19.endif

20.endfor

21.returnf′={fi,i∈1,…,m;|f′|=r}

4.3 結合優選評價指標的多目標社區檢測算法

優選獲得評價指標指導多目標社區檢測算法處理具體復雜網絡，能使Pareto解集包含更多社區質量特征，滿足不同決策需求，依據決策準則獲得最后結果.結合優選評價指標的多目標社區檢測算法具體實現步驟如下：

Step 1.建立復雜網絡G(V,E)，設置種群規模popsize，最大迭代代數Maxiter；

Step 2.構建備選評價指標集合f={fi,i=1,…,m}，產生可行社區檢測結果集合Set；

Step 3.按照多目標社區檢測問題構建方法MOCDP，構建f′={fi,i∈1,…,m;|f′|=r}；

Step 4.初始化種群Pop，開始循環優化iter=1；

Step 5.計算種群個體適應度值p=(fi(Ωp),fi∈f′)；

Step 6.比較種群支配關系，獲得Pareto占優種群；

Step 7.根據多目標社區檢測算法操作算子對種群Pop進行更新；

Step 8.重新計算種群適應度值，更新Pareto占優種群；

Step 9.若滿足最大迭代條件iter>Maxiter，結束輸出Pareto占優種群，否則，返回執行Step 7；

Step 10.依據決策準則從Pareto占優種群選擇最終結果.

(6)

5 實驗與分析

5.1 實驗結果度量標準

通過對融合評價指標優選的多目標社區檢測算法結果質量進行度量，可以反映評價指標優選對算法的影響.本文在度量多目標社區檢測算法結果質量時，選擇模塊度函數Q和歸一化互信息函數NMI.

模塊度函數Q在優化算法中不僅可以作為目標指導種群進化，而且也常應用于度量結果質量，在4.3節已經具體說明.歸一化互信息函數NMI[20]是在已知網絡真實社區結構的前提下，用于度量網絡社區檢測結果和真實社區結構之間的相似性，相似性越高說明算法準確性越高.NMI的定義如下：

(7)

A和B分別為算法在網絡G(V,E)上的檢測結果和實際真實社區結果，CA(CB)是網絡社區劃分數目，C為混淆矩陣，C中元素Cij為中第i個社區與B中第j個社區的共同節點數目，Ci·(C·j)則表示混淆矩陣C中第i行(第j列)元素總和，N是網絡的節點數目.如果A=B，則NMI(A,B)=1；如果A和B完全不同，則NMI(A,B)=0.

5.2 實驗數據及結果

實驗所選用的網絡數據集包括Zachary′s Karate Club網絡、American College Football網絡、Books about US Politics網絡3個真實網絡數據集，各網絡數據匯總如表2所示.

表2 網絡數據集數據匯總表Table 2 Network dataset data

5.2.1 MOCDP方法構建多目標社區檢測問題結果

共收集19種備選評價指標用于優選構建多目標社區檢測問題，如表3所示.依據指標間相關性的聚類操作，每個數據集上獲得的結果如表4所示.

表3 備選子目標集合匯總表Table 3 Alternative sub target set

表4 構建多目標社區檢測問題結果匯總表Table 4 Build multi-target community detection problem results

5.2.2 不同目標組合對多目標社區檢測算法性能影響

本文為分析MOCDP方法構建的多目標社區檢測問題對于社區檢測算法的性能影響，在MOPSO-Net[16]算法框架基礎上，將文獻[12]與文獻[16]中選擇的目標函數組合與采用MOCDP方法產生的目標函數組合進行了對比實驗.參數設置按照MOPSO-Net中說明，在三個真實網絡數據集上運行20次的實驗結果如表5所示.

觀察三個數據集上整體實驗結果發現，基于本文MOCDP方法的MOPSO-Net算法能夠取得有效的實驗結果，說明MOCDP方法用于構建社區檢測算法的多目標問題可行.而與此同時，可以發現不同目標組合方法指導MOPSO-Net尋優的效果在不同數據集上存在較大差異，如文獻[12]中選擇CS/CF指導MOPSO-Net尋優時更明顯，表現在Football網絡上結果更好，在Club網絡上結果更差，說明在多目標社區檢測處理問題時，合理選擇目標函數組合十分必要.

分析MOCDP方法對MOPSO-Net尋優的影響，在處理同樣網絡數據集時，本文優選的目標指導MOPSO-Net算法尋優效果更好，特別在Football網絡結構中，本文優選的目標函數組合是MMC/CF，獲得的社區檢測結果在NMI值與Q值兩項指標的多次實驗的最大均值與最大值都超過了另外兩種目標組合結果.在Politics網絡數據集上，三種組合的目標函數獲得的Q值的最大均值與最大值相近，但本文MOCDP方法的優選目標組合Compactness/CS獲得的檢測結果NMI值更優.

表5 不同多目標組合在MOPSO-Net處理不同數據集上的實驗結果Table 5 Experimental results of different multi-target combinations on different data sets processed by MOPSO-Net

對于應用同一目標函數組合處理不同網絡數據集時，多目標社區檢測算法尋優結果之間存在效果差別.如Club網絡中，三種目標函數組合方式指導MOPSO-Net算法尋優時，普遍效果較差，而在Football網絡中則普遍更好，分析原因是網絡數據集的復雜度影響，網絡中反映社區特征少而影響到目標函數對種群解個體的評價，致使尋優效果不好.但綜合整體實驗結果，本文MOCDP方法構建的多目標社區檢測問題在相同算法中檢測效果更好，能夠發現與網絡真實社區結構更相近的社區檢測結果.

5.2.3 結合MOCDP方法的不同多目標社區檢測算法性能分析

為驗證本文MOCDP方法在不同算法上的結果影響，以下選擇MOGA-Net算法、NNIA-Net算法、MOPSO-Net算法設置實驗.其中，需要說明的是MOGA-Net算法中，交叉操作與變異操作的概率分別設置為0.8和0.2，采用輪盤賭選擇的精英個體設置為種群規模10%.每個算法在同一網絡上的種群規模設置為1000，進化代數1000代，實驗算法的其他參數依據相應原文獻設置，重復運行20次，獲得算法結果統計如圖2、圖3、圖4所示.

圖2 在Zachary′s Karate Club網絡上比較更改目標函數前后不同算法性能Fig.2 Compare the performance of different algorithms beforeand after changing the target function on Zachary′sKarate Club network

由圖上顯示，在相同網絡上，運用MOCDP方法優選目標函數后，不同多目標社區檢測算法獲得結果之間存在不同差距.圖2中，MOGA-Net算法和NNIA-Net算法相比MOPSO-Net算法更為明顯，原有平均最大NMI值分別為0.46和0.459，平均最大模塊度值分別為0.341和0.325，優選目標函數后，MOGA-Net-I、NNIA-Net-I算法在性能上出現提升，特別是，NNIA-Net-I算法在多次運行結果中，每次結果的最大NMI值與最大模塊度值Q保持穩定，獲得統一的網絡社區劃分結果.MOPSO-Net-I算法雖然平均最大NMI值和平均最大模塊度值Q在結果上不及原算法，但實驗結果中最大NMI值和最大Q值分別優于原算法.

圖3 在American College Football網絡上比較更改目標函數前后不同算法性能Fig.3 Compare the performance of different algorithms beforeand after changing the objective function on the AmericanCollege Football network

比較圖3中結果，雖然MOGA-Net-I獲得的最大NMI值和最大Q值略低MOGA-Net，但兩項指標在均值上更優，說明MOGA-Net-I算法結果更為穩定，解集合整體質量更優秀.此外NNIA-Net-I結果中NMI值指標與Q值指標基本和原算法一致.而圖4中結果顯示所有算法對Politics網絡數據集進行社區檢測時，最大NMI值均在0.4以上，而NNIA-Net-I的最大NMI值達到0.712，與NNIA-Net的0.524相比提高35.87%.雖然MOGA-Net-I與MOPSO-Net-I相比原算法獲得的結果模塊度值Q有所下降，但平均最大值NMI值均有提高.

當相同算法處理不同網絡數據時，通過MOCDP方法優選目標對同一多目標社區檢測算法性能的影響程度存在差異.實驗結果表明在三個真實網絡數據集上采用MOCDP方法優選目標函數能夠提升多目標社區檢測算法性能，其中，MOCDP方法優選目標函數效果在MOGA-Net、NNIA-Net算法上更好.說明采用MOCDP方法優選目標函數有助于提升多目標社區檢測算法準確性性能，并且在不改進算法框架的前提下，合理優選目標函數使得社區檢測算法結果穩定性提高，網絡社區劃分結果更滿足決策需求.

圖4 在Books about US Politics網絡上比較更改目標函數前后不同算法性能Fig.4 Comparing the performance of different algorithmsbefore and after changing the objective function on theBooks about US Politics network

6 結 論

針對復雜網絡中社區檢測算法的研究，提出一種基于評價指標相關性分析的多目標社區檢測算法.首先介紹了已有度量社區質量指標的三種分類，定義評價指標的相關關系，通過基于Spearman相關系數的目標相關性度量方法，對目標函數之間關系進行驗證分析，隨后，在介紹基于評價指標相關性分析的多目標社區檢測算法時，詳細描述了評價指標組合聚類操作步驟，提出了評價指標優選準則與MOCDP方法偽代碼內容.將MOCDP方法在三個真實網絡數據集上進行實驗，構建了不同的多目標社區檢測問題.選擇了MOPSO-Net算法框架，對比已有的兩種目標函數組合與MOCDP方法對相同算法的結果影響，實驗表明，同一算法框架下，MOCDP方法選擇的目標函數組合更有利于算法尋找最優解.與此同時，MOGA-Net，NNIA-Net，MOPSO-Net三種不同算法在結合MOCDP方法之后，算法有效性出現不同程度的提升.本文考慮已有算法框架的尋優性能不足問題，下一步將結合以上研究內容設計一種更具應用價值的新的多目標社區檢測算法.