Growing neural gas as a memory mechanism of a heuristic to solve a community detection problem in networks

Growing neural gas as a memory mechanism of a heuristic to solve a community detection problem in networks

Author Santos, Camila Pereira Autor UNIFESP Google Scholar
Nascimento, Maria C. V. Autor UNIFESP Google Scholar
Abstract 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. (C) 2016 The Authors. Published by Elsevier B.V.
Keywords Growing Neural Gas
Community Detection In Networks
Heuristic Methods
Language English
Date 2016
Published in Procedia Computer Science. Amsterdam, v. 96, p. 485-494, 2016.
ISSN 1877-0509 (Sherpa/Romeo, impact factor)
Publisher Funpec-Editora
Extent 485-494
Origin https://doi.org/10.1016/j.procs.2016.08.110
Access rights Open access Open Access
Type Conference paper
Web of Science ID WOS:000383252400052
URI http://repositorio.unifesp.br/handle/11600/49398

Show full item record




File

Name: WOS000383252400052.pdf
Size: 229.6Kb
Format: PDF
Description:
Open file

This item appears in the following Collection(s)

Search


Browse

Statistics

My Account