Community Detection Using Dual-Representation Chemical Reaction Optimization

IEEE Trans Cybern. 2017 Dec;47(12):4328-4341. doi: 10.1109/TCYB.2016.2607782. Epub 2016 Sep 23.

Abstract

Many complex networks have been shown to have community structures. Detecting those structures is very important for understanding the organization and function of networks. Because this problem is NP-hard, it is appropriate to resort to evolutionary algorithms. Chemical reaction optimization (CRO) is a novel evolutionary algorithm inspired by the interactions among molecules during chemical reactions. In this paper, we propose a CRO variant named dual-representation CRO (DCRO) to address the community detection problem. DCRO encodes a solution in two representations: one is locus-based and the other is vector-based. The former representation can ensure the validity of a solution and fits for diversification search, and the latter is convenient for intensification search. We thus design two operators for CRO based on these two representations. Their cooperation enables DCRO to achieve a good balance between exploration and exploitation. Experimental results on synthetic and real-life networks show that DCRO can find community structures close to the actual ones and is capable of achieving solutions comparable to several state-of-the-art methods.