|本期目录/Table of Contents|

[1]李佩茜,冯少荣*.一种高效的基于教与学的社区发现算法[J].厦门大学学报(自然科学版),2018,57(01):104-111.[doi:10.6043/j.issn.0438-0479.201703040]
 LI Peixi,FENG Shaorong*.An Efficient Multi-population Community Detection Algorithm Using Teaching-learning-based Optimization[J].Journal of Xiamen University(Natural Science),2018,57(01):104-111.[doi:10.6043/j.issn.0438-0479.201703040]
点击复制

一种高效的基于教与学的社区发现算法(PDF/HTML)
分享到:

《厦门大学学报(自然科学版)》[ISSN:0438-0479/CN:35-1070/N]

卷:
57卷
期数:
2018年01期
页码:
104-111
栏目:
研究论文
出版日期:
2018-01-26

文章信息/Info

Title:
An Efficient Multi-population Community Detection Algorithm Using Teaching-learning-based Optimization
文章编号:
0438-0479(2018)01-0104-08
作者:
李佩茜冯少荣*
厦门大学信息科学与技术学院,福建 厦门 361005
Author(s):
LI PeixiFENG Shaorong*
School of Information Science and Engineering,Xiamen University,Xiamen 361005,China
关键词:
社区发现 教与学 多目标 多种群进化算法
Keywords:
community detection teaching-learning multi-objective multi-population evolutionary algorithm
分类号:
TP 181
DOI:
10.6043/j.issn.0438-0479.201703040
文献标志码:
A
摘要:
社区结构是复杂网络的重要特征,社区发现就是为了挖掘复杂网络中的社区结构.为了提高基于教与学的多目标社区发现算法(MODTLBO/D)的准确率,降低时间复杂度,提出了一种在多种群进化策略下的MODTLBO/D(E-MODTLBO/D).在E-MODTLBO/D中,采用自适应学习因子加强在教学阶段的探索与搜索能力; 在学习阶段,每个个体在各自的子种群内采用随机学习策略或者是改进的量子行为学习策略.在每次迭代更新后,子种群间进行信息交流,维持算法的多样性与避免早熟收敛.实验表明,E-MODTLBO/D在时间复杂度与发现高质量的社区结构方面要优于MODTLBO/D等一些经典社区发现算法.
Abstract:
Community structure is an important feature of complex networks,and community detection aims at mining the community structure of complex networks.In order to improve the multi-objective optimization of community detection using discrete tea-ching-learning-based optimization with decomposition(MODTLBO/D),and decrease time complexity,we propose an efficient tea-ching-learning-based optimization algorithm combined with multi-population evolutionary strategy for community detection.In this study,we adopt adaptive learning factor in teacher phase to enhance the ability of exploration and search.In learner phase,each learner employs the random learning strategy or modified quantum-behaved learning strategy in corresponding subpopulation.After each generation,subpopulations exchange information to maintain the diversity and discourage premature convergence.The experiments results demonstrate that our proposed algorithm has an advantage of time complexity and is highly efficient at discovering quality community structure.

参考文献/References:

[1] NEWMAN M E J,GIRVAN M M.Finding and evaluating community structure in networks[J].Phys Rev E,2004,69(2):99-106.
[2] NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Phys Rev E,2004,69(6):066133.
[3] RAO R V,SAVSANI V J,VAKHARIA D P.Teaching-learning-based optimization:an optimization method for continuous non-linear large scale problems[J].Information Sciences,2012,183(1):1-15.
[4] YU K,WANG X,WANG Z.Constrained optimization based on improved teaching-learning-based optimization algorithm[J].Information Sciences,2016,352/353:61-78.
[5] GHASEMI M,GHAVIDEL S,GITIZADEH M,et al.An improved teaching-learning-based optimization algorithm using Levy mutation strategy for non-smooth strategy for non-smooth power flow[J].International Journal of Electrical Power& Energy Systems,2015,65:375-384.
[6] BASU M.Teaching-learning-based optimization algorithm for multi-area economic dispatch[J].Energy,2014,68:21-28.
[7] PATEL V K,SAVSANI V J.A multi-objective improved teaching-learning-based optimization algorithm(MO-ITLBO)[J].Information Sciences,2014,357:182-200.
[8] KEESARI H S,RAO R V.Optimization of job shop scheduling problems using teaching-learning-based optimization algorithm[J].Opsearch,2013,51(4):545-561.
[9] XIA K,GAO L,LI W D,et al.Disassembly sequence planning using a simplified teaching-learning-based optimization algorithm[J].Advanced Engineering Informatics,2014,28:518-527.
[10] BAYKASOGLU A,HAMZADAYI A,KOSE S Y.Testing the performance of teaching-learning-based optimization(TLBO)algorithm on combinatorial problems:Flow shop and job shop scheduling cases[J].Information Sciences,2014,276(C):204-218.
[11] DEDE T.Application of teaching-learning-based-optimization algorithm for the discrete optimization of truss structures[J].Ksce Journal of Civil Engineering,2014,18(6):1759-1767.
[12] LI J,PAN Q,MAO K.A discrete teaching-learning-based optimization algorithm for realistic flow shop rescheduling problems[J].Engineering Applications of Artificial Intelligence,2015,37:279-292.
[13] CHEN D,ZOU F,LU R Q,et al.Multi-objective optimization of community detection using discrete teaching-learning-based optimization & with decomposition[J].Information Sciences,2016,369:402-418.
[14] EZHILARASI G A,SWARUP K S.Network decomposition using Kernighan-Lin strategy aided harmony search algorithm[J].Swarm & Evolutionary Computation,2012(7):1-6.
[15] POTHEN A,SIMON H,LIOU K P.Partitioning sparse matrices with eigenvectors of graphs[J].Siam Journal on Matrix Analysis & Applications,1990,11(3):430-452.
[16] FIEDLER M.A property of eigenvectors of non-negative symmetric matrices and its applications to graph theory[J].Czechoslovak Mathematical Journal,1975,25:619-637.
[17] WEI Y C,CHENG C K.Ration cut partitioning for hie-rarchical designs[J].IEEE Transactions on Computer-Aided Design,1991,10(7):911-921.
[18] HE L,ZHANG H.Iterative ensemble normalized cuts[J].Pattern Recognition,2015,52:274-286.
[19] ZHANG X,FEI S,SONG C,et al.Label propagation algorithm based on local cycles for community detection[J].International Journal of Modern Physics B,2015,29(5):1550029.
[20] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[21] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(2):066111.
[22] BLONDEL V D,GUILAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,10:P10008.
[23] CRUZ J D,BOTHOREL C,POULET F.Entropy based community detection in augmented social networks[C]∥International Conference on Computational aspects of Social Networks.Salamanca:IEEE,2011:163-168.
[24] HASSAN E A,HAFEZ A I,HASSANIEN A E,et al.Community detection algorithm based on artificial fish swarm optimization[J].Advances in Intelligent Systems & Computing,2014,323:509-521.
[25] KARIMI-MAID A M,FATHIAN M,AMIRI B.A hybrid artificial immune network for detecting communities in complex networks[J].Computing,2015,97(5):483-507.
[26] LI Y,LIU J,LIU C.A comparative analysis of evolutio-nary and memetic algorithms for community detection from signed social networks[J].Soft Computing,2014,18(2):329-348.
[27] LI Z,LIU J.A multi-agent genetic algorithm for community detection in complex networks[J].Physica A Statistical Mechanics & Its Applications,2016,449:336-347.
[28] SHI C,YAN Z,CAI Y,et al.Multi-objective community detection in complex networks[J].Applied Soft Computing,2012,12(2):850-859.
[29] PIZZUTI C.A multi-objective genetic algorithm to find communities in complex networks[J].IEEE Transactions on Evolutionary Computation,2012,6(3):418-430.
[30] GONG M G,MA L,ZHANG Q F,et al.Community detection in networks by using multi-objective evolutionary algorithm with decomposition[J].Physica A Statistical Mechanics & Its Application,2012,391:4050-4060.
[31] GONG M G,CAI Q,CHEN X,et al.Complex network clustering by multi-objective discrete particle swarm optimization based on decomposition[J].IEEE Transactions on Evolutionary Computation,2014,18(1):82-97.
[32] AMIRI B,HOSSAIN L,CRAWFORD J W,et al.Community detection in complex networks:multi-objective enhanced firefly algorithm[J].Knowledge-Based Systems,2013,46:1-11.
[33] CAI Q,GONG M G,MA L,et al.Greedy discrete particle swarm optimization for large-scale social network clustering[J].Information Sciences,2015,316(41):503-516.
[34] LIU C,LIU J,JIANG Z.A multi-objective evolutionary algorithm based on similarity for community detection from signed social networks[J].IEEE Transactions on Cybernetics,2014,44(12):2274-2287.
[35] ZHAO Y,LI S,JIN F.Overlapping community detection in complex networks using multi-objective evolutionary algorithm[J].Computational & Applied Mathematics,2015,36(1):1-20.
[36] ZHOU X,LIU Y,LI B,et al.Multi-objective biogeography based optimization algorithm with decomposition for community detection in dynamic networks[J].Physica A:Statistical Mechanics & Its Applications,2015,436:430-442.
[37] RADICCHI F,CASTELLANO,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.
[38] DANON L,DAZ-GUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics Theory & Experiment,2005,78:P09008.
[39] KENNEDY J,EBERHART R C.A discrete binary version of the particle swarm algorithm[J].Computational Cybernetics and Simulation,1997,5:4104-4108.
[40] GONG M G,CAI Q,LI Y,et al.An improved memetic algorithm for community detection in complex networks[C]∥2012 IEEE Congress on Evolutionary Computation.Brisbane:IEEE,2012:1-8.
[41] YUE Z,GAO Y.An improved teaching-learning-based optimization algorithm[J].Journal of Lanzhou University of Technology,2015,41(6):99-103.
[42] ZOU F,WANG L,HEI X,et al.Teaching-learning-based optimization with dynamic group strategy for global optimization[J].Information Sciences,2014,273:112-131.
[43] ZHANG Q F,LI H.MOEA/D:a multi-objective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Compution,2017,11(6):712-731.
[44] ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1997,33(4):452-473.
[45] LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[46] NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Science,2006,103(23):8577-8582.
[47] ROSINC C,BELEW R,MORRIS G,et al.New methods for competitive co-evolution[J].Evolutionary Computation,1997,5(1):1-29.

备注/Memo

备注/Memo:
收稿日期:2017-03-22 录用日期:2017-11-30
基金项目:国家社会科学基金重大项目(13&ZD148)
*通信作者:shaorong@xmu.edu.cn
更新日期/Last Update: 1900-01-01