A genetic algorithm for community detection in complex networks

Abstract

A new genetic algorithm for community detection in complex networks was proposed. It adopts matrix encoding that enables traditional crossover between individuals. Initial populations are generated using nodes similarity, which enhances the diversity of initial individuals while retaining an acceptable level of accuracy, and improves the efficiency of optimal solution search. Individual crossover is based on the quality of individuals’ genes; all nodes unassigned to any community are grouped into a new community, while ambiguously placed nodes are assigned to the community to which most of their neighbors belong. Individual mutation, which splits a gene into two new genes or randomly fuses it into other genes, is non-uniform. The simplicity and effectiveness of the algorithm are revealed in experimental tests using artificial random networks and real networks. The accuracy of the algorithm is superior to that of some classic algorithms, and is comparable to that of some recent high-precision algorithms.

Keywords

complex networks / community detection / genetic algorithm / matrix encoding / nodes similarity

References

[1] NewmanM E J, GirvanM. Finding and evaluating community structure in networks [J]. Physical Review E, 2004, 69(2): 026113

[2] JinD, LiuJ, YangB, HeD-x, LiuD-you. Genetic algorithm with local search for community detection in large-scale complex networks [J]. Acta Automatic Sinica, 2011, 37(7): 873-882

[3] LiS-z, ChenY-h, DuH-f, FeldmanM W. A genetic algorithm with local search strategy for improved detection of community structure [J]. Complexity, 2010, 15(4): 53-60

[4] LiuX, LiD-y, WangS-l, TaoZ-weiShiY, AlbadaG D V, DongarraJ, SlootP M A. Effective algorithm for detecting community structure in complex networks based on GA and clustering [C]. Computational Science — ICCS 2007 — 7th International Conference, 2007Berlin HeidelbergSpringer657-664

[5] GogA, DumitrescuD, HirsbrunnerB. Community detection in complex networks using collaborative evolutionary algorithms [C]. COSTA F A E, ROCHA L M, COSTA E, HARVEY I, COUTINHO A. Advances in Artificial Life — 9th European Conference, ECAL 2007, 2007Berlin HeidelbergSpringer886-894

[6] TASGIN M, HERDAGDELEN A, BINGOL H. Community detection in complex networks using genetic algorithms [J/OL]. 2007-11-04. http://arxiv.org/PScache/arxiv/pdf/0711/0711.0491v1.pdf.

[7] HeD-x, ZhouX, WangZ, ZhouC-g, WangZ, JinDi. Community mining in complex networks clustering combination based genetic algorithm [J]. Acta Automatica Sinica, 2010, 36(8): 1160-1170

[8] PizzutiC. GA-net: A genetic algorithm for community detection in social networks [C]. RUDOLPH G, JANSEN T, LUCAS S, POLONI C, BEUME N. Parallel Problem Solving from Nature — PPSN X — 10th International Conference, 2008Berlin HeidelbergSpringer1081-1090

[9] PizzutiC. Community detection in social networks with genetic algorithms [C]. KEIJZER M. GECCO’08: Preceedings of 10th Annual Conference on Genetic and Evolutionary Computation 2008, 2008New York, NY, USAACM1137-1138

[10] PizzutiC. A multi-objective genetic algorithm for community detection in networks [C]. ICTAI 2009 — 21st IEEE International Conference on Tools with Artificial Intelligence, 2009Washington DC, USAIEEE Computer Society379-386

[11] ShiC, YanZ-y, WangY, CaiY-n, WuBin. A genetic algorithm for detecting communities in large-scale complex networks [J]. Advances in Complex Systems, 2010, 13(1): 3-17

[12] CaiY-chaoResearch on force aggregation technology in situation assessment [D], 2006ChangshaNational University of Defense Technology, Information System and Management College

[13] LeichtE A, HolmeP, NewmanM E J. Vertex similarity in networks [J]. Physical Review E, 2006, 73(2): 026120

[14] GirvanM, NewmanM 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

[15] NewmanM E J. Fast algorithm for detecting community structure in networks [J]. Physical Review E, 2004, 69(6): 066133

[16] DanonL, Díaz-GuileraA, DuchJ, ArenasA. Comparing community structure identification [J]. Journal of Statistical Mechanics, 2005P09008

[17] RaghavanU N, AlbertR, KumaraS. Near linear time algorithm to detect community structures in large-scale networks [J]. Physical Review E, 2007, 76(3): 036106

[18] NEWMAN M E J. Network data [DB/OL]. 2011-06-14. http://www-personal.umich.edu/~mejn/netdata/.