位置修復(fù)和粒子置換的FSUD-PSO簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)*

肖 敏，郭 美+，胡山泉

1.湘南學(xué)院 軟件與通信工程學(xué)院，湖南 郴州 423000

2.湘南學(xué)院 信息化建設(shè)與管理辦公室，湖南 郴州 423000

位置修復(fù)和粒子置換的FSUD-PSO簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)*

肖 敏1，郭 美1+，胡山泉2

1.湘南學(xué)院 軟件與通信工程學(xué)院，湖南 郴州 423000

2.湘南學(xué)院 信息化建設(shè)與管理辦公室，湖南 郴州 423000

XIAO Min,GUO Mei,HU Shanquan.Location repair and particle replacement based FSUD-PSO for signature network community discovery.Journal of Frontiers of Computer Science and Technology,2016,10(11)：1641-1650.

為提高簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)效果，解決其評估指標(biāo)存在的數(shù)據(jù)耦合和依賴性，造成網(wǎng)絡(luò)社區(qū)單指標(biāo)優(yōu)化存在較大局限性的問題，提出了基于位置修復(fù)和粒子置換的FSUD-PSO（fast sorting and uniform density of multi-objective particle swarm optimization）簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。首先，對簽名網(wǎng)絡(luò)模型進(jìn)行研究，并在考慮數(shù)據(jù)耦合和依賴性前提下給出簽名網(wǎng)絡(luò)社區(qū)評價(jià)指標(biāo)，以及多目標(biāo)Pareto最優(yōu)目標(biāo)模型；其次，構(gòu)建簽名網(wǎng)絡(luò)模型的多目標(biāo)優(yōu)化粒子編碼與更新規(guī)則，并根據(jù)簽名網(wǎng)絡(luò)特點(diǎn)設(shè)計(jì)了位置修復(fù)和粒子置換策略，同時(shí)為提高多目標(biāo)粒子群算法性能，設(shè)計(jì)了快速排序均勻密度的多目標(biāo)粒子群算法FSUD-PSO；最后，通過標(biāo)準(zhǔn)測試集實(shí)驗(yàn)對比，驗(yàn)證了所提FSUD-PSO簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的有效性。

位置修復(fù)；粒子置換；多目標(biāo)粒子群；快速排序；均勻密度

1 引言

網(wǎng)絡(luò)無處不在，前所未有地改變著人們的日常生活[1-2]。從理論分析和實(shí)際應(yīng)用角度研究這些復(fù)雜網(wǎng)絡(luò)具有重要意義。分析復(fù)雜網(wǎng)絡(luò)的直接方法是用圖形進(jìn)行網(wǎng)絡(luò)表示，圖由一組節(jié)點(diǎn)和邊組成[3]，節(jié)點(diǎn)代表網(wǎng)絡(luò)對象，邊緣表示對象之間的關(guān)系。通過分析圖的特性可以得到網(wǎng)絡(luò)的特性。網(wǎng)絡(luò)有很多特性，如小世界性、無標(biāo)度特性等，其中網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)是最受關(guān)注的特性。在圖形語言中，一個(gè)社區(qū)被稱為子圖，特點(diǎn)是社區(qū)內(nèi)節(jié)點(diǎn)之間的相似性要高于社區(qū)間節(jié)點(diǎn)的相似性[4]。

社區(qū)結(jié)構(gòu)對許多網(wǎng)絡(luò)非常重要，因此復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)已引起了學(xué)者們的極大興趣[5]。到目前為止，已經(jīng)提出了大量的方法來檢測網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。近年來，研究者們提出了一類用于優(yōu)化社區(qū)質(zhì)量評判指標(biāo)的超啟發(fā)式方法，主要有單目標(biāo)社區(qū)發(fā)現(xiàn)和多目標(biāo)社區(qū)發(fā)現(xiàn)。如文獻(xiàn)[6]基于遺傳算法（genetic algorithm，GA）獲得網(wǎng)絡(luò)社區(qū)模塊度Q的優(yōu)化，進(jìn)而得到網(wǎng)絡(luò)社區(qū)的最優(yōu)劃分；文獻(xiàn)[7]給定網(wǎng)絡(luò)社區(qū)的質(zhì)量評判標(biāo)準(zhǔn)，并采用GA-Net獲得網(wǎng)絡(luò)的檢測優(yōu)化；文獻(xiàn)[8]利用社區(qū)極小化設(shè)計(jì)ACGA算法實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)優(yōu)化，將社區(qū)進(jìn)行個(gè)體編碼，提升社區(qū)發(fā)現(xiàn)質(zhì)量；文獻(xiàn)[9]采用粒子群優(yōu)化（particle swarm optimization，PSO）算法實(shí)現(xiàn)網(wǎng)絡(luò)社區(qū)的二分迭代劃分，進(jìn)而實(shí)現(xiàn)Web的社區(qū)檢測；文獻(xiàn)[10]利用鄰居節(jié)點(diǎn)獲得PSO粒子的有序表，并利用粒子群的全局搜索能力進(jìn)行社區(qū)挖掘等。

盡管單目標(biāo)社區(qū)發(fā)現(xiàn)計(jì)算效果較好，并可獲得特定網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，但真實(shí)情況下，網(wǎng)絡(luò)社區(qū)過程需要滿足多個(gè)要求，且此類目標(biāo)會(huì)出現(xiàn)前后矛盾，采用單目標(biāo)社區(qū)發(fā)現(xiàn)與實(shí)際情形可能不符，對此采用多目標(biāo)進(jìn)化算法的社區(qū)發(fā)現(xiàn)受到學(xué)者的關(guān)注[11]。文獻(xiàn)[12]采用進(jìn)化算法與規(guī)劃計(jì)算方式獲得網(wǎng)絡(luò)社區(qū)內(nèi)外部鏈接的同步優(yōu)化，但算法計(jì)算復(fù)雜度過高。文獻(xiàn)[13]設(shè)計(jì)狀態(tài)離散的多目標(biāo)PSO算法（multi-objective discrete particle swarm optimization，MODPSO），實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)的社區(qū)聚類發(fā)現(xiàn)，但算法在保持搜索多樣性能力上還存在缺陷，不利于全局Pareto次優(yōu)解集的獲得。

本文以簽署網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)作為研究對象，在相應(yīng)位置修復(fù)和粒子轉(zhuǎn)換的基礎(chǔ)上提出了快速排序和均勻密度的多目標(biāo)粒子群算法（fast sorting and uniform density of multi-objective particle swarm optimization，F(xiàn)SUD-PSO）。文章主要框架如下：（1）提出問題，分析基于簽名網(wǎng)絡(luò)的模型與相關(guān)的評價(jià)指標(biāo)，給出多目標(biāo)優(yōu)化的目標(biāo)；（2）構(gòu)建簽名網(wǎng)絡(luò)模型的多目標(biāo)優(yōu)化粒子編碼與更新規(guī)則，并設(shè)計(jì)相應(yīng)的位置修復(fù)和粒子置換策略，設(shè)計(jì)快速排序和均勻密度的多目標(biāo)粒子群算法FSUD-PSO；（3）通過仿真實(shí)驗(yàn)進(jìn)行分析。

2 問題提出

網(wǎng)絡(luò)社區(qū)通常表示為節(jié)點(diǎn)和邊組成的有向連接圖。邊分正邊和負(fù)邊兩種類型。網(wǎng)絡(luò)社區(qū)檢測的任務(wù)是根據(jù)某些原則將符號網(wǎng)絡(luò)劃分為不同的集群。每個(gè)集群被稱為社區(qū)。

定義1（網(wǎng)絡(luò)社區(qū)）對于無向連接網(wǎng)絡(luò)可定義結(jié)構(gòu)G=(V,E)，其中V為網(wǎng)絡(luò)頂點(diǎn)（節(jié)點(diǎn)），E為網(wǎng)絡(luò)邊集，且有E={e=(u,v),u∈V,v∈V}，G可采用尺寸為和Vi?Vj=?(i≠j)。

定義2（簽名網(wǎng)絡(luò)模型）給定網(wǎng)絡(luò)模型G=(V, PL,NL)，其中V為網(wǎng)絡(luò)頂點(diǎn)（節(jié)點(diǎn)），PL和NL分別為正、負(fù)鏈接集合。令A(yù)為G的鄰接矩陣，lij為節(jié)點(diǎn)i和j間的鏈接。

根據(jù)定義1和定義2可知，簽名網(wǎng)絡(luò)模型與網(wǎng)絡(luò)社區(qū)定義的區(qū)別在于，前者邊分為正、負(fù)鏈接，并在模型中體現(xiàn)。圖1給出帶有9個(gè)節(jié)點(diǎn)和16條邊的簽名網(wǎng)絡(luò)示例。

Fig.1 Example of signature network圖1 簽名網(wǎng)絡(luò)示例

在弱簽名社區(qū)中，社區(qū)內(nèi)部節(jié)點(diǎn)的正鏈接和社區(qū)間節(jié)點(diǎn)的負(fù)鏈接都是密集存在的。根據(jù)圖1可知，簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的任務(wù)是把整個(gè)網(wǎng)絡(luò)分成許多社區(qū)，但劃分優(yōu)劣標(biāo)準(zhǔn)仍是難題。

2.2 簽名網(wǎng)絡(luò)社區(qū)指標(biāo)評價(jià)

為給出簽名社區(qū)結(jié)構(gòu)劃分定量標(biāo)準(zhǔn)，文獻(xiàn)[14]提出新的模塊量化標(biāo)準(zhǔn)，新指標(biāo)SQ稱為簽名模塊化：

式中，wij是簽名鄰接矩陣的權(quán)重；表示節(jié)點(diǎn)所有正（負(fù)）權(quán)重總和。如果節(jié)點(diǎn)i和 j在同一組，δ(i,j)=1；否則δ(i,j)=0。SQ取值越大，社區(qū)結(jié)構(gòu)分離程度越好。同時(shí)，另一個(gè)Silhouette指標(biāo)為：

Fig.2 Signature community discovery圖2 簽名社區(qū)發(fā)現(xiàn)

圖2給出迭代次數(shù)為90時(shí)，SQ=0.423，GS=0.698，以及迭代次數(shù)為110時(shí)，SQ=0.763，GS= 0.699，兩種情形下的簽名社區(qū)結(jié)構(gòu)。

根據(jù)圖2可知，隨著簽名社區(qū)發(fā)現(xiàn)過程的優(yōu)化，簽名模塊化指標(biāo)SQ取值也相應(yīng)增大，但GS指標(biāo)并未出現(xiàn)數(shù)值增加。

首先，給出耦合度定義，簽名網(wǎng)絡(luò)G在社區(qū)發(fā)現(xiàn)函數(shù)迭代tn→tm過程中(m>n)，如果社區(qū)發(fā)現(xiàn)評估向量元素Fi滿足條件，那么Fi和Fj間耦合度如下：

可以基于權(quán)重先驗(yàn)知識進(jìn)行評估標(biāo)準(zhǔn)合成，從而基于單目標(biāo)算法進(jìn)行優(yōu)化。但不同評估指標(biāo)間存在耦合性，導(dǎo)致合并效果不理想，無法獲得最優(yōu)解。

2.3 算法的優(yōu)化目標(biāo)

上述定義表明該模型優(yōu)化需采用多目標(biāo)進(jìn)化算法。這里首先給出多目標(biāo)Pareto最優(yōu)相關(guān)定義。

（1）Pareto支配：對于簽名網(wǎng)絡(luò)模型發(fā)現(xiàn)過程V→P，則G=(V,PL,NL)中兩種社區(qū)形式P1,P2∈P，滿足如下條件時(shí)，形式P1支配P2成立，即P1?P2。

（2）Pareto等價(jià)：如果滿足如下條件時(shí)，形式P1等價(jià)形式P2，即P1=P2。

（3）Pareto未知：如果滿足如下條件，形式P1與形式P2關(guān)系未知，即P1?P2。

（4）Pareto最優(yōu)：如果滿足如下條件，簽名網(wǎng)絡(luò)模型社區(qū)發(fā)現(xiàn)策略集P內(nèi)的某策略P*即為Pareto最優(yōu)策略。

（5）Pareto前沿：簽名網(wǎng)絡(luò)模型最優(yōu)策略對應(yīng)的評估向量集是Pareto社區(qū)前沿。

對于簽名網(wǎng)絡(luò)G=(V,PL,NL)，F(xiàn)是預(yù)定義目標(biāo)集，社區(qū)劃分?jǐn)?shù)量為k，該值可根據(jù)進(jìn)化算法進(jìn)行聚類或預(yù)定義給出，則社區(qū)發(fā)現(xiàn)流程即為查找F令為最優(yōu)劃分。根據(jù)前述定義，可定義簽名網(wǎng)絡(luò)多目標(biāo)社區(qū)發(fā)現(xiàn)模型為：

式中，X為某簽名網(wǎng)絡(luò)模型社區(qū)發(fā)現(xiàn)策略；gj(X)為社區(qū)發(fā)現(xiàn)約束，并可定義為：

3 簽名網(wǎng)絡(luò)模型的多目標(biāo)優(yōu)化

3.1 粒子編碼與更新規(guī)則

這里采用整數(shù)排列方式的粒子位置向量，并基于字符串進(jìn)行二進(jìn)制編碼。采用的模式如圖3所示。

Fig.3 Particle representation model圖3 基于字符串的粒子表示模式

每個(gè)粒子都代表優(yōu)化問題的一個(gè)解決方案。傳統(tǒng)的粒子更新規(guī)則為：

由圖3可知，式（12）、（13）所示粒子更新規(guī)則不適于簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題，對此定義新的粒子更新規(guī)則為：

式（14）中，“?”為異或操作，φ(t)可定義為：

式（15）中，“?”操作符可定義如下：

式中，Nj為節(jié)點(diǎn) j的鄰域粒子集；如果a=b，δ(a, b)=1，否則δ(a,b)=0。操作步驟見圖4所示。

Fig.4 Particle updating rules圖4 粒子更新規(guī)則

根據(jù)圖4，簽名網(wǎng)絡(luò)的拓?fù)湫畔⒘Ｗ訝顟B(tài)規(guī)則更新，可保證算法獲得可行的社區(qū)發(fā)現(xiàn)解決方案。

3.2 位置修復(fù)和粒子置換

根據(jù)編碼方式，兩個(gè)不同位置向量可能對應(yīng)于相同的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，具體如圖5所示。

在圖5中，Xi和Pi分別對應(yīng)當(dāng)前和歷史上最好的粒子位置。解碼后，Xi和Pi代表同一網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。根據(jù)式（14）、（15），可得非零向量Vi，Xi會(huì)隨時(shí)間改變。為節(jié)省時(shí)間，設(shè)計(jì)位置修復(fù)算法，見偽代碼1所示。

Fig.5 Community structure of position vector圖5 位置向量社區(qū)結(jié)構(gòu)

如圖5所示，經(jīng)過位置修復(fù)后，根據(jù)式（14）可得Xi和Pi的一致零向量。不需要計(jì)算新的位置矢量，節(jié)省了計(jì)算時(shí)間。

置換目的是用更好子代解決方案取代原始個(gè)體。本文為更好保持種群多樣性，提出了新的子問題更新策略。給定為新生產(chǎn)的子代解決方案，在所提更新策略中，只有T個(gè)子問題得到更新，所提更新策略見偽代碼2所示。

3.3 快速排序與均勻密度的多目標(biāo)粒子群的簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)

為了提高多目標(biāo)粒子群算法的性能，設(shè)計(jì)快速排序和均勻密度算法。

過程1（快速排序）基于個(gè)體間的非支配對種群進(jìn)行初始化，同時(shí)進(jìn)行初步的個(gè)體排序。

（1）針對PSO算法的種群P內(nèi)，存在的所有個(gè)體按照以下操作過程進(jìn)行快速排序：

①首先假定Sp=?，np=0，則個(gè)體p是PSO算法粒子種群P內(nèi)的某粒子，Sp表示粒子種群內(nèi)被某粒子p支配的粒子，np為粒子群內(nèi)部被個(gè)體p支配的粒子數(shù)量。

②針對粒子群P內(nèi)部的某粒子q，若滿足關(guān)系p?q，那么可得Sp=Sp?{q}；若不滿足關(guān)系q?p，那么可得np=np+1。

③設(shè)定np=0，那么粒子p所處粒子等級為prank= 1，然后把 p附加至現(xiàn)有Pareto前沿內(nèi)，則可得F1= F1?{p}。

（2）循環(huán)執(zhí)行下列步驟直到符合預(yù)設(shè)終止條件Fi=?：

①先初始化Q=?，作用是暫時(shí)對Fi進(jìn)行儲存。

②針對目標(biāo)Fi內(nèi)的所有粒子p，以及Sp內(nèi)的所有粒子q，設(shè)定nq=nq-1，若滿足nq=0，也就是q僅受到 p粒子所支配，則可設(shè)定q排序級別為qrank= i+1，同時(shí)設(shè)定Q=Q?q。

③設(shè)定i=i+1。

④設(shè)定Fi=Q，然后按照順序獲得第2～n個(gè)排序的前沿目標(biāo)F2～Fn。

過程2（均勻密度）在粒子群種群非支配優(yōu)化步驟內(nèi)，保留粒子原則是，首先考慮適應(yīng)度高的粒子，其次考慮密度位置更低的粒子。假定當(dāng)前種群內(nèi)含r組子目標(biāo) f1,f2,…,fr，粒子i的區(qū)域密度為P[i]dis，那么P[i].m是粒子i相對于子目標(biāo)m的適應(yīng)度，則均勻密度指標(biāo)可表示為[12]：

如果FSUD-PSO的粒子規(guī)模設(shè)定為N，則FSUDPSO優(yōu)化過程的復(fù)雜度最大情形是，對粒子種群的r組子函數(shù)采取快速排序，該過程的復(fù)雜度是O(rNlogN)，而擁擠度的計(jì)算復(fù)雜性為O(rN)，均勻密度計(jì)算過程的復(fù)雜度是O(rNlogN)。

基于FSUD-PSO算法的簽名網(wǎng)絡(luò)模型社區(qū)發(fā)現(xiàn)流程見圖6所示，具體計(jì)算過程如下：

Fig.6 FSUD-PSO signature network community discovery process圖6 FSUD-PSO簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)流程

步驟1假定FSUD-PSO算法初始粒子種群大小是N，粒子進(jìn)化的終止代數(shù)是gmax，同時(shí)設(shè)定粒子種群范圍是[Xmin,Xmax]，基于均勻分布方式對粒子種群X初始化，同時(shí)根據(jù)2.2節(jié)指標(biāo)評估粒子初始等級，然后進(jìn)行快速的支配排序，并對其均勻區(qū)域密度進(jìn)行計(jì)算，同時(shí)設(shè)定i=1。

步驟2基于輪盤賭方式在粒子種群pop內(nèi)獲得N 2組粒子個(gè)體構(gòu)建父代粒子Xp，并按照3.1～3.2節(jié)內(nèi)容進(jìn)行粒子更新、位置修復(fù)和粒子置換操作，可獲得更新后的粒子種群規(guī)模為N 2。

步驟3將新粒子種群Xi+1與前一代粒子種群Xi混合獲得混合粒子群Xinter，同時(shí)對T個(gè)子粒子群執(zhí)行過程1的快速排序和過程2的均勻密度計(jì)算，并根據(jù)計(jì)算數(shù)值生成含N組粒子的新粒子群pop。

步驟4令i=i+1，若滿足條件i≤gen，那么重新執(zhí)行步驟2；若滿足條件i>gen，則繼續(xù)執(zhí)行步驟5。

步驟5輸出FSUD-PSO算法所求解簽名網(wǎng)絡(luò)模型社區(qū)的Pareto最優(yōu)發(fā)現(xiàn)策略。

4 仿真實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

本文對基于FSUD-PSO算法的基準(zhǔn)簽名網(wǎng)絡(luò)進(jìn)行測試，通過C++進(jìn)行算法編碼，實(shí)驗(yàn)硬件i7-6800HQ，2.8 GHz，8 GB內(nèi)存DDR3-1600 GHz。對比算法選取MODPSO和MOEA-SN。種群規(guī)模pop和最大算法迭代次數(shù)均設(shè)置為200，變異和交叉概率分別為0.25和0.75，學(xué)習(xí)參數(shù)c1=c2=1.452，慣性權(quán)重ω=0.725，所采取的基準(zhǔn)測試集見表1所示。

Table 1 Signature network information statistics表1 簽名網(wǎng)絡(luò)信息統(tǒng)計(jì)

4.2 參數(shù)影響實(shí)驗(yàn)

在更新操作中，參數(shù)T會(huì)對簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法性能產(chǎn)生影響，下面對其影響進(jìn)行測試。因?yàn)閰?shù)T的不同取值會(huì)導(dǎo)致Pareto前沿不同，采用超體積指數(shù)（HI）對Pareto前沿效果進(jìn)行評價(jià)[15]：

其中，PS為Pareto最優(yōu)解集；yref∈Rm表示Pareto最優(yōu)解占主導(dǎo)地位的所有參考點(diǎn)，m為對象數(shù)量；代表勒貝格測度；?表示支配關(guān)系。

對HI指標(biāo)歸一化，設(shè)置參考點(diǎn)yref為1.2，設(shè)置T變化范圍是T=[1,3,5]，設(shè)置慣性權(quán)重ω=0.725，則FSUD-PSO算法基準(zhǔn)簽名網(wǎng)絡(luò)測試結(jié)果見表2。

根據(jù)表2實(shí)驗(yàn)數(shù)據(jù)可知，隨著參數(shù)T取值增大，HI指標(biāo)先增大后降低，T=3時(shí)的HI指標(biāo)要優(yōu)于T=1和T=5時(shí)的HI指標(biāo)，并且具有相對更低的HI指標(biāo)方差，說明算法穩(wěn)定性相對更佳。主要原因在于，T作為子問題更新數(shù)量，如果T取值過大，將會(huì)浪費(fèi)過多的計(jì)算時(shí)間，并且不利于算法進(jìn)化優(yōu)勢的保留，多樣性將會(huì)大幅下降。同時(shí)隨著參數(shù)T取值增大，算法計(jì)算復(fù)雜度會(huì)相應(yīng)增加。而如果T取值過小，不利于種群進(jìn)化速度的提升。對此這里根據(jù)實(shí)驗(yàn)結(jié)果選取T=3進(jìn)行實(shí)驗(yàn)。

慣性權(quán)重設(shè)置方式會(huì)對算法性能產(chǎn)生影響，這里選取慣性權(quán)重ω=0.725，ω∈[0.6,0.8]隨機(jī)選取和非線性遞減（二次曲線遞減）3種形式，設(shè)置T=3，結(jié)果見表3所示。

根據(jù)表3對比數(shù)據(jù)可知，非線性遞減（二次曲線遞減）形式的慣性權(quán)重設(shè)置方式獲得的算法性能最佳，ω∈[0.6,0.8]隨機(jī)選取方式性能其次。在指標(biāo)穩(wěn)定性方面，ω∈[0.6,0.8]隨機(jī)選取方式穩(wěn)定性最佳，但是和非線性遞減（二次曲線遞減）形式的慣性權(quán)重設(shè)置方式相差不大。

Table 2 Experimental results with different T表2 參數(shù)T影響實(shí)驗(yàn)結(jié)果

4.3 粒子置換實(shí)驗(yàn)

為驗(yàn)證所提策略的有效性，對比使用新置換策略的FSUD-PSO算法和不使用新置換策略的FSUDPSO算法，實(shí)驗(yàn)結(jié)果見圖7所示。因篇幅原因，僅給出4個(gè)基準(zhǔn)庫EGFR、Macrophage、Yeast和Ecoli的Pareto最優(yōu)解方案對比情況。

Table 3 Comparison of inertia weight表3 慣性權(quán)重取值對比

根據(jù)圖7結(jié)果可知，所提新置換策略可有效提高FSUD-PSO算法的簽名網(wǎng)絡(luò)發(fā)現(xiàn)效果，顯示了新置換策略的有效性。

4.4 社區(qū)發(fā)現(xiàn)性能

對于每個(gè)網(wǎng)絡(luò)，選擇具有最大簽名模塊值解決方案的Pareto前沿作為所提算法的最終輸出結(jié)果。圖8為在Macrophage測試集上的社區(qū)發(fā)現(xiàn)結(jié)構(gòu)。

圖8對Macrophage測試集上真實(shí)社區(qū)與本文社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行了對比。可以看出原始社區(qū)發(fā)現(xiàn)結(jié)構(gòu)共分3個(gè)社區(qū)，而本文發(fā)現(xiàn)結(jié)果尋找到4個(gè)社區(qū)，因此本文算法可發(fā)現(xiàn)其他有意義的社區(qū)結(jié)構(gòu)。

基于MODPSO、MOEA-SN和本文FSUD-PSO算法在表2所示6種數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果見表4所示，對比指標(biāo)選取簽名模塊化SQ指標(biāo)。根據(jù)表4數(shù)據(jù)可知，相對于另兩種算法，F(xiàn)SUD-PSO算法具有更高的簽名模塊化SQ值，這表明FSUD-PSO社區(qū)發(fā)現(xiàn)效果要優(yōu)于對比算法。例如在Macrophage測試集中，F(xiàn)SUD-PSO的SQ指標(biāo)相對于MODPSO和MOEA-SN算法的SQ指標(biāo)分別提高7.1%和8.6%。

Fig.7 Effect of replacement operation圖7 替換操作影響實(shí)驗(yàn)

Table 4 Comparison of signature modules表4 簽名模塊化指標(biāo)對比

Fig.8 Macrophage test set圖8 Macrophage測試集

5 結(jié)束語

本文提出了基于位置修復(fù)和粒子置換的FSUDPSO簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，提高了簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)效果。在考慮數(shù)據(jù)耦合和依賴性前提下給出簽名網(wǎng)絡(luò)社區(qū)多目標(biāo)Pareto最優(yōu)目標(biāo)模型，并根據(jù)簽名網(wǎng)絡(luò)特點(diǎn)設(shè)計(jì)了位置修復(fù)和粒子置換，然后設(shè)計(jì)快速排序均勻密度的多目標(biāo)粒子群算法進(jìn)行簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)。實(shí)驗(yàn)結(jié)果驗(yàn)證了FSUD-PSO簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的有效性。

[1]Yu Hai,Zhao Yuli,Cui Kun,et al.A community discovery algorithm based on cross entropy[J].Journal of Computers, 2015,38(8):1574-1581.

[2]Folino F,Pizzuti C.An evolutionary multiobjective approach for community discovery in dynamic networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2014,26(8):1838-1852.

[3]Wang Changdong,Lai Jianhuang,Yu P S.NEIWalk:community discovery in dynamic content-based networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2014,26(7):1734-1748.

[4]Zhang Yingjie,Gong Zhonghan,Chen Qiankun.A complex network community discovery based on immune discrete differential evolution algorithm[J].Journal of Automation, 2015,41(4):749-757.

[5]Zhang Bentao,Li Yong,Jin Depeng,et al.Social-aware peer discovery for D2D communications underlaying cellular networks[J].IEEE Transactions on Wireless Communications,2015,14(5):2426-2439.

[6]Xin Yu,Yang Jing,Xie Zhiqiang.An algorithm for semantic overlapping community discovery based on data field analysis[J].Chinese Science:Information Science,2015, 45(7):918-933.

[7]Zhang Jiankang,Chen Sheng,Mu Xiaomin,et al.Evolutionary-algorithm-assisted joint channel estimation and turbo multiuser detection/decoding for OFDM/SDMA[J]. IEEE Transactions on Vehicular Technology,2014,63(3): 1204-1222.

[8]Liu Qiang,Zhou Bin,Li Shudong,et al.Community detection utilizing a novel multi-swarm fruit fly optimization algorithm with hill-climbing strategy[J].Arabian Journal for Science and Engineering,2016,41(3):807-828.

[9]Wu Chaotian,Li Tianrui,Teng Fei,et al.An improved PSO algorithm for community detection[C]//Proceedings of the 2015 10th International Conference on Intelligent Systems and Knowledge Engineering,Taipei,China,Nov 24-27,2015.Piscataway,USA:IEEE,2015:138-143.

[10]Qiu Xiaohui,Chen Yuzhong.An improved particle swarm optimization algorithm for social network community discovery[J].Journal of Chinese Computer System,2014,35 (6):1422-1426.

[11]Huang Faliang,Zhang Shichao,Zhu Xiaofeng.A network community discovery method based on multi objective optimization[J].Journal of Software,2013,24(9):2062-2077.

[12]Gong Maoguo,Ma Lijia,Zhang Qingfu,et al.Community detection in networks by using multiobjective evolutionary algorithm with decomposition[J].Physica A:Statistical Mechanics and ItsApplications,2012,391(15):4050-4060.

[13]Cao Cen,Ni Qingjian,Zhai Yuqing.A novel community detection method based on discrete particle swarm optimization algorithms in complex networks[C]//Proceedings of the 2015 IEEE Congress on Evolutionary Computation, Sendai,May 25-28,2015.Piscataway,USA:IEEE,2015: 171-178.

[14]Gomez S,Jensen P,Arenas A.Analysis of community structure in networks of correlated data[J].Physical Review E:Statistical Nonlinear&Soft Matter Physics, 2009,80:016114.

[15]Feng Lin,Wang Jing,Liu Shenglan.Multi-label dimensionality reduction and classification with extreme learning machines[J].Journal of Systems Engineering and Electronics,2014,25(3):502-513.

附中文參考文獻(xiàn)：

[1]于海,趙玉麗,崔坤,等.一種基于交叉熵的社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(8):1574-1581.

[4]張英杰,龔中漢,陳乾坤.基于免疫離散差分進(jìn)化算法的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[J].自動(dòng)化學(xué)報(bào),2015,41(4):749-757.

[6]辛宇,楊靜,謝志強(qiáng).基于數(shù)據(jù)場分析的語義重疊社區(qū)發(fā)現(xiàn)算法[J].中國科學(xué):信息科學(xué),2015,45(7):918-933.

[10]邱曉輝,陳羽中.一種面向社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的改進(jìn)粒子群優(yōu)化算法[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(6):1422-1426.

[11]黃發(fā)良,張師超,朱曉峰.基于多目標(biāo)優(yōu)化的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J].軟件學(xué)報(bào),2013,24(9):2062-2077.

XIAO Min was born in 1981.He received the M.S.degree from Hunan University in 2010.Now he is a lecturer at Xiangnan University.His research interests include network security and information technology,etc.

肖敏（1981—），男，湖南郴州人，2010年于湖南大學(xué)獲得碩士學(xué)位，現(xiàn)為湘南學(xué)院講師，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全，信息技術(shù)等。

GUO Mei was born in 1980.She received the M.S.degree from Hunan University in 2010.Now she is a lecturer at Xiangnan University.Her research interests include data analysis and algorithm research,etc.

郭美（1980—），女，廣西柳州人，2010年于湖南大學(xué)獲得碩士學(xué)位，現(xiàn)為湘南學(xué)院講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)分析，算法研究等。

HU Shanquan was born in 1966.He received the M.S.degree from Beijing University of Posts and Telecommunications in 2005.Now he is an associate professor at Xiangnan University.His research interests include network design and development,network security and network engineering,etc.

胡山泉（1966—），男，湖南郴州人，2005年于北京郵電大學(xué)獲得碩士學(xué)位，現(xiàn)為湘南學(xué)院副教授，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)軟件設(shè)計(jì)與開發(fā)，網(wǎng)絡(luò)安全，網(wǎng)絡(luò)工程等。

Location Repair and Particle Replacement Based FSUD-PSO for Signature Network Community Discovery?

XIAO Min1,GUO Mei1+,HU Shanquan2
1.College of Software and Communication Engineering,Xiangnan University,Chenzhou,Hunan 423000,China
2.Department of Information Construction and Management,Xiangnan University,Chenzhou,Hunan 423000,China
+Corresponding author:E-mail:xnguomi1981@sina.com

In order to improve the effect of signature network community discovery,and solve the evaluation indicator of the presence of data coupling and dependence,which leads some limitations of single index optimization in network community,this paper proposes signature network community discovery based on FSUD-PSO(fast sorting and uniform density of multi-objective particle swarm optimization)with location repair and particle replacement.Firstly,this paper studies the signature network model,and gives the community evaluation index of the signature network under the premise of considering the data coupling and dependence.Secondly,this paper builds a signature network model with particle coding and update rules for multi-objective optimization and network according to the characteristics of signature design repair and particle replacement,at the same time,in order to improve multi-objective particle swarm algorithm performance,it designs the FSUD-PSO algorithm.Finally,the effectiveness of the proposed FSUD-PSO signaturenetwork community is verified by comparing with the standard test sets.

position repair;particle replacement;multi-objective particle swarm;fast sorting;uniform density

10.3778/j.issn.1673-9418.1607040

A

TP391

*The Research Project of Teaching Reform in Hunan Ordinary Colleges and Universities under Grant Nos.[2013]223-446,[2012]401-447(湖南省普通高等學(xué)校教學(xué)改革研究項(xiàng)目湘教通[2013]223號446，湘教通[2012]401號447).

Received 2016-06,Accepted 2016-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-08-15,http://www.cnki.net/kcms/detail/11.5602.TP.20160815.1659.012.html