肖 敏，郭 美+，胡山泉

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)效果，解決其評(píng)估指標(biāo)存在的數(shù)據(jù)耦合和依賴(lài)性，造成網(wǎng)絡(luò)社區(qū)單指標(biāo)優(yōu)化存在較大局限性的問(wèn)題，提出了基于位置修復(fù)和粒子置換的FSUD-PSO（fast sorting and uniform density of multi-objective particle swarm optimization）簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。首先，對(duì)簽名網(wǎng)絡(luò)模型進(jìn)行研究，并在考慮數(shù)據(jù)耦合和依賴(lài)性前提下給出簽名網(wǎng)絡(luò)社區(qū)評(píng)價(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；最后，通過(guò)標(biāo)準(zhǔn)測(cè)試集實(shí)驗(yàn)對(duì)比，驗(yàn)證了所提FSUD-PSO簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的有效性。

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

1 引言

網(wǎng)絡(luò)無(wú)處不在，前所未有地改變著人們的日常生活[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ò)對(duì)象，邊緣表示對(duì)象之間的關(guān)系。通過(guò)分析圖的特性可以得到網(wǎng)絡(luò)的特性。網(wǎng)絡(luò)有很多特性，如小世界性、無(wú)標(biāo)度特性等，其中網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)是最受關(guān)注的特性。在圖形語(yǔ)言中，一個(gè)社區(qū)被稱(chēng)為子圖，特點(diǎn)是社區(qū)內(nèi)節(jié)點(diǎn)之間的相似性要高于社區(qū)間節(jié)點(diǎn)的相似性[4]。

社區(qū)結(jié)構(gòu)對(duì)許多網(wǎng)絡(luò)非常重要，因此復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)已引起了學(xué)者們的極大興趣[5]。到目前為止，已經(jīng)提出了大量的方法來(lái)檢測(cè)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。近年來(lái)，研究者們提出了一類(lèi)用于優(yōu)化社區(qū)質(zhì)量評(píng)判指標(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ì)量評(píng)判標(biāo)準(zhǔn)，并采用GA-Net獲得網(wǎng)絡(luò)的檢測(cè)優(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ū)檢測(cè)；文獻(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ū)過(guò)程需要滿(mǎn)足多個(gè)要求，且此類(lèi)目標(biāo)會(huì)出現(xiàn)前后矛盾，采用單目標(biāo)社區(qū)發(fā)現(xiàn)與實(shí)際情形可能不符，對(duì)此采用多目標(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ù)雜度過(guò)高。文獻(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ū)聚類(lèi)發(fā)現(xiàn)，但算法在保持搜索多樣性能力上還存在缺陷，不利于全局Pareto次優(yōu)解集的獲得。

本文以簽署網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)作為研究對(duì)象，在相應(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èn)題，分析基于簽名網(wǎng)絡(luò)的模型與相關(guān)的評(píng)價(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）通過(guò)仿真實(shí)驗(yàn)進(jìn)行分析。

2 問(wèn)題提出

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

定義1（網(wǎng)絡(luò)社區(qū)）對(duì)于無(wú)向連接網(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)評(píng)價(jià)

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

式中，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)過(guò)程的優(yōu)化，簽名模塊化指標(biāo)SQ取值也相應(yīng)增大，但GS指標(biāo)并未出現(xiàn)數(shù)值增加。

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

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

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

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

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

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

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

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

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

對(duì)于簽名網(wǎng)絡(luò)G=(V,PL,NL)，F(xiàn)是預(yù)定義目標(biāo)集，社區(qū)劃分?jǐn)?shù)量為k，該值可根據(jù)進(jìn)化算法進(jìn)行聚類(lèi)或預(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)化問(wèn)題的一個(gè)解決方案。傳統(tǒng)的粒子更新規(guī)則為：

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

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

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

式中，Nj為節(jié)點(diǎn) j的鄰域粒子集；如果a=b，δ(a, b)=1，否則δ(a,b)=0。操作步驟見(jiàn)圖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è)不同位置向量可能對(duì)應(yīng)于相同的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，具體如圖5所示。

在圖5中，Xi和Pi分別對(duì)應(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ù)算法，見(jiàn)偽代碼1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

過(guò)程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相對(duì)于子目標(biāo)m的適應(yīng)度，則均勻密度指標(biāo)可表示為[12]：

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

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

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]，基于均勻分布方式對(duì)粒子種群X初始化，同時(shí)根據(jù)2.2節(jié)指標(biāo)評(píng)估粒子初始等級(jí)，然后進(jìn)行快速的支配排序，并對(duì)其均勻區(qū)域密度進(jìn)行計(jì)算，同時(shí)設(shè)定i=1。

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

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

步驟4令i=i+1，若滿(mǎn)足條件i≤gen，那么重新執(zhí)行步驟2；若滿(mǎn)足條件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è)置

本文對(duì)基于FSUD-PSO算法的基準(zhǔn)簽名網(wǎng)絡(luò)進(jìn)行測(cè)試，通過(guò)C++進(jìn)行算法編碼，實(shí)驗(yàn)硬件i7-6800HQ，2.8 GHz，8 GB內(nèi)存DDR3-1600 GHz。對(duì)比算法選取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)測(cè)試集見(jiàn)表1所示。

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

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

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

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

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

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

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

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

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

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

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

圖8對(duì)Macrophage測(cè)試集上真實(shí)社區(qū)與本文社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行了對(duì)比。可以看出原始社區(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é)果見(jiàn)表4所示，對(duì)比指標(biāo)選取簽名模塊化SQ指標(biāo)。根據(jù)表4數(shù)據(jù)可知，相對(duì)于另兩種算法，F(xiàn)SUD-PSO算法具有更高的簽名模塊化SQ值，這表明FSUD-PSO社區(qū)發(fā)現(xiàn)效果要優(yōu)于對(duì)比算法。例如在Macrophage測(cè)試集中，F(xiàn)SUD-PSO的SQ指標(biāo)相對(duì)于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)對(duì)比

Fig.8 Macrophage test set圖8 Macrophage測(cè)試集

5 結(jié)束語(yǔ)

本文提出了基于位置修復(fù)和粒子置換的FSUDPSO簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，提高了簽名網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)效果。在考慮數(shù)據(jù)耦合和依賴(lài)性前提下給出簽名網(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ù)場(chǎng)分析的語(yǔ)義重疊社區(qū)發(fā)現(xiàn)算法[J].中國(guó)科學(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ì)與開(kāi)發(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號(hào)446，湘教通[2012]401號(hào)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