An Effective Community Detection Method Based on Improved Genetic Algorithm

Abstract:

Detecting community structure from complex networks has triggered considerable attention in several application domains. This paper proposes a new community detection method based on improved genetic algorithm (named CDIGA), which tries to find the best community structure by maximizing the network modularity. String encoding is used to realize genetic representation. Parts of nodes assign their community identifiers to all of their neighbors to ensure the convergence of the algorithm and eliminate unnecessary iterations when initial population is created. Crossover operator and mutation operator are improved too, one-way crossover strategy is introduced to crossover process, the Connect validity of mutation node is ensured in mutation process. We compared it with three other algorithms in computer generated networks and real world networks, Experiment Results show that the improved algorithm is highly effective for discovering community structure.

• Periodical: Applied Mechanics and Materials (Volumes 568-570)
• Pages: 852-857
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.568-570.852
• Online since: June 2014
• Authors: Lu Wang, Yong Quan Liang*, Qi Jia Tian, Jie Yang, Chao Song, Zhuang Wu
• Keywords: Community Detection, Complex Network, Genetic Algorithm (GA), Modularity, Normalized Mutual Information

References

[1] S.N. Dorogovtsev, J. F. F. Mendes, Evolution of networks, Advances in Physics, 6th March (2001).

[2] M. Girvan, M.E.J. Newman, Community structure in social and biological networks, PNAS, vol. 99, no. 12, pp.7821-7826, (2002).

[3] Gulbahce, N. and S. Lehmann, The art of community detection. Bioessays, 2008. 30(10): 934-938.

DOI: 10.1002/bies.20820

[4] Palla. G, et al, Uncovering the overlapping community structure of complex networks in nature and society, Nature, 2005. 435(7043): 814-818.

DOI: 10.1038/nature03607

[5] Capocci, A., V.D.P. Servedio, et al, Detecting communities in large networks, Statistical Mechanics and its Applications, 2005. 352(2-4): pp.669-676.

DOI: 10.1016/j.physa.2004.12.050

[6] Newman M E J, Girvan M, Finding and evaluating community structure in networks, Physical Review E, 2004, 69(2): 026113.

[7] Tasgin M, Herdagdelen A, Bingol H, Community detection in complex networks using genetic algorithms [Online], avail- able: http: /arxiv. org/abs/0711. 0491, January 8, (2010).

[8] A. Lancichinetti, S. Fortunato, and F. Radicchi, New benchmark in community detection, arXiv: 0805. 4770v2 [physics. soc-ph] [Online]. Available: http: /arxiv. org/pdf/0805. 4770v2.

[9] N. Matake, T. Hiroyasu, M. Miki, and T. Senda, Multiobjective clustering with automatic k-determination for large-scale data, in Proc. Int. GECCO, 2007, p.861–868.

DOI: 10.1145/1276958.1277126

[10] Zachary W W, An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(1): 452–473.

DOI: 10.1086/jar.33.4.3629752

[11] Lusseau D, The emergent properties of a dolphin social network. Proceedings of the Royal Society B: Biological Sciences, 2003, 270(Supplement 2): S186-S188.

[12] 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.

DOI: 10.1073/pnas.122653799