A Genetic Algorithm for Modularity Density Optimization in Community Detection

Many complex systems can be modeled as complex networks, so we can use network theory to study this models. One important feature in networks is community structure, i.e. the organization of nodes in communities, with many edges joining nodes of the same community and comparatively few edges joining nodes of different communities. A large number of community detection algorithms have been proposed in the last decade. Many of these algorithms use modularity as function to optimize. The modularity has been exposed that have resolution limits and contains an intrinsic scale that depends on the total size of edges in the network. Modules smaller than this scale may not be detected even in the extreme case that they are complete graphs connected by single bridges. Recently a new quantitative measure has been proposed for evaluating the partition of a network into communities called modularity density. In this paper we propose a genetic algorithm to optimize this quantitative measure. We use the matrix representation that make it easier to mutate and crossover the individuals. Adjusted Rand Index (ARI) is used for measuring performance of algorithm. The experimental tests using artificial, LFR benchmark and real world networks with known community structure, revealed the effectiveness of the algorithm.