计算机科学 ›› 2015, Vol. 42 ›› Issue (Z6): 57-60.
杨令兴,张喜斌
YANG Ling-xing and ZHANG Xi-bin
摘要: 在将复杂网络的社区结构检测问题建模为单目标优化问题时,采用粒子群算法进行优化。传统粒子群算法用来解决连续优化问题,而社区结构检测问题则是一种基于图的离散优化问题。应用了新的编码策略和粒子更新策略解决这一问题,在更新策略中引入了基于近邻更新的方式,保证了在一定程度上遵循邻域信息引导粒子更新,以符合真实复杂网络的特性。另外,采用拓展的模块度密度函数进行优化,以解决传统模块度密度函数的分辨率限制问题,保证能在不同分辨率发现复杂网络的社区结构。实验结果证明,本算法是有效的,能够检测出不同分辨率下的社区结构。
[1] Roxborough T,Sen A.Graph clustering using multiway ratiocut(Software demonstration)[C]∥Graph Drawing.Springer Berlin Heidelberg,1997:291-296 [2] Angelini L,Boccaletti S,Marinazzo D,et al.Identification of network modules by optimization of ratio association[J].arXiv preprint cond-mat/0610182,2006 [3] Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905 [4] Fortunato S,Barthelemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences,2007,104(1):36-41 [5] Kennedy J,Eberhart R.Particle swarm optimization[C]∥IEEE International Conference on Neural Networks,1995.IEEE,1995,4:1942-1948 [6] Li Zhen-ping,Zhang Shui-hua,Wang Rui-sheng,et al.Quantitative Function for Community Detection[J].Phys.Rev.E,2008,77(3):036109 [7] Kennedy J.The particle swarm:social adaptation of knowledge[C]∥IEEE International Conference on Evolutionary Computation,1997.IEEE,1997:303-308 [8] 陈琳,何嘉.基于模糊聚类的粒子群优化算法[J].西南民族大学学报:自然科学版,2007,33(4):739-742 [9] Gong M,Cai Q,Li Y,et al.An improved memetic algorithm for community detection in complex networks[C]∥2012 IEEE Congress on Evolutionary Computation(CEC).IEEE,2012:1-8 [10] 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,8(1):82-97 [11] Danon L,Diaz-Guilera A,Duch J,et al.Comparing communitystructure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005,2005(9):P09008 [12] Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110 [13] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826 |
No related articles found! |
|