Quantum-Behaved Discrete Particle Swarm Optimization for Complex Network Clustering
YANG Zhongbao1,2, CHU Yangjie2, HONG Ye2, JIANG Dengying2
1.School of Mathematics and Statistic, Qiannan Normal University for Natinalities, Douyun 558000, China; 2.Wuhan University of Technology,Wuhan 430070,China
Abstract：Community structure is one of the most important features of complex network. In order to solve the problem of resolution limit of modularity optimization methods, a quantum-behaved discrete particle swarm optimization for complex network clustering is proposed in non-overlapping community detection algorithm (NQD-PSO). The core node and neighborly common nodes are constructed asa motif, which is the initial value of the quantum particle swarm optimization algorithm. At the same time, constructing the motif weighted community clustering function as the adaptive function of the algorithm, while it can use the triangular model to judge the problem of community stability measurement for quantifying the stability of community then the compression factor is adopted to adjust the global and local search model, which makes the algorithm globally converge by combining with quantum particle swarm optimization. Compared with other algorithms, NQD-PSO algorithm uses motif orderly table coding method, and experimental results on both synthetic and real datasets show thatthe NQD-PSO algorithm can mine more high-quality community structures.
[1]周旭.复杂网络中社区发现算法研究[D].吉林大学,2016. Zhou Xu,Research on community detection algorithms in complex networks[D].JiLinJilin University,2016. [2]尚敬文,王朝坤等.基于深度稀疏自动编码器的社区发现算法[J].软件学报,2017,28(3):648662 ShangJingwen,Wang Chaokun,et al.Commu-nity detection algorithm based on deep sparse autoencoder[J].Journal of Softwre,2017,28(3):648662. [3]Pizzuti C. GA-net: A genetic algorithm for community detection in social networks[C]// International Conference on Parallel Problem Solving From Nature: PPSN X.Springer-Verlag,2008:10811090. [4]Pizzuti C. A multi-objective genetic algorithm for community detection in networks[C]// IEEE International Conference on TOOLS with Artificial Intelligence. IEEE Computer Society,2009:379386. [5]白云,任国霞.基于粒子群优化的复杂网络社区挖掘[J].计算机工程,2015,41(3):177181. Bai Yun,Ren Guoxia. Complex network comm-unity mining based on particle swarm optimization[J].Computer Engineering,2015,41(3):177181. [6]Gong M, Cai Q, Chen X, et al. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2014,18(1):8297. [7]Li L, Jiao L, Zhao J, et al. Quantum-behaved discrete multi-objective particle swarm optimization for complex network clustering[J].Pattern Recognition,2017,63:114. [8]黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法[J].软件学报,2013,24(9):2062-2077. Huang Faliang, Zhang Shichao,Zhu Xiaofeng.Discovering network community based on multi-objective optimization[J].Journal of Software,2013,24(9):20622077. [9]韩忠明,谭旭升,陈炎,等.NCSS:一种快速有效的复杂网络社团划分算法[J].中国科学:信息科学,2016,46(4):431444. Han Zhongming,Tan Xusheng, et al. NCSS:an effective and efficiet complex network community detection algorithm[J].Scientia Sinica informations,2016,46(4):431444. [10] Prat-Pérez A, Dominguez-Sal D, Brunat J M. Shap-ing communities out of triangles[J].Computer Science,2012:16771681. [11] 张成兴.时变压缩因子粒子群算法[J].计算机工程与应用,2015,51(23):5964 Zhang Chengxing.Particle swarm optimization based on time varying constrict factor[J].Computer Engineering and Applications,2015,51(23):5964. [12] 方伟,孙俊,谢振平,等.量子粒子群优化算法的收敛性分析及控制参数研究[J].物理学报,2010,59(6):36863694. Fang Wei, Sun Jun, Xie Zhenping, et al. Convergence analysis of quantum-behaved particle swarm optimization algorithm and study on its control parameter[J].Acta Physica Sinica,2010,59(6):36863694. [13] Handl J,Knowles J.An evolutionary approach to multiobjective clustering[J].IEEE Transactions on Evolutionary Computation,2007,11(1):5676. [14] Gómez S, Jensen P, Arenas A. Analysis of community structure in networks of correlated data[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2008,80(2):016114. [15] Lancichinetti A,Fortunato S, Radicchi F.Benchmark graphs for testing community detection algorithms.[J].Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008,78(4Pt2):04611 [16] Girvan M,Newman M E J.Community structure in social andbiological networks[J].Proc of National Academy of Science,2002,9(12):78217826 [17] Li Y Y,Wang Y,Chen J,et al. Overlapping community detection through an improved multi-objective quantum-behaved particle swarm optimization[J].Journal of Heuristics,2015,21(4):549575.
