位置修復和粒子置換的FSUD-PSO簽名網絡社區發現*

肖 敏，郭 美+，胡山泉

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

2.湘南學院 信息化建設與管理辦公室，湖南 郴州 423000

位置修復和粒子置換的FSUD-PSO簽名網絡社區發現*

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

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

2.湘南學院 信息化建設與管理辦公室，湖南 郴州 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.

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

位置修復；粒子置換；多目標粒子群；快速排序；均勻密度

1 引言

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

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

盡管單目標社區發現計算效果較好，并可獲得特定網絡社區發現，但真實情況下，網絡社區過程需要滿足多個要求，且此類目標會出現前后矛盾，采用單目標社區發現與實際情形可能不符，對此采用多目標進化算法的社區發現受到學者的關注[11]。文獻[12]采用進化算法與規劃計算方式獲得網絡社區內外部鏈接的同步優化，但算法計算復雜度過高。文獻[13]設計狀態離散的多目標PSO算法（multi-objective discrete particle swarm optimization，MODPSO），實現復雜網絡的社區聚類發現，但算法在保持搜索多樣性能力上還存在缺陷，不利于全局Pareto次優解集的獲得。

本文以簽署網絡社區發現作為研究對象，在相應位置修復和粒子轉換的基礎上提出了快速排序和均勻密度的多目標粒子群算法（fast sorting and uniform density of multi-objective particle swarm optimization，FSUD-PSO）。文章主要框架如下：（1）提出問題，分析基于簽名網絡的模型與相關的評價指標，給出多目標優化的目標；（2）構建簽名網絡模型的多目標優化粒子編碼與更新規則，并設計相應的位置修復和粒子置換策略，設計快速排序和均勻密度的多目標粒子群算法FSUD-PSO；（3）通過仿真實驗進行分析。

2 問題提出

網絡社區通常表示為節點和邊組成的有向連接圖。邊分正邊和負邊兩種類型。網絡社區檢測的任務是根據某些原則將符號網絡劃分為不同的集群。每個集群被稱為社區。

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

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

根據定義1和定義2可知，簽名網絡模型與網絡社區定義的區別在于，前者邊分為正、負鏈接，并在模型中體現。圖1給出帶有9個節點和16條邊的簽名網絡示例。

Fig.1 Example of signature network圖1 簽名網絡示例

在弱簽名社區中，社區內部節點的正鏈接和社區間節點的負鏈接都是密集存在的。根據圖1可知，簽名網絡社區發現的任務是把整個網絡分成許多社區，但劃分優劣標準仍是難題。

2.2 簽名網絡社區指標評價

為給出簽名社區結構劃分定量標準，文獻[14]提出新的模塊量化標準，新指標SQ稱為簽名模塊化：

式中，wij是簽名鄰接矩陣的權重；表示節點所有正（負）權重總和。如果節點i和 j在同一組，δ(i,j)=1；否則δ(i,j)=0。SQ取值越大，社區結構分離程度越好。同時，另一個Silhouette指標為：

Fig.2 Signature community discovery圖2 簽名社區發現

圖2給出迭代次數為90時，SQ=0.423，GS=0.698，以及迭代次數為110時，SQ=0.763，GS= 0.699，兩種情形下的簽名社區結構。

根據圖2可知，隨著簽名社區發現過程的優化，簽名模塊化指標SQ取值也相應增大，但GS指標并未出現數值增加。

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

可以基于權重先驗知識進行評估標準合成，從而基于單目標算法進行優化。但不同評估指標間存在耦合性，導致合并效果不理想，無法獲得最優解。

2.3 算法的優化目標

上述定義表明該模型優化需采用多目標進化算法。這里首先給出多目標Pareto最優相關定義。

（1）Pareto支配：對于簽名網絡模型發現過程V→P，則G=(V,PL,NL)中兩種社區形式P1,P2∈P，滿足如下條件時，形式P1支配P2成立，即P1?P2。

（2）Pareto等價：如果滿足如下條件時，形式P1等價形式P2，即P1=P2。

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

（4）Pareto最優：如果滿足如下條件，簽名網絡模型社區發現策略集P內的某策略P*即為Pareto最優策略。

（5）Pareto前沿：簽名網絡模型最優策略對應的評估向量集是Pareto社區前沿。

對于簽名網絡G=(V,PL,NL)，F是預定義目標集，社區劃分數量為k，該值可根據進化算法進行聚類或預定義給出，則社區發現流程即為查找F令為最優劃分。根據前述定義，可定義簽名網絡多目標社區發現模型為：

式中，X為某簽名網絡模型社區發現策略；gj(X)為社區發現約束，并可定義為：

3 簽名網絡模型的多目標優化

3.1 粒子編碼與更新規則

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

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

每個粒子都代表優化問題的一個解決方案。傳統的粒子更新規則為：

由圖3可知，式（12）、（13）所示粒子更新規則不適于簽名網絡社區發現問題，對此定義新的粒子更新規則為：

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

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

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

Fig.4 Particle updating rules圖4 粒子更新規則

根據圖4，簽名網絡的拓撲信息粒子狀態規則更新，可保證算法獲得可行的社區發現解決方案。

3.2 位置修復和粒子置換

根據編碼方式，兩個不同位置向量可能對應于相同的網絡社區結構，具體如圖5所示。

在圖5中，Xi和Pi分別對應當前和歷史上最好的粒子位置。解碼后，Xi和Pi代表同一網絡社區結構。根據式（14）、（15），可得非零向量Vi，Xi會隨時間改變。為節省時間，設計位置修復算法，見偽代碼1所示。

Fig.5 Community structure of position vector圖5 位置向量社區結構

如圖5所示，經過位置修復后，根據式（14）可得Xi和Pi的一致零向量。不需要計算新的位置矢量，節省了計算時間。

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

3.3 快速排序與均勻密度的多目標粒子群的簽名網絡社區發現

為了提高多目標粒子群算法的性能，設計快速排序和均勻密度算法。

過程1（快速排序）基于個體間的非支配對種群進行初始化，同時進行初步的個體排序。

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

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

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

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

（2）循環執行下列步驟直到符合預設終止條件Fi=?：

①先初始化Q=?，作用是暫時對Fi進行儲存。

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

③設定i=i+1。

④設定Fi=Q，然后按照順序獲得第2～n個排序的前沿目標F2～Fn。

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

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

基于FSUD-PSO算法的簽名網絡模型社區發現流程見圖6所示，具體計算過程如下：

Fig.6 FSUD-PSO signature network community discovery process圖6 FSUD-PSO簽名網絡社區發現流程

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

步驟2基于輪盤賭方式在粒子種群pop內獲得N 2組粒子個體構建父代粒子Xp，并按照3.1～3.2節內容進行粒子更新、位置修復和粒子置換操作，可獲得更新后的粒子種群規模為N 2。

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

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

步驟5輸出FSUD-PSO算法所求解簽名網絡模型社區的Pareto最優發現策略。

4 仿真實驗與分析

4.1 實驗設置

本文對基于FSUD-PSO算法的基準簽名網絡進行測試，通過C++進行算法編碼，實驗硬件i7-6800HQ，2.8 GHz，8 GB內存DDR3-1600 GHz。對比算法選取MODPSO和MOEA-SN。種群規模pop和最大算法迭代次數均設置為200，變異和交叉概率分別為0.25和0.75，學習參數c1=c2=1.452，慣性權重ω=0.725，所采取的基準測試集見表1所示。

Table 1 Signature network information statistics表1 簽名網絡信息統計

4.2 參數影響實驗

在更新操作中，參數T會對簽名網絡社區發現算法性能產生影響，下面對其影響進行測試。因為參數T的不同取值會導致Pareto前沿不同，采用超體積指數（HI）對Pareto前沿效果進行評價[15]：

其中，PS為Pareto最優解集；yref∈Rm表示Pareto最優解占主導地位的所有參考點，m為對象數量；代表勒貝格測度；?表示支配關系。

對HI指標歸一化，設置參考點yref為1.2，設置T變化范圍是T=[1,3,5]，設置慣性權重ω=0.725，則FSUD-PSO算法基準簽名網絡測試結果見表2。

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

慣性權重設置方式會對算法性能產生影響，這里選取慣性權重ω=0.725，ω∈[0.6,0.8]隨機選取和非線性遞減（二次曲線遞減）3種形式，設置T=3，結果見表3所示。

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

Table 2 Experimental results with different T表2 參數T影響實驗結果

4.3 粒子置換實驗

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

Table 3 Comparison of inertia weight表3 慣性權重取值對比

根據圖7結果可知，所提新置換策略可有效提高FSUD-PSO算法的簽名網絡發現效果，顯示了新置換策略的有效性。

4.4 社區發現性能

對于每個網絡，選擇具有最大簽名模塊值解決方案的Pareto前沿作為所提算法的最終輸出結果。圖8為在Macrophage測試集上的社區發現結構。

圖8對Macrophage測試集上真實社區與本文社區發現結果進行了對比。可以看出原始社區發現結構共分3個社區，而本文發現結果尋找到4個社區，因此本文算法可發現其他有意義的社區結構。

基于MODPSO、MOEA-SN和本文FSUD-PSO算法在表2所示6種數據集上的實驗結果見表4所示，對比指標選取簽名模塊化SQ指標。根據表4數據可知，相對于另兩種算法，FSUD-PSO算法具有更高的簽名模塊化SQ值，這表明FSUD-PSO社區發現效果要優于對比算法。例如在Macrophage測試集中，FSUD-PSO的SQ指標相對于MODPSO和MOEA-SN算法的SQ指標分別提高7.1%和8.6%。

Fig.7 Effect of replacement operation圖7 替換操作影響實驗

Table 4 Comparison of signature modules表4 簽名模塊化指標對比

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

5 結束語

本文提出了基于位置修復和粒子置換的FSUDPSO簽名網絡社區發現算法，提高了簽名網絡社區發現效果。在考慮數據耦合和依賴性前提下給出簽名網絡社區多目標Pareto最優目標模型，并根據簽名網絡特點設計了位置修復和粒子置換，然后設計快速排序均勻密度的多目標粒子群算法進行簽名網絡社區發現。實驗結果驗證了FSUD-PSO簽名網絡社區發現的有效性。

[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.

附中文參考文獻：

[1]于海,趙玉麗,崔坤,等.一種基于交叉熵的社區發現算法[J].計算機學報,2015,38(8):1574-1581.

[4]張英杰,龔中漢,陳乾坤.基于免疫離散差分進化算法的復雜網絡社區發現[J].自動化學報,2015,41(4):749-757.

[6]辛宇,楊靜,謝志強.基于數據場分析的語義重疊社區發現算法[J].中國科學:信息科學,2015,45(7):918-933.

[10]邱曉輝,陳羽中.一種面向社會網絡社區發現的改進粒子群優化算法[J].小型微型計算機系統,2014,35(6):1422-1426.

[11]黃發良,張師超,朱曉峰.基于多目標優化的網絡社區發現方法[J].軟件學報,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年于湖南大學獲得碩士學位，現為湘南學院講師，主要研究領域為網絡安全，信息技術等。

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年于湖南大學獲得碩士學位，現為湘南學院講師，主要研究領域為數據分析，算法研究等。

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年于北京郵電大學獲得碩士學位，現為湘南學院副教授，主要研究領域為網絡軟件設計與開發，網絡安全，網絡工程等。

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(湖南省普通高等學校教學改革研究項目湘教通[2013]223號446，湘教通[2012]401號447).

Received 2016-06,Accepted 2016-08.

CNKI網絡優先出版:2016-08-15,http://www.cnki.net/kcms/detail/11.5602.TP.20160815.1659.012.html