Identification of multi-resolution network structures with multi-objective immune algorithm

Community structure is one of the most important properties in complex networks, and the field of community detection has received an enormous amount of attention in the past several years. Many quality metrics and methods have been proposed for revealing community structures at multiple resolution levels, while most existing methods need a tunable parameter in their quality metrics to determine the resolution level in advance. In this study, a multi-objective evolutionary algorithm (MOEA) for revealing multi-resolution community structures is proposed. The proposed MOEA-based community detection algorithm aims to find a set of tradeoff solutions which represent network partitions at different resolution levels in a single run. It adopts an efficient multi-objective immune algorithm to simultaneously optimize two contradictory objective functions, Modified Ratio Association and Ratio Cut. The optimization of Modified Ratio Association tends to divide a network into small communities, while the optimization of Ratio Cut tends to divide a network into large communities. The simultaneous optimization of these two contradictory objectives returns a set of tradeoff solutions between the two objectives. Each of these solutions corresponds to a network partition at one resolution level. Experiments on artificial and real-world networks show that the proposed method has the ability to reveal community structures of networks at different resolution levels in a single run.

We present a multi-objective immune algorithm for revealing multi-resolution community structure in networks. The proposed algorithm aims to find a set of tradeoff solutions which represent network partitions at different resolution levels in a single run. It adopts an efficient multi-objective immune algorithm to simultaneously optimize two contradictory objective functions, Modified Ratio Association (MRA) and Ratio Cut (RC). The simultaneous optimization of these two contradictory objectives returns a set of tradeoff solutions between the two objectives. Each of these solutions corresponds to a network partition at one resolution level. This figure shows the results for the Journal network obtained from the proposed algorithm. (a) displays the Pareto front of Journal network. As observed, the proposed algorithm generated 17 solutions (corresponding to variety of resolutions). The solution 2 in (a) splits the network into 2 communities as shown in (b), with physical and chemical journals as a community, and biological and ecological journals as another community; solution 3 divides the network into 3 communities, with ecological and biological journals separated, but physical and chemical journals remain together in the same community (c); in (d), the network is divided into 4 communities correctly by solution 4, with each field journals as one community.Figure optionsDownload as PowerPoint slideHighlights
► We propose a multi-objective evolutionary algorithm for revealing community structure in networks.
► We simultaneously optimize two objective functions, Modified Ratio Association and Ratio Cut.
► The proposed method can find network partitions at different resolution levels in a single run.