Growing Neural Gas as a Memory Mechanism of a Heuristic to Solve a Community Detection Problem in Networks

Iterative heuristics are commonly used to address combinatorial optimization problems. However, to meet both robustness and efficiency with these methods when their iterations are independent, it is necessary to consider a high number of iterations or to include local search-based strategies in them. Both approaches are very time-consuming and, consequently, not efficient for medium and large-scale instances of combinatorial optimization problems. In particular, the community detection problem in networks is well-known due to the instances with hundreds to thousands of vertices. In the literature, the heuristics to detect communities in networks that use a local search are those that achieve the partitions with the best solution values. Nevertheless, they are not suitable to tackle medium to large scale networks. This paper presents an adaptive heuristic, named GNGClus, that uses the neural network Growing Neural Gas to play the role of memory mechanism. The computational experiment with LFR networks indicates that the proposed strategy significantly outperformed the same solution method with no memory mechanism. In addition, GNGClus was very competitive with a version of the heuristic that employs an elite set of solutions to guide the solution search.