基于单目标PSO的社区检测算法

计算机科学 ›› 2015, Vol. 42 ›› Issue (Z6): 57-60.

基于单目标PSO的社区检测算法

杨令兴,张喜斌

空军工程大学航空航天工程学院西安710038,空军工程大学航空航天工程学院西安710038

出版日期:2018-11-14 发布日期:2018-11-14

Community Detection Algorithm Based on Single Objective PSO

YANG Ling-xing and ZHANG Xi-bin

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 在将复杂网络的社区结构检测问题建模为单目标优化问题时,采用粒子群算法进行优化。传统粒子群算法用来解决连续优化问题,而社区结构检测问题则是一种基于图的离散优化问题。应用了新的编码策略和粒子更新策略解决这一问题,在更新策略中引入了基于近邻更新的方式,保证了在一定程度上遵循邻域信息引导粒子更新,以符合真实复杂网络的特性。另外,采用拓展的模块度密度函数进行优化,以解决传统模块度密度函数的分辨率限制问题,保证能在不同分辨率发现复杂网络的社区结构。实验结果证明,本算法是有效的,能够检测出不同分辨率下的社区结构。

Abstract: The community detection problem is modeled as single objective optimization problem,and the PSO algorithm is adopted to solve it.The traditional PSO algorithms are used to handle with continuous optimal problems,while the community detection problem is a graph based on discrete optimal problem in our paper.In this case,a new coding scheme and particles updating scheme were used to overcome this shortcoming.Besides that,a neighbor based strategy was adopted in the updating scheme to confirm that the neighborhood information can guide their updating which is con-sistent with the property of the real world complex networks.Besides,the general modularity density function is taken as the objective function to overcome the resolution problem,which confirms proposed algorithm can detect the construction of community under different resolutions.Experimental results indicate that this algorithm is effective and can detect the community construction of different resolutions.

Key words: Complex networks,Community detection,Modularity density function,PSO algorithm,Single objective

杨令兴,张喜斌. 基于单目标PSO的社区检测算法[J]. 计算机科学, 2015, 42(Z6): 57-60. https://doi.org/

YANG Ling-xing and ZHANG Xi-bin. Community Detection Algorithm Based on Single Objective PSO[J]. Computer Science, 2015, 42(Z6): 57-60. https://doi.org/

参考文献

[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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed