A Multi-objective Community Detection Algorithm with a Learning-Based Strategy

Abstract

Abstract Community detection is a fundamental task in network analysis in that it can express the characteristics of individual behaviors and the relationships between individuals in complex networks, thus revealing the functional and structural properties of various networks. However, as networks become larger and larger, how to quickly and accurately detect the community structure of large-scale networks has become a huge challenge nowadays. In this paper, an efficient algorithm, called Local Search for Community Detection (LSCD), is proposed to solve the multi-objective community detection problem. In the algorithm, an iterated local search is performed to search for non-dominated solutions in the solution space. To search for higher quality non-dominated solutions, this paper employs a learning-based strategy to select nodes in each round of the search. The strategy learns from the historical movement of the nodes and changes their selection probability according to their importance. Moreover, to search the entire solution space, this paper proposes a local search strategy that restricts one objective with a bound for a certain round, as well as an adaptive bound update mechanism. Experimental results on synthetic and real-world networks show that the proposed algorithm outperforms several state-of-the-art algorithms in terms of multi-objective optimization performance and accuracy in detecting the community structure of complex networks, since it performs best on 44 instances out of 46 in terms of Modularity (Q) and 29 out of 39 in terms of Normalized Mutual Information (NMI). In addition, the results show that the proposed algorithm has a good ability to handle large-scale networks.

Keywords

• Local search
• Community detection
• Multi-objective optimization
• Clustering