Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem

doi:10.11772/j.issn.1001-9081.2020060800

Abstract

Abstract: For solving the problem of multi-objective community detection in complex network, a Discrete Random Drift Particle Swarm Optimization (DRDPSO) algorithm was proposed. Firstly, by performing random coding operation on communities and using discretization operation for random drift optimization algorithm, the local network structure was improved and the global modularity value was gradually enhanced. Secondly, two objective functions, Kernel K-Means (KKM) and Ratio Cut (RC), were used to control the community size in the network and ameliorate the modularity resolution ratio. Finally, the Pareto non-inferior solution sets were updated step by step according to the multi-objective solving strategy, and the objective community structures satisfying the requirements were selected from the Pareto non-inferior solution sets. To verify the effectiveness of proposed algorithm, the comparison experiments of DRDPSO algorithm with other community detection algorithms were carried out on three generation networks with 10 different parameter configurations and three real networks. And the community detection results obtained by different algorithms were compared and analyzed by using two evaluation indicators of best community. Experimental results show that using DRDPSO algorithm for solving the multi-objective community detection problem in complex network, the probability of obtaining the highest community detection evaluation indexes (normalized mutual information and modularity) is more than 95%. The application of DRDPSO algorithm in real network can further improve the accuracy and robustness of network community division.

Key words: community detection, multi-objective complex network, discretization, Random Drift Particle Swam Optimization (RDPSO), modularity, Pareto non-inferior solution set

摘要： 针对求解复杂网络的多目标社区发现问题，提出了一种离散化随机漂移粒子群优化（DRDPSO）算法。首先，通过对社区进行随机化编码操作和针对随机漂移算法的离散化操作，来改善局部网络结构并逐渐增强全局模块度值；其次，根据核K均值（KKM）和比例割（RC）两个目标函数来控制网络中的社区规模、缓解模块度分辨率限制；最后，根据多目标求解策略逐步更新Pareto非劣解集，从Pareto非劣解集选取满足需求的目标社区结构。为了验证所提算法的有效性，将DRDPSO算法与其他社区发现算法在三种具有10个不同参数设置的生成网络及三种真实网络上进行对比实验，并采用两个最佳社区评价指标对各算法获得的社区发现结果进行对比分析。实验结果表明，使用DRDPSO算法求解复杂网络的多目标社区发现问题时，获得的社区发现评价指标（归一化互信息和模块度）最高的概率达到95%以上。可见DRDPSO算法在真实网络进行应用能进一步地提高网络社区划分的精确度和鲁棒性。

关键词: 社区发现, 多目标复杂网络, 离散化, 随机漂移粒子群优化, 模块度, Pareto非劣解集

CLC Number:

TP301.6
TP18

LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem[J]. Journal of Computer Applications, 2021, 41(3): 803-811.

李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.

References

[1] VILLANDRE L,STEPHENS D A,LABBE A,et al. Assessment of overlap of phylogenetic transmission clusters and communities in simple sexual contact networks:applications to HIV-1[J]. PLoS One, 2016, 11(2):No. e0148459.
[2] AI J,LIU Y,SU Z,et al. Link prediction in recommender systems based on multi-factor network modeling and community detection[J]. EPL(Europhysics Letters),2019,126(3):No. 38003.
[3] BIOGLIO L,PENSA R G. Impact of neighbors on the privacy of individuals in online social networks[J]. Procedia Computer Science,2017,108:28-37.
[4] 李金华. 广义创新网络的演化结构及其现实意义[J]. 科学学与科学技术管理,2008,29(2):101-107. (LI J H. Evolving structure of generalized innovation networks and its practical implications[J]. Science of Science and Management of S. & T., 2008, 29(2):101-107.)
[5] 赵卫绩, 张凤斌, 刘井莲. 复杂网络社区发现研究进展[J]. 计算机科学,2020,47(2):10-20.(ZHAO W J,ZHANG F B,LIU J L. Review on community detection in complex networks[J]. Compute Science,2020,47(2):10-20.)
[6] GIRVAN M,NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Science of the United States of America,2002,99(12):7821-7826.
[7] ROSVALL M,BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008,105(4):1118-1123.
[8] RAGHAVAN U N,ALBERT R,KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E,Statistical,Nonlinear,and Soft Matter Physics,2007,76(3 Pt 2):No. 036106.
[9] DONG S. Improved label propagation algorithm for overlapping community detection[J]. Computing,2020,102(10):2185-2198.
[10] NEWMAN M E J. Fast algorithm for detecting community structure in network[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004:69(6 Pt 2):No. 066133.
[11] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.
[12] CLAUSET A,NEWMAN M E J,MOORE C. Finding community structure in very large networks[J]. Physical Review E, Statistical,Nonlinear,and Soft Matter Physics,2004,70(6 Pt 2):No. 066111.
[13] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics:Theory and Experiment,2008,2008:No. P10008.
[14] SMITH K,JANIKOW C,CLIMER S. Evolving to recognize highdimensional relationships in data:GA operators and representation designed expressly for community detection[C]//Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion. New York:ACM,2019:308-309.
[15] 陈永建, 周艳, 刘超英. 基于遗传算法的大规模社交网络社区发现算法[J]. 计算机工程与设计,2018,39(8):2452-2459. (CHEN Y J, ZHOU Y, LIU C Y. Community discovering algorithm of large scale social networks based on genetic algorithm[J]. Computer Engineering and Design,2018,39(8):2452-2459.)
[16] 张英杰, 龚中汉, 陈乾坤. 基于免疫离散差分进化算法的复杂网络社区发现[J]. 自动化学报,2015,41(4):749-757. (ZHANG Y J,GONG Z H,CHEN Q K. Community detection in complex networks using immune discrete differential evolution algorithm[J]. Acta Automatica Sinica,2015,41(4):749-757.)
[17] BELKHIRI Y, KAMELN, DIRAS H, et al. Bee swarm optimization for community detection in complex network[C]//Proceedings of the 2017 World Conference on Information System and Technologies,AISC 570. Cham:Springer,2017:73-85.
[18] CAI Q,GONG M,MA L,et al. Greedy discrete particle swarm optimization for large-scale social network clustering[J]. Information Sciences,2015,316:503-516.
[19] CAI X,SHI Y,ZHU Y,et al. An algorithm Q-PSO for community detection in complex networks[C]//Proceedings of the 16th International Symposium on Distributed Computing and Applications to Business,Engineering and Science. Piscataway:IEEE,2017:76-79.
[20] 孙延维, 彭智明, 李健波. 基于粒子群优化与模糊聚类的社区发现算法[J]. 重庆邮电大学学报(自然科学版),2015,27(5):660-666.(SUN Y W,PENG Z M,LI J B. Community detection algorithm based on particle swarm optimization and fuzzy clustering[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2015,27(5):660-666.)
[21] CAI Q,GONG M,SHEN B,et al. Discrete particle swarm optimization for identifying community structures in signed social networks[J]. Neural Networks,2014,58:4-13.
[22] CAO C,NI Q,ZHAI Y. 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. Piscataway:IEEE,2015:171-178.
[23] CHAITANYA K,SOMAYAJULU D,KRISHNA P R. A PSO based community detection in social networks with node attributes[C]//Proceedings of the 2018 IEEE Congress on Evolutionary Computation. Piscataway:IEEE,2018:1-6.
[24] SUN J,WU X,PALADE V,et al. Random drift particle swarm optimization algorithm:convergence analysis and parameter selection[J]. Machine Learning,2015,101(1/2/3):345-376.
[25] RADICCHI F,CASTELLANO C,CECCONI F,et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004,101(9):2658-2663.
[26] FORTUNATO S. Community detection in graphs[J]. Physics Reports,2010,486(3/4/5):75-174.
[27] ANGELINI L, BOCCALETTI S, MARINAZZO D, et al. Identification of network modules by optimization of ratio association[J]. Chaos:An Interdisciplinary Journal of Nonlinear Science,2007,17(2):No. 023114.
[28] FORTUNATO S, BARTHÉLEMY M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America,2007,104(1):36-41.
[29] CLERC M, KENNEDY J. The particle swarm:explosion, stability,and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.
[30] 邱晓辉, 陈羽中. 一种面向社会网络社区发现的改进粒子群优化算法[J]. 小型微型计算机系统,2014,35(6):1422-1426. (QIU X H,CHEN Y Z. An improved particle-swarm-optimization algorithm for community discovery in social networks[J]. Journal of Chinese Computer Systems,2014,35(6):1422-1426.)
[31] GONG M,CAI Q,LI Y,et al. An improved memetic algorithm for community detection in complex networks[C]//Proceedings of the 2012 IEEE Congress on Evolutionary Computation. Piscataway:IEEE,2012:1-8.
[32] SHANG R,LUO S,LI Y,et al. Large-scale community detection based on node membership grade and sub-communities integration[J]. Physica A:Statistical Mechanics and its Applications, 2015,428:279-294.
[33] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E,Statistical, Nonlinear, and Soft Matter Physics,2008,78(4 Pt 2):No. 046110.