位置修复和粒子置换的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