一種融合評價指標(biāo)相關(guān)性的多目標(biāo)社區(qū)檢測算法

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

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

E-mail：18397509886@163.com

1 引 言

復(fù)雜網(wǎng)絡(luò)將實體對象的交互關(guān)系抽象為一組頂點的連邊關(guān)系，檢測復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)對網(wǎng)絡(luò)犯罪、癌癥監(jiān)測、產(chǎn)品營銷等現(xiàn)實問題具有重要意義[1，2].設(shè)計合適的社區(qū)質(zhì)量評價指標(biāo)是社區(qū)檢測的核心問題之一.用于評價社區(qū)質(zhì)量的指標(biāo)，根據(jù)描述社區(qū)結(jié)構(gòu)質(zhì)量的角度，可以分為：基于網(wǎng)絡(luò)拓撲特性的評價指標(biāo)、基于模塊度擴展的評價指標(biāo)、基于節(jié)點情景特征的評價指標(biāo)三類，如表1所示.

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

表1 社區(qū)質(zhì)量評價指標(biāo)Table 1 Indicators for assessing community quality

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

2 多目標(biāo)社區(qū)檢測Pareto最優(yōu)解集

多目標(biāo)社區(qū)檢測通過優(yōu)化多個度量社區(qū)結(jié)構(gòu)質(zhì)量的指標(biāo)，以獲得復(fù)雜網(wǎng)絡(luò)中更合理的社區(qū)檢測結(jié)果，其定義如下[17]：

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

(1)

式中，f(·)表示第i個目標(biāo)函數(shù)，Ω為已知網(wǎng)絡(luò)G(V,E)的一種可行社區(qū)檢測結(jié)果，當(dāng)且僅當(dāng)Ω在所有目標(biāo)函數(shù)上獲得最優(yōu)值時，Ω被稱為已知網(wǎng)絡(luò)的絕對最優(yōu)解.而在實際情況中，一般無法獲得絕對最優(yōu)解，通常會根據(jù)Pareto支配關(guān)系獲得一組Pareto最優(yōu)解.

在網(wǎng)絡(luò)G(V,E)中，存在兩種可行社區(qū)檢測結(jié)果ΩA，ΩB，當(dāng)滿足式(2)時，稱ΩA支配ΩB，記為ΩAΩB.

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

(2)

3 評價指標(biāo)間的相關(guān)性分析

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

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

(3)

從表1中篩選部分指標(biāo)，選擇3個真實網(wǎng)絡(luò)數(shù)據(jù)集驗證基于Spearman系數(shù)的評價指標(biāo)相關(guān)性度量方法的有效性.數(shù)據(jù)集上的隨機樣本數(shù)目為2000，度量結(jié)果如圖1所示.

圖1 評價指標(biāo)之間相關(guān)性度量結(jié)果Fig.1 Correlation measurement results between evaluation indicators

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

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

4 結(jié)合評價指標(biāo)相關(guān)性分析的多目標(biāo)社區(qū)檢測算法

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

4.1 評價指標(biāo)組合聚類

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

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

(4)

4.2 評價指標(biāo)優(yōu)選準則與方法描述

按照評價指標(biāo)組合聚類的簇類數(shù)目，提出以下兩條優(yōu)選準則選擇評價指標(biāo)，構(gòu)建社區(qū)檢測的多目標(biāo)問題.

準則1.在任一簇內(nèi)，如果當(dāng)前備選評價指標(biāo)與簇內(nèi)其他備選評價指標(biāo)之間的相關(guān)性均值fI最大，則當(dāng)前備選評價指標(biāo)作為目標(biāo)之一被選擇.

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

(5)

根據(jù)前面組合聚類與優(yōu)選準則從備選評價指標(biāo)集構(gòu)建多目標(biāo)社區(qū)檢測問題的方法流程偽代碼如下所示：

方法.多目標(biāo)社區(qū)檢測問題構(gòu)建方法MOCDP

輸入：網(wǎng)絡(luò)G(V,E)，備選評價指標(biāo)集合f={fi,i=1,…,m}，優(yōu)選評價指標(biāo)數(shù)目r

輸出：優(yōu)選評價指標(biāo)集合f′={fi,i∈1,…,m;|f′|=r}

1.初始化可行社區(qū)檢測結(jié)果數(shù)據(jù)集Set={Ω1,Ω2,…,ΩN}；

2.fort=1:mdo

3.計算產(chǎn)生備選評價指標(biāo)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)； //相關(guān)性聚類

13.forj=1:rdo

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

15.f=f∪fi; //按照準則1選擇fi作為目標(biāo)函數(shù)

16.else

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

18.f=f∪fi; //按照準則2選擇fi作為目標(biāo)函數(shù)

19.endif

20.endfor

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

4.3 結(jié)合優(yōu)選評價指標(biāo)的多目標(biāo)社區(qū)檢測算法

優(yōu)選獲得評價指標(biāo)指導(dǎo)多目標(biāo)社區(qū)檢測算法處理具體復(fù)雜網(wǎng)絡(luò)，能使Pareto解集包含更多社區(qū)質(zhì)量特征，滿足不同決策需求，依據(jù)決策準則獲得最后結(jié)果.結(jié)合優(yōu)選評價指標(biāo)的多目標(biāo)社區(qū)檢測算法具體實現(xiàn)步驟如下：

Step 1.建立復(fù)雜網(wǎng)絡(luò)G(V,E)，設(shè)置種群規(guī)模popsize，最大迭代代數(shù)Maxiter；

Step 2.構(gòu)建備選評價指標(biāo)集合f={fi,i=1,…,m}，產(chǎn)生可行社區(qū)檢測結(jié)果集合Set；

Step 3.按照多目標(biāo)社區(qū)檢測問題構(gòu)建方法MOCDP，構(gòu)建f′={fi,i∈1,…,m;|f′|=r}；

Step 4.初始化種群Pop，開始循環(huán)優(yōu)化iter=1；

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

Step 6.比較種群支配關(guān)系，獲得Pareto占優(yōu)種群；

Step 7.根據(jù)多目標(biāo)社區(qū)檢測算法操作算子對種群Pop進行更新；

Step 8.重新計算種群適應(yīng)度值，更新Pareto占優(yōu)種群；

Step 9.若滿足最大迭代條件iter>Maxiter，結(jié)束輸出Pareto占優(yōu)種群，否則，返回執(zhí)行Step 7；

Step 10.依據(jù)決策準則從Pareto占優(yōu)種群選擇最終結(jié)果.

(6)

5 實驗與分析

5.1 實驗結(jié)果度量標(biāo)準

通過對融合評價指標(biāo)優(yōu)選的多目標(biāo)社區(qū)檢測算法結(jié)果質(zhì)量進行度量，可以反映評價指標(biāo)優(yōu)選對算法的影響.本文在度量多目標(biāo)社區(qū)檢測算法結(jié)果質(zhì)量時，選擇模塊度函數(shù)Q和歸一化互信息函數(shù)NMI.

模塊度函數(shù)Q在優(yōu)化算法中不僅可以作為目標(biāo)指導(dǎo)種群進化，而且也常應(yīng)用于度量結(jié)果質(zhì)量，在4.3節(jié)已經(jīng)具體說明.歸一化互信息函數(shù)NMI[20]是在已知網(wǎng)絡(luò)真實社區(qū)結(jié)構(gòu)的前提下，用于度量網(wǎng)絡(luò)社區(qū)檢測結(jié)果和真實社區(qū)結(jié)構(gòu)之間的相似性，相似性越高說明算法準確性越高.NMI的定義如下：

(7)

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

5.2 實驗數(shù)據(jù)及結(jié)果

實驗所選用的網(wǎng)絡(luò)數(shù)據(jù)集包括Zachary′s Karate Club網(wǎng)絡(luò)、American College Football網(wǎng)絡(luò)、Books about US Politics網(wǎng)絡(luò)3個真實網(wǎng)絡(luò)數(shù)據(jù)集，各網(wǎng)絡(luò)數(shù)據(jù)匯總?cè)绫?所示.

表2 網(wǎng)絡(luò)數(shù)據(jù)集數(shù)據(jù)匯總表Table 2 Network dataset data

5.2.1 MOCDP方法構(gòu)建多目標(biāo)社區(qū)檢測問題結(jié)果

共收集19種備選評價指標(biāo)用于優(yōu)選構(gòu)建多目標(biāo)社區(qū)檢測問題，如表3所示.依據(jù)指標(biāo)間相關(guān)性的聚類操作，每個數(shù)據(jù)集上獲得的結(jié)果如表4所示.

表3 備選子目標(biāo)集合匯總表Table 3 Alternative sub target set

表4 構(gòu)建多目標(biāo)社區(qū)檢測問題結(jié)果匯總表Table 4 Build multi-target community detection problem results

5.2.2 不同目標(biāo)組合對多目標(biāo)社區(qū)檢測算法性能影響

本文為分析MOCDP方法構(gòu)建的多目標(biāo)社區(qū)檢測問題對于社區(qū)檢測算法的性能影響，在MOPSO-Net[16]算法框架基礎(chǔ)上，將文獻[12]與文獻[16]中選擇的目標(biāo)函數(shù)組合與采用MOCDP方法產(chǎn)生的目標(biāo)函數(shù)組合進行了對比實驗.參數(shù)設(shè)置按照MOPSO-Net中說明，在三個真實網(wǎng)絡(luò)數(shù)據(jù)集上運行20次的實驗結(jié)果如表5所示.

觀察三個數(shù)據(jù)集上整體實驗結(jié)果發(fā)現(xiàn)，基于本文MOCDP方法的MOPSO-Net算法能夠取得有效的實驗結(jié)果，說明MOCDP方法用于構(gòu)建社區(qū)檢測算法的多目標(biāo)問題可行.而與此同時，可以發(fā)現(xiàn)不同目標(biāo)組合方法指導(dǎo)MOPSO-Net尋優(yōu)的效果在不同數(shù)據(jù)集上存在較大差異，如文獻[12]中選擇CS/CF指導(dǎo)MOPSO-Net尋優(yōu)時更明顯，表現(xiàn)在Football網(wǎng)絡(luò)上結(jié)果更好，在Club網(wǎng)絡(luò)上結(jié)果更差，說明在多目標(biāo)社區(qū)檢測處理問題時，合理選擇目標(biāo)函數(shù)組合十分必要.

分析MOCDP方法對MOPSO-Net尋優(yōu)的影響，在處理同樣網(wǎng)絡(luò)數(shù)據(jù)集時，本文優(yōu)選的目標(biāo)指導(dǎo)MOPSO-Net算法尋優(yōu)效果更好，特別在Football網(wǎng)絡(luò)結(jié)構(gòu)中，本文優(yōu)選的目標(biāo)函數(shù)組合是MMC/CF，獲得的社區(qū)檢測結(jié)果在NMI值與Q值兩項指標(biāo)的多次實驗的最大均值與最大值都超過了另外兩種目標(biāo)組合結(jié)果.在Politics網(wǎng)絡(luò)數(shù)據(jù)集上，三種組合的目標(biāo)函數(shù)獲得的Q值的最大均值與最大值相近，但本文MOCDP方法的優(yōu)選目標(biāo)組合Compactness/CS獲得的檢測結(jié)果NMI值更優(yōu).

表5 不同多目標(biāo)組合在MOPSO-Net處理不同數(shù)據(jù)集上的實驗結(jié)果Table 5 Experimental results of different multi-target combinations on different data sets processed by MOPSO-Net

對于應(yīng)用同一目標(biāo)函數(shù)組合處理不同網(wǎng)絡(luò)數(shù)據(jù)集時，多目標(biāo)社區(qū)檢測算法尋優(yōu)結(jié)果之間存在效果差別.如Club網(wǎng)絡(luò)中，三種目標(biāo)函數(shù)組合方式指導(dǎo)MOPSO-Net算法尋優(yōu)時，普遍效果較差，而在Football網(wǎng)絡(luò)中則普遍更好，分析原因是網(wǎng)絡(luò)數(shù)據(jù)集的復(fù)雜度影響，網(wǎng)絡(luò)中反映社區(qū)特征少而影響到目標(biāo)函數(shù)對種群解個體的評價，致使尋優(yōu)效果不好.但綜合整體實驗結(jié)果，本文MOCDP方法構(gòu)建的多目標(biāo)社區(qū)檢測問題在相同算法中檢測效果更好，能夠發(fā)現(xiàn)與網(wǎng)絡(luò)真實社區(qū)結(jié)構(gòu)更相近的社區(qū)檢測結(jié)果.

5.2.3 結(jié)合MOCDP方法的不同多目標(biāo)社區(qū)檢測算法性能分析

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

圖2 在Zachary′s Karate Club網(wǎng)絡(luò)上比較更改目標(biāo)函數(shù)前后不同算法性能Fig.2 Compare the performance of different algorithms beforeand after changing the target function on Zachary′sKarate Club network

由圖上顯示，在相同網(wǎng)絡(luò)上，運用MOCDP方法優(yōu)選目標(biāo)函數(shù)后，不同多目標(biāo)社區(qū)檢測算法獲得結(jié)果之間存在不同差距.圖2中，MOGA-Net算法和NNIA-Net算法相比MOPSO-Net算法更為明顯，原有平均最大NMI值分別為0.46和0.459，平均最大模塊度值分別為0.341和0.325，優(yōu)選目標(biāo)函數(shù)后，MOGA-Net-I、NNIA-Net-I算法在性能上出現(xiàn)提升，特別是，NNIA-Net-I算法在多次運行結(jié)果中，每次結(jié)果的最大NMI值與最大模塊度值Q保持穩(wěn)定，獲得統(tǒng)一的網(wǎng)絡(luò)社區(qū)劃分結(jié)果.MOPSO-Net-I算法雖然平均最大NMI值和平均最大模塊度值Q在結(jié)果上不及原算法，但實驗結(jié)果中最大NMI值和最大Q值分別優(yōu)于原算法.

圖3 在American College Football網(wǎng)絡(luò)上比較更改目標(biāo)函數(shù)前后不同算法性能Fig.3 Compare the performance of different algorithms beforeand after changing the objective function on the AmericanCollege Football network

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

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

圖4 在Books about US Politics網(wǎng)絡(luò)上比較更改目標(biāo)函數(shù)前后不同算法性能Fig.4 Comparing the performance of different algorithmsbefore and after changing the objective function on theBooks about US Politics network

6 結(jié) 論

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