Memetic algorithm with simulated annealing strategy and tightness greedy optimization for community detection in networks

• A Memetic algorithm (MA-SAT) is proposed for community detection in networks.
• Simulated annealing (SA) and tightness greedy optimization (TGO) are used.
• TGO is designed to improve diversity, increasing little computation cost.
• The balance between SA strategy and genetic algorithm is analyzed.
• The abundant results show that the MA-SAT is very efficient and competitive.

Community structure is one of the most important properties in complex networks, and the problem of community detection in the networks has been investigated extensively in recent years. In this paper, a Memetic algorithm (MA) based on genetic algorithm with two different local search strategies is proposed to maximize the modularity density, and a more general version of the objective function is used with a tunable parameter λ which can resolve the resolution limit. One local search strategy is simulated annealing (SA), and the other one is tightness greedy optimization (TGO). SA is employed to find individuals with higher modularity density, which helps to enhance the convergence speed of the MA and avoid being trapped into local optima. TGO adopts the local tightness function which makes full use of local structural information to generate neighbor partition, which increases very little computation cost and benefits the diversity of the population of MA. Experiments on the computer-generated networks, LFR Benchmark networks, and real-world networks show that compared with several state-of-the-art methods, our algorithm (named as MA-SAT) is very efficient and competitive.

Figure optionsDownload as PowerPoint slide