分解多目标优化揭示复杂网络社区层次结构

doi:10.3969/j.issn.1001-2400.2013.03.031

Abstract

Abstract:

A new algorithm for community detection of complex networks is proposed. The problem of community detection is considered as multi-objective optimization problem. Tradeoff among multi-objectives realizes the detection of the community structure in a wider spread space, the disadvantages of the traditional single optimization algorithm is overcome. The MOEA/D framework is adopted and the Tchebycheff decomposition technique is used. A simulated annealing based weighted-sum method is used to perform local search which can expand the search scope, and not easily fall into local optimal solution. Finally, simulation experiments are done to test the algorithm using artificial and reality networks. The results show that, compared with existing algorithms, the algorithm has a higher detection accuracy and a small amount of computation, and can reveal the hierarchy community structure of the complex network by Pareto optimal solutions.

Key words: complex networks, community detection, multi objective optimization, hierarchy structure

CLC Number:

TP393

CHEN Guoqiang;WANG Yuping. Revealing of the hierarchy community of the complex network by decomposition multi-objective optimization[J].J4, 2013, 40(3): 205-211.

References

［1］ Papadopoulos S, Kompatsiaris Y, Vakali A, et al. Community Detection in Social Media Performance and Application Considerations［J］. Data Mining and Knowledge Discovery, 2012, 24(3): 515-554.
［2］ Girvan M, Newman M E J. Community Structure in Social and Biological Networks［J］. Proc Natl Acad Sci, 2002, 99(12): 7821-7826.
［3］ Wu Jianshe, Jiao Licheng, Jin Chao, et al. Overlapping Community Detection Via Network Dynamics［J］. Physical Review E, 2012, 85(1): 016115-1-016115-7.
［4］付立冬, 高琳. 特征向量的核方法检测网络社团结构［J］. 西安电子科技大学学报, 2012, 39(2): 207-214.
Fu Lidong, Gao Lin. Kernel K-means Clustering Algorithm for Detecting Communities in Complex Networks Based on Eigenvector［J］. Journal of Xidian University, 2012, 39(2): 207-214.
［5］ Psorakis I, Roberts S, Ebden M. Overlapping Community Detection Using Bayesian Non-negative Matrix Factorization［J］. Physical Review E, 2011, 83(6): 066114-1-066114-9.
［6］ Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks［J］. Phys Rev E, 2004, 69(2): 026113-1-026113-15.
［7］ Fortunato S, Barthélemy M. Resolution Limit in Community Detection［J］. Proc Natl Acad Sci, 2007,104(1): 36-41.
［8］ Li Z P, Zhang S H, Wang R S, et al. Quantitative Function for Community Detection［J］. Phys Rev E, 2008, 77(3): 036106-1-036106-9.
［9］ Chen Guoqiang, Wang Yuping. Community Detection in Complex Networks Using Immune Clone Selection Algorithm［J］. International Journal of Digital Content Technology and Its Applications, 2011, 5(6): 182-189.
［10］ Maoguo Gong, Bao Fu, Licheng Jiao, et al. Memetic Algorithm for Community Detection in Networks［J］. Physical Review E, 2011, 84(4): 056101-1-056101-9.
［11］陈国强, 王宇平. 基于极值优化模块密度的复杂网络社区检测［J］. 华中科技大学学报(自然科学版), 2011, 39(4): 82-85.
Chen Guoqiang, Wang Yuping. Community Detection in Complex Networks Using Extremal Optimization Modularity Density［J］. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2011, 39(4): 82-85.
［12］ Shi Chuan, Zhong Cha, Yan Zhenyu, et al. A Multi-objective Approach for Community Detection in Complex Network［C］//2010 IEEE Congress on Evolutionary Computation. Barcelona: IEEE, 2010: 18-23.
［13］ Pizzuti C. A Multi-objective Genetic Algorithm for Community Detection in Networks［C］//2009 21st IEEE International Conference on Tools with Artificial Intelligence. New Jersey: IEEE, 2009: 379-386.
［14］ Martin R, Carl T B. An Information-theoretic Framework for Resolving Community Structure in Complex Networks［J］. Proc Natl Acad Sci, 2007, 104(18): 7327-7331.
［15］ Zhang Qingfu, Li Hui. Moea/D: a Multiobjective Evolutionary Algorithm Based on Decomposition［J］. IEEE Trans on Evolutionary Computation, 2007, 11(6): 712-731.
［16］ Lancichinetti A, Fortunato S, Radicchi F. Benchmark Graphs for Testing Community Detection Algorithms［J］. Physical Review E, 2008, 78(4): 046110-1-046110-5.
［17］ Danon L, Díaz-Guilera A, Duch J, et al. Comparing Community Structure Identification［J］. Journal of Statistical Mechanics, 2005, 2005(9): 09008-1-09008-7.
［18］ Zachary W W. An Information Flow Model for Conflict and Fission in Small Groups［J］. Journal of Anthropological Research, 1977, 33(4): 452-473.
［19］ Lusseau D. The Emergent Properties of Dolphin Social Network［J］. Biology Letters, Proc R Soc, 2003, 270(S2): S186-S188.
［20］ Newman N E J. Modularity and Community Structure in Networks［J］. Proc Natl Acad Sci, 2006,103(3): 8577-8582.

[1]	ZHANG Shubo,REN Shuxia,WU Tao. Improved spectral clustering community detection algorithm by combining the probability matrix [J]. Journal of Xidian University, 2019, 46(3): 167-172.
[2]	WANG Yu;GAO Lin. Discovering communities in dynamic networks: a bridgeness incremental clustering algorithm [J]. J4, 2013, 40(1): 30-35.
[3]	FU Li-dong;GAO Lin. Spectral approach to finding communities in networks based on the modularity density [J]. J4, 2010, 37(5): 916-920+965.

Revealing of the hierarchy community of the complex network by decomposition multi-objective optimization

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Metrics

Comments

Recommended 0