A Memetic Algorithm for Community Detection in Complex Networks

Olivier Gach^{1, 2} and Jin-Kao Hao²

¹LIUM & IUT, Université du Maine, Av. O. Messiaen, 72085, Le Mans, France
olivier.gach@univ-lemans.fr

²LERIA, Université d’Angers, 2 Bd Lavoisier, 49045, Angers Cedex 01, France
hao@info.univ-angers.fr

Abstract. Community detection is an important issue in the field of complex networks. Modularity is the most popular partition-based measure for community detection of networks represented as graphs. We present a hybrid algorithm mixing a dedicated crossover operator and a multi-level local optimization procedure. Experimental evaluations on a set of 11 well-known benchmark graphs show that the proposed algorithm attains easily all the current best solutions and even improves 6 of them in terms of maximum modularity.

Keywords: heuristic, community detection, complex networks, graph partitioning, modularity, combinatorial optimization

LNCS 7492, p. 327 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012