基于免疫离散差分进化算法的复杂网络社区发现

张英杰; 龚中汉; 陈乾坤

doi:10.16383/j.aas.2015.c140018

基于免疫离散差分进化算法的复杂网络社区发现

doi: 10.16383/j.aas.2015.c140018

1.
湖南大学信息科学与工程学院长沙 410082

基金项目:

国家自然科学基金(61440026),教育部博士点基金(20110161110035),湖南省自然科学基金重点项目(13JJA002)资助

详细信息

作者简介:
龚中汉湖南大学信息科学与工程学院硕士研究生.2011年获得湖南大学信息科学与工程学院学士学位.主要研究方向为进化计算和数据挖掘.E-mail:hncl18@hnu.edu.cn

通讯作者:
张英杰湖南大学信息科学与工程学院副教授.2005年获得湖南大学控制理论与控制工程博士学位.主要研究方向为智能控制,计算智能和节能优化控制.本文通信作者.E-mail:zhangyj@hnu.edu.cn

计量
- 文章访问数: 1767
- HTML全文浏览量: 97
- PDF下载量: 1537
- 被引次数: 0
出版历程
- 收稿日期: 2014-01-10
- 修回日期: 2014-12-02
- 刊出日期: 2015-04-20

Community Detection in Complex Networks Using Immune Discrete Differential Evolution Algorithm

1.
College of Information Science and Engineering, Hunan University, Changsha 410082

Funds:

Supported by National Natural Science Foundation of China(61440026), Doctoral Fund of Ministry of Education of China(20110161110035), and Hunan Provincial Natural Science Foundation of China(13JJA002)

摘要

摘要: 针对复杂网络社区发现问题,在标准差分进化算法的框架下,提出一种新型免疫离散差分进化算法(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.
- Differential evolution /
- clonal selection /
- community detection /
- modularity

HTML全文

参考文献(28)

[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

施引文献

资源附件(0)

访问统计

计量

文章访问数: 1767
HTML全文浏览量: 97
PDF下载量: 1537
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于免疫离散差分进化算法的复杂网络社区发现

doi: 10.16383/j.aas.2015.c140018

作者简介:
龚中汉湖南大学信息科学与工程学院硕士研究生.2011年获得湖南大学信息科学与工程学院学士学位.主要研究方向为进化计算和数据挖掘.E-mail:hncl18@hnu.edu.cn

通讯作者:
张英杰湖南大学信息科学与工程学院副教授.2005年获得湖南大学控制理论与控制工程博士学位.主要研究方向为智能控制,计算智能和节能优化控制.本文通信作者.E-mail:zhangyj@hnu.edu.cn

计量

Community Detection in Complex Networks Using Immune Discrete Differential Evolution Algorithm

计量

目录

留言板

基于免疫离散差分进化算法的复杂网络社区发现

doi: 10.16383/j.aas.2015.c140018

作者简介: 龚中汉 湖南大学信息科学与工程学院硕士研究生.2011年获得湖南大学信息科学与工程学院学士学位.主要研究方向为进化计算和数据挖掘.E-mail:hncl18@hnu.edu.cn

通讯作者: 张英杰 湖南大学信息科学与工程学院副教授.2005年获得湖南大学控制理论与控制工程博士学位.主要研究方向为智能控制,计算智能和节能优化控制.本文通信作者.E-mail:zhangyj@hnu.edu.cn

计量

出版历程

Community Detection in Complex Networks Using Immune Discrete Differential Evolution Algorithm

计量

出版历程

目录

作者简介:
龚中汉湖南大学信息科学与工程学院硕士研究生.2011年获得湖南大学信息科学与工程学院学士学位.主要研究方向为进化计算和数据挖掘.E-mail:hncl18@hnu.edu.cn

通讯作者:
张英杰湖南大学信息科学与工程学院副教授.2005年获得湖南大学控制理论与控制工程博士学位.主要研究方向为智能控制,计算智能和节能优化控制.本文通信作者.E-mail:zhangyj@hnu.edu.cn