Network Community Detection using A Backtracking-based Discrete State Transition Algorithm

摘要

Finding network communities (i.e. community detection) is a famous topic in network science. By far, many widely concerned community detection approaches are designed by using evolutionary computation methods. Recent years, a new evolutionary algorithm called state transition algorithm (STA) was created and developed. In our previous work, a population-based discrete STA (MDSTA) has been put forwarded to settle network community detection task. Similar to most population-based evolutionary algorithms, MDSTA has a relatively complex algorithm structure which may limit the application of the algorithm. To address this problem, a backtracking-based discrete STA (BDSTA) is designed in this study. BDSTA is an individual-based method, and two kinds of substitute operators based on label-based representation strategy and locus-based representation strategy are used in BDSTA for global search and local search, respectively. Owing to that the individual-based algorithms often fall into a stagnation solution, we employ a backtracking search strategy in the global search procedure. Finally, five real-world networks and the extended GN artificial networks are used to test BDSTA and some state-of-art algorithms. Experimental results prove that BDSTA often get high-quality community partitions and it is more efficient than these state-of-art algorithms.