A Network Reduction-Based Multiobjective Evolutionary Algorithm for Community Detection in Large-Scale Complex Networks.

Evolutionary algorithms have been demonstrated to be very competitive in the community detection for complex networks. They, however, show poor scalability to large-scale networks due to the exponential increase of search space. In this paper, we suggest a network reduction-based multiobjective evolutionary algorithm for community detection in large-scale networks, where the size of the networks is recursively reduced as the evolution proceeds. In each reduction of the network, the local communities found by the elite individuals in the population are identified as nodes of the reduced network for further evolution, thereby considerably reducing the search space. A local community repairing strategy is also suggested to correct the misidentified nodes after each network reduction during the evolution. Experimental results on synthetic and real-world networks demonstrate the superiority of the proposed algorithm over several state-of-the-art community detection algorithms for large-scale networks, in terms of both computational efficiency and detection performance.

A Mixed Representation-Based Multiobjective Evolutionary Algorithm for Overlapping Community Detection.

Designing multiobjective evolutionary algorithms (MOEAs) for community detection in complex networks has attracted much attention of researchers recently. However, most of the existing methods focus on addressing the task of nonoverlapping community detection, where each node must belong to one and only one community. In fact, communities are often overlapped with each other in many real-world networks, thus it is necessary to design overlapping community detection algorithms. To this end, this paper proposes a mixed representation-based MOEA (MR-MOEA) for overlapping community detection. In MR-MOEA, a mixed individual representation scheme is proposed to fast encode and decode the overlapping divisions of complex networks. Specifically, this mixed representation consists of two parts: one represents all potential overlapping nodes and the other delegates all nonoverlapping nodes. These two parts evolve together to detect the overlapping communities of networks based on different updating strategies suggested in MR-MOEA. We verify the effectiveness of the proposed algorithm MR-MOEA on ten real-world complex networks and the experimental results demonstrate that MR-MOEA is superior over six representative algorithms for overlapping community detection.