A Reduced Mixed Representation Based Multi-Objective Evolutionary Algorithm for Large-Scale Overlapping Community Detection

In recent years, the application of multi-objective evolutionary algorithms (MOEAs) to overlapping community detection in complex networks has been a hot research topic. However, the existing MOEAs for detecting overlapping communities show poor scalability to large-scale networks due to the fact that the encoding length of individuals is usually equal to the number of all nodes in the network. To this end, we suggest a reduced mixed representation based multi-objective evolutionary algorithm named RMR-MOEA for large-scale overlapping community detection, where the length of the individual is recursively reduced as the evolution proceeds. Specifically, a mixed representation is adopted for fast encoding and decoding the individual in the population, which consists of two parts: one represents all potential overlapping nodes and the other represents all non-overlapping nodes. Then, in each individual length reduction, two strategies are suggested to respectively shorten the length of each part in the mixed representation, with the aim to greatly reduce the search space. Finally, the experimental results on 10 real-world complex networks demonstrate the effectiveness of the proposed RMR-MOEA in terms of both detection performance and running time, especially on large-scale networks.