A novel modularity-based discrete state transition algorithm for community detection in networks

Complex network analysis is a hot topic in the data mining area which aims to reveal the hidden information behind a network. As an important tool in complex network analysis, community detection tries to perform a network clustering operation to find the community structure, which can be formulated as an optimization problem. In the past few decades, various of community detection algorithms have been designed to address this challenging problem. Although many algorithms are feasible to detect the network partitions, most of them only get suboptimal solutions or have poor stability. The state transition algorithm (STA) is a novel intelligent paradigm for global optimization, and it exhibits powerful global search ability in various complex optimization problems. Thus, in this paper, a novel modularity-based discrete state transition algorithm (MDSTA) is proposed to obtain more optimal and stable solutions. Moreover, based on the heuristic information of the network, vertex substitute transformation operator and community substitute transformation operator are proposed for global search. Then, each initialized individual evolves through these two substitute operations. Next, an elite population that contains individuals with high fitness values is selected from these evolved individuals. Finally, a two-way crossover operation among the elite population is conducted for local search. The framework of MDSTA is pretty simple and easy to implement. Several state-of-art community detection algorithms are used to compare with MDSTA both on artificial networks and real-world networks. The experimental results demonstrate that MDSTA is effective and stable for community detection in networks. (C) 2019 Elsevier B.V. All rights reserved.