Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks

Abstract

In order to further improve the performance of current genetic algorithms aiming at discovering communities, a local search based genetic algorithm GALS is here proposed. The core of GALS is a local search based mutation technique. In order to overcome the drawbacks of traditional mutation methods, the paper develops the concept of marginal gene and then the local monotonicity of modularity function Q is deduced from each nodes local view. Based on these two elements, a new mutation method combined with a local search strategy is presented. GALS has been evaluated on both synthetic benchmarks and several real networks, and compared with some presently competing algorithms. Experimental results show that GALS is highly effective and efficient for discovering community structure.

17 pages, 8 figures. arXiv admin note: text overlap with arXiv:1303.4711

References in corpus (22)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Functional cartography of complex metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Self-similar community structure in organisations
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• A Local Method for Detecting Communities
• Community Detection in Complex Networks Using Genetic Algorithms
• Multiresolution community detection for megascale networks by information-based replica correlations
• Maximizing Modularity is hard
• Genetic Algorithm with Ensemble Learning for Detecting Community Structure in Complex Networks