Community Detection in Complex Networks Using Immune Discrete Differential Evolution Algorithm
-
摘要: 针对复杂网络社区发现问题,在标准差分进化算法的框架下,提出一种新型免疫离散差分进化算法(Immune discrete differential evolution, IDDE).该算法通过标签传播策略生成初始种群,采用离散差分进化策略来保证种群在问题空间的全局搜索能力,同时对种群中的优秀个体执行针对性的高频克隆变异操作,以提高算法的局部开发能力,改善算法的收敛性能.在计算机生成网络与真实世界网络中的仿真实验结果表明:IDDE算法具有较强的寻优性能与鲁棒性,能够有效探测复杂网络中存在的社区结构.Abstract: Aimed at the existing problem of community detection in complex networks, a novel immune discrete differential evolution(IDDE) is proposed in the framework of standard differential evolution. In the proposed method, the initial population is generated through label propagation, and the discrete differential evolution strategy is utilized to ensure the global searching ability of the IDDE; meanwhile, the high-frequency clonal selection mutation operation is applied to excellent individuals of the population to improve the local exploitation ability and the convergence performance of the IDDE. Artificial networks and several real networks are employed to test the performance of the IDDE, and the testing results show that the IDDE achieves better searching ability and stronger robustness, and that it can detect the community structure in complex networks effectively.
-
Key words:
- Differential evolution /
- clonal selection /
- community detection /
- modularity
-
[1] Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826 [2] [2] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2):026113 [3] [3] Zhang S H, Wang R S, Zhang X S. Identification of overlapping community structure in complex networks using fuzzy means clustering. Physica A:Statistical Mechanics and Its Applications, 2007, 374(1):483-490 [4] Huang Fa-Liang, Huang Ming-Xuan, Yuan Chang-An, Yao Zhi-Qiang. Spectral clustering ensemble algorithm for discovering overlapping communities in social networks. Control and Decision, 2014, 29(4):713-718(黄发良, 黄名选, 元昌安, 姚志强. 网络重叠社区发现的谱聚类集成算法. 控制与决策, 2014, 29(4):713-718) [5] [5] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale network. Physical Review E, 2007, 76(3):036106 [6] Jin Di, Liu Jie, Yang Bo, He Dong-Xiao, Liu Da-You. Genetic algorithm with local search for community detection in large-scale complex networks. Acta Automatica Sinica, 2011, 37(7):873-882(金弟, 刘杰, 杨博, 何东晓, 刘大有. 局部搜索与遗传算法结合的大规模复杂网络社区探测. 自动化学报, 2011, 37(7):873-882) [7] [7] Shang R H, Bai J, Jiao L C, Jin C. Community detection based on modularity and an improved genetic algorithm. Physica A:Statistical Mechanics and Its Applications, 2013, 392(5):1215-1231 [8] Huang Fa-Liang, Zhang Shi-Chao, Zhu Xiao-Feng. Discovering network community based on multi-objective optimization. Journal of Software, 2013, 24(9):2062-2077(黄发良, 张师超, 朱晓峰. 基于多目标优化的网络社区发现方法. 软件学报, 2013, 24(9):2062-2077) [9] [9] Gong M G, Cai Q, Chen X W, Ma L J. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Transactions on Evolutionary Computation, 2014, 18(1):82-97 [10] Luo Zhi-Gang, Ding Fan, Jiang Xiao-Zhou, Shi Jin-Long. New progress on community detection in complex networks. Journal of National University of Defense Technology, 2011, 33(1):47-52(骆志刚, 丁凡, 蒋晓舟, 石金龙. 复杂网络社团发现算法研究新进展. 国防科技大学学报, 2011, 33(1):47-52) [11] Brandes U, Delling D, Gaertler M, Goerke R, Hoefer M, Nikoloski Z, Wagner D. Maximizing modularity is hard. arXiv:physics/0608255, 2006. [12] Guimer R, Sales-Pardo M, Amaral L A N. Modularity from fluctuations in random graphs and complex network. Physical Review E, 2004, 70(2):025101 [13] Huang Fa-Liang, Xiao Nan-Feng. Particle-swarm-optimization algorithm to discover network community. Control Theory and Application, 2011, 28(9):1135-1140(黄发良, 肖南峰. 网络社区发现的粒子群优化算法. 控制理论与应用, 2011, 28(9):1135-1140) [14] Jia G B, Cai Z X, Musolesi M, Wang Y, Tennant D A, Weber R J, Heath J K, He S. Community detection in social and biological networks using differential evolution. In:Proceedings of the 6th International Conference on Learning and Intelligent Optimization Conference LION6. Heidelberg:Springer, 2012. 71-85 [15] Wolpert D H, Macready W G. No free lunch theorems for optimization. IEEE Transaction on Evolutionary Computation, 1997, 2(1):62-87 [16] Santo F. Community detection in graphs. Physics Reports, 2010, 486(3-5):75-174 [17] Fortunato S, Barthelemy M. Resolution limit in community detection. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1):36-41 [18] Storn R, Price K. Differential evolution:a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11(4):341-359 [19] Karabulut K, Tasgetiren M F. A discrete artificial bee colony algorithm for the traveling salesman problem with time windows. In:Proceedings of the 2012 IEEE Congress Evolutionary Computation. Piscataway, NJ:IEEE, 2012. 1-7 [20] Pan Q K, Mehmet F T, Liang Y C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers Industrial Engineering, 2008, 55(4):795-816 [21] Tasgin M, Herdagdelen A, Bingol H. Community detection in complex networks using genetic algorithms. arXiv:0711.0491, 2007. [22] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Physical Review E, 2004, 70(6):066111 [23] Gong M G, Fu B, Jiao L C, Du H F. Memetic algorithm for community detection in networks. Physical Review E, 2011, 84(5):056101 [24] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E, 2008, 78(4):046110 [25] Danon L, Daz-Guilera A, Duch J, Arenas A. Comparing community structure identification. Journal of Statistical Mechanics:Theory and Experiment, 2005, 2005(09):P09008 [26] Derrac J, Garca S, Molina D, Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 2011, 1(1):3-18 [27] Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1997, 33(4):452-473 [28] Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 2003, 54(4):396-405
点击查看大图
计量
- 文章访问数: 1691
- HTML全文浏览量: 97
- PDF下载量: 1531
- 被引次数: 0