A multi-objective ant colony optimization with decomposition for community detection in complex networks

Abstract

Community detection in complex networks plays an important role in mining and analyzing the structure and function of networks. However, traditional algorithms for community detection-based graph partition and hierarchical clustering usually have to face expensive computational costs or require some specific conditions when dealing with complex networks. Recently, community detection based on intelligent optimization attracts more and more attention because of its good effectiveness. In this paper, a new multi-objective ant colony optimization with decomposition (MACOD) for community detection in complex networks is proposed. Firstly, a new framework of multi-objective ant colony algorithm specialized initially for the complex network clustering is developed, in which two-objective optimization problem can be decomposed into a series of subproblems and each ant is responsible for one single objective subproblem and it targets a particular point in the Pareto front. Secondly, a problem-specific individual encoding strategy based on graph is proposed. Moreover, a new efficient local search mechanism is designed in order to improve the stability of the algorithm. The proposed MACOD has been compared with four other state of the art algorithms on two benchmark networks and seven real-world networks including three large-scale networks. Experimental results show that MACOD performs competitively for the community detection problems.

Keywords

Community detection decomposition multi-objective optimization ant colony

Introduction

In recent years, complex networks have received more and more attention (Newman, 2003; Zhang et al., 2013). In the view of network theory, the complexity of a network is mainly due to the complexity of the relationships between nodes. A complex network generally has the following features: Firstly, the small-world property, which means that the average path length of the network grows no faster than logarithmically with network size, although most of the large-scale networks are complex. Secondly, the degree distribution of most real-world networks follows heavy-tailed degree distributions. Thirdly, many real-world networks have high clustering coefficients, which indicates high transitivity in interaction. Finally, many real-world networks exhibit community structure, which means that the network can be decomposed into subnetworks with dense intra-connections and sparse inter-connections.

Community structure is an important property of complex networks. Research on the community structure can help us understand and analyze the complex networks. The detection of the community structure can also be called community detection. In past years, a large number of community detection algorithms have been put forward. KL algorithm, proposed by Kernighan and Lin (1970), is a greedy optimization method that assigns a benefit function Q to divisions of the network and then attempts to optimize the benefit function over possible divisions. However, the sizes of communities must be specified in advance. Girvan and Newman (2002) proposed a method that is hereinafter denoted by the GN algorithm. It uses centrality indices to find community boundaries and information from edge betweeness to detect community peripheries. Newman (2004) put forward the modularity Q to optimize an objective function for community detection. Halalai et al. (2010) developed a distributed approach for the community detection problem using a genetic algorithm that employed specialized variation operators (uniform crossover and repaired mutation). Moreover, a composite fitness function that handles the performance/efficiency tradeoff is designed in this approach. A memetic algorithm for community detection was developed by Gong et al. (2011). It adopts the modularity density as an objective function with a tunable parameter that allows one to explore the network at different resolutions. This algorithm is a synergy of a genetic algorithm with a hill-climbing strategy as the local search procedure. MOEA/D-net (Gong et al., 2012) maximizes the density of internal degrees and minimizes the density of external degrees simultaneously underlying framework MOEA/D (Zhang and Li, 2007). It produces a set of solutions that can represent various divisions to the networks at different hierarchical levels. Shang et al. (2013) proposed a community detection method based on the modularity and an improved genetic algorithm (GA-net) that uses the simulated annealing method as the local search method with the number of community structures as the prior information. Chang et al. (2013) proposed an ant colony optimization (ACO) to solve the community detection problem by just maximizing one objective function, namely the modularity measure. This algorithm adopts the scheme of max-min ant system, and a new kind of heuristic based on the correlation between nodes. Inspired by this algorithm, MOEA/D-ACO proposed by Ke et al. (2013) combined ACO and the multiobjective evolutionary algorithm (EA) based on decomposition (MOEA/D). A discrete framework of the particle swarm optimization algorithm (MODPSO) (Gong et al., 2014) was proposed to deal with community detection problem. Also, it adopts a decomposition mechanism (Eichfelder, 2014) and a problem-specific population initialization method based on label propagation. This algorithm not only can deal with undirected networks, but also the signed network.

As mentioned above, many bio-inspired algorithms including genetic algorithm and particle swarm optimization are applied to community detection in networks, and can obtain good results. As a swarm intelligence algorithm, ACO, such as ACO algorithm (Chang et al., 2013), is also used to deal with community detection problems, which can improve the modularity value as well as successfully detect the community structure. Moreover, MOEAD-net based on multi-objective optimization obtains better results in solving community detection problems, compared with those existing algorithms based on single optimization criteria. Inspired by these ideas, we propose an ACO based on multi-objective optimization to solve community detection problems in this paper, namely a multi-objective ant colony optimization based on decomposition (denoted as MACOD). Firstly, the decomposition method (Zhang and Li, 2007) is adopted to optimize two contradictory objective functions, namely, negative ratio association and ratio cut (Chang et al., 2013) to realize effective community detection. In the proposed MACOD, a multi-objective problem is firstly decomposed into a series of single objective problems. Each ant is encoded to the form of a locus-based adjacency representation and responsible for dealing with one subproblem. All of the ants are divided into several groups, and ants in the same cluster use the same pheromone matrix, and each cluster can get one optimal solution in each generation owing to the decomposition strategy. The pheromone matrix of each cluster is updated by its optimal solution in each generation. In order to avoid too big or too small pheromone values that can lead to the stagnation of the search, the scope of the pheromone values is limited and a heuristic pheromone matrix is constructed by using the correlation between nodes in the network. All ants in the population share the heuristic pheromone matrix. In order to improve the stability of the algorithm, a new efficient local search strategy is also proposed.

The structure of this paper is organized as follows. In Section 2, we introduce the related background knowledge, including some definitions in the community detection problem and concepts used in the multi-objective optimization problems, and so forth. Section 3 describes the proposed MACOD in detail. In Section 4, the proposed MACOD will be compared with other four algorithms on two benchmark networks and seven real-world networks, and its performance will be analyzed. Section 5 concludes this paper.

Related background

Some definitions in the community detection problems

Generally, a network N can be expressed as a graph $G = (V, E)$ , where V is a set of nodes (or vertices), and E is a set of connection edges between nodes. The community detection can be converted to a graph partition problem, in which a graph is divided into non-overlapping sub-graph problem. In this way, a sub-graph represents a community, and the connection between nodes is relatively tight in the same community and nevertheless, relatively sparse between communities. The graph G with n nodes can be represented as an adjacency matrix A with the size of n×n, each element $A_{ij}$ of A is 1 if there is an edge between node i and node j, and otherwise $A_{ij} = 0$ . The degree of node is defined as the number of nodes connected with this node.

The degree $k_{i}$ of node i is defined as follows

k_{i} = \sum_{j = 1}^{n} A_{ij}, j \in V

(1)

If the node i belongs to a sub-graph $S \subset G$ , the degree of i can be represented as

k_{i} (S) = k_{i}^{in} (S) + k_{i}^{out} (S)

(2)

where $k_{i}^{in} (S) = \sum_{j \in S} A_{ij}$ is the number of nodes in S that connect with node i, and $k_{i}^{out} (S) = \sum_{j \notin S} A_{ij}$ is the number of nodes in $G - S$ that connect with node i.

For $\forall i \in S$ , if $k_{i}^{in} (S) > k_{i}^{out} (S)$ , the sub-graph S has a strong community structure, and a community has a weak community structure if $\sum_{i \in S} k_{i}^{in} (S) > \sum_{i \in S} k_{i}^{out} (S)$ . This means that, in a strong community, each node has more connections within the community than with the others in the graph, and in a weak community, the sum of the degrees with the sub-graph is larger than the sum of degrees towards the others in the graph.

Concepts in multi-objective optimization

A multi-objective optimization problem (MOP) can be stated as follows

Minimize F (x) = (f_{1} (x), \dots, f_{m} (x))

(3)

subject to $x \in Ω$ , where $Ω$ is the decision (variable) space, $F : Ω \to R^{m}$ consists of m real-valued objective functions and $R^{m}$ is called the objective space.

For the minimization optimization problem, it is said that a decision vector $u \in Ω$ dominates another vector $v \in Ω$ ( $u ≻ v$ ) if and only if, for $\forall i = 1, 2, \dots, m$ , $f_{i} (u) ⩽ f_{i} (v)$ and $\exists j \in {1, 2, \dots, m}$ , $f_{i} (u) < f_{i} (v)$ .

We say that a decision vector $x^{*} \in Ω$ is a Pareto-optimal if there is no $x \in Ω$ so that $F (x) ≻ F (x^{*})$ . $F (x^{*})$ is called a Pareto-optimal objective vector.

The Pareto-optimal set (PS) consists of all the Pareto-optimal solutions and the set of all the Pareto optimal objective vectors is called Pareto front (PF).

In this paper, two objective functions, namely, negative ratio association (NRA) and ratio cut (RC) (Gong et al., 2014) are minimized simultaneously. The two objective functions will be introduced in the following.

A graph is denoted as $G = (V, E)$ where V is the set of nodes (or vertices) and E is the set of edges connection between nodes. The corresponding adjacent matrix of the graph G is A. If $V_{1}$ and $V_{2}$ are two disjoint subsets of V, $L (V_{1}, V_{2}) = \sum_{i \in V_{1}, j \in V_{2}} A_{ij}$ and $L (V_{1}, {\bar{V}}_{2}) = \sum_{i \in V_{1}, j \in {\bar{V}}_{2}} A_{ij}$ . Given a partition $S = {V_{1}, V_{2}, \dots, V_{s})$ of the graph G, where $V_{i}$ is the node set of sub-graph $G_{i}$ for $i = 1, 2, \dots, s$ . Therefore, the NRA is defined as

NRA = - \sum_{i = 1}^{s} \frac{L (V_{i}, V_{i})}{| V_{i} |}

(4)

The RC is represented as

RC = \sum_{i = 1}^{s} \frac{L (V_{i}, {\bar{V}}_{i})}{| V_{i} |}

(5)

The corresponding multi-objective optimization for the community detection problems can be described as

Minimize {\begin{matrix} f_{1} = NRA = - \sum_{i = 1}^{s} \frac{L (V_{i}, V_{i})}{| V_{i} |} \\ f_{2} = RC = \sum_{i = 1}^{s} \frac{L (V_{i}, {\bar{V}}_{i})}{| V_{i} |} \end{matrix}

(6)

In this paper, we adopt decomposition strategy to solve the multi-objective optimization defined in equation (6). By using decomposition based Tchebycheff approach (Gong et al., 2014), the bi-objective optimization problems defined above can be changed as follows

\begin{matrix} Minimize g^{te} (x | λ, z^{*}) = max_{1 ⩽ i ⩽ m} {λ_{i} | f_{i} (x) - z_{i}^{*} |} \\ Subject to x \in Ω \end{matrix}

(7)

where m is the number of the objective functions, $z^{*} = (z_{1}^{*}, \dots, z_{m}^{*})^{T}$ is the reference point, that is, $z_{i}^{*} = min {f_{i} (x) | x \in Ω}$ for each $i = 1, \dots, m$ .

The decomposition based Tchebycheff method transforms the MOP into a set of distinct scalar aggregation problems. Every ant is responsible to solve the corresponding problem by applying priorities to each objective according to its weighting vector. It can help to find potential solutions that are evenly distributed along the PF and mitigate premature convergence (Gong et al., 2012).

Ant colony algorithm (ACO)

Ant colony algorithm was proposed by Dorigo (1992), and it was inspired from the path in the process of ants searching for food. The ant colony algorithm is a kind of simulated evolutionary algorithm. Firstly, the ant colony algorithm has a self-organization feature; that is to say, for some ants, through pheromones between ants, they can get a solution they is close to the optimal solution after a certain time period. Secondly, the ant colony algorithm is essentially a kind of parallel algorithm. In the search process, each ant performs an independent search, they only communicate with each other through the pheromone. So, the ant colony algorithm can be regarded as a distributed multi-agent system, and it begins to search from the different locations at the same time. Thirdly, the ant colony algorithm has positive feedback features. From the process of real ants foraging, we know that the ants will eventually find the shortest path, which directly depends on the accumulation of pheromones in the shortest path, and the accumulation of pheromones is a positive feedback process. Fourthly, the ant colony algorithm has strong robustness. Compared to other algorithms, its initial route request is not high, and needs no manual adjustment in the process of the search.

The ant colony algorithms were originally used to solve single objective optimization problems (Cordon et al., 2002; Dorigo and Gambardella, 1997; García-Martínez et al., 2007). Because of its good performance in single objective optimization, several multi-objective ACOs (mACOs) have been developed in recent years (Alaya et al., 2007; Angus and Woodward, 2009; Guntsch and Middendorf, 2002). In this paper, a new multi-objective ACO with decomposition is proposed for solving community detection problems in complex network.

The proposed method for community detection

In this section, the proposed MACOD will be described in detail.

Solution representation

A network can be modeled as a graph $G = (V, A)$ , which consists of the n nodes (or vertices) set and adjacency matrix A. $V = {v_{1}, \dots, v_{n}}$ is the set of nodes, and A is an $n \times n$ adjacency matrix representing connections between nodes. For an unweighted graph, A is Boole matrix and $A_{ij} \in {0, 1}$ .

Because a network can be represented as a graph, a community can be represented as a sub-graph of the network. Therefore, detecting the community structure in a network is equivalent to finding several sub-graphs that reveals the best partition of the network. Hence, the solution to the community detection problem can be formulated as a vector with n elements. Also, the vector represents a graph, whose connected component is equivalent to a community. For example, if the ith element in the vector equals j, then this relation can be interpreted as a link between verticies $v_{i}$ and $v_{j}$ , meaning $v_{i}$ and $v_{j}$ are in the same connected component, that is to say, in the same community. This kind of representation is called the locus-based adjacency representation, which has been employed by Pizzuti (2012) for multi-objective clustering. Figure 1 gives an example for the locus-based adjacency scheme.

Figure 1.

Illustration of the locus-based adjacency scheme. (a) A network with three communities. (b) Three sub-graph representing the three communities. (c) The locus-based representation for a solution. (d) Community classification results of decoding a solution.

Figure 1(a) shows a network with 12 nodes partitioned into three groups drawn as squares, circles and triangles, respectively. Figure 1(c) shows a possible solution vector to the community detection problem of the network in Figure 1(a). Figure 1(c) corresponds to sub-graph shown in Figure 1(b). Figure 1(d) is a result of decoding a solution in Figure 1(c). Given a specific network, the method shown in Figure 1 can be used for the initialization of population.

Heuristic information

For a specific problem, the use of a priori knowledge can solve this problem better. For partitioning community network problem, not only the pheromones will be used, but also the relationships between nodes in the network. The heuristic pheromone is adopted to reflect the relationships between nodes.

The Pearson correlation between nodes is used as the similarity measure in Chang et al., (2013), which is a good method to reveal the correlation between nodes. The Pearson correlation $C (i, j)$ between nodes $v_{i}$ and $v_{j}$ is defined as follows

C (i, j) = \frac{\sum_{v_{l} \in V} (A_{il} - μ_{i}) (A_{jl} - μ_{j})}{n σ_{i} σ_{j}}

(8)

where $A_{il}$ is the $l th$ element of the $i th$ row in the adjacency matrix A, n is number of nodes, $μ_{i} = \sum_{l} A_{il} / n$ is the average, and $σ_{i} = \sqrt{\sum_{l} {(A_{il} - μ_{i})}^{2} / n}$ is the standard deviation.

If nodes $v_{i}$ and $v_{j}$ are very similar in the view of the structure, the value of $C (i, j)$ will be close to 1. If nodes $v_{i}$ and $v_{j}$ are little similar, then the value of $C (i, j)$ will be close to -1. Since $C (i, j)$ may take negative value, our algorithm uses the following function to convert it into positive for convenience

η_{ij} = \frac{1}{1 + e^{- C (i, j)}}

(9)

We take $η_{ij}$ as heuristic information. The more similar nodes $v_{i}$ and $v_{j}$ are, the larger value $η_{ij}$ would take, and the more probably edge $(i, j)$ is to be taken as a solution component.

Method of producing solution

We denote a solution as a set of n edges for a network with n nodes. A pair of nodes represents an edge. For example, the edge $(i, j)$ represents a connection line between node i and node j. The process of generating a solution is choosing n edges. Generating solution is also called solution construction. For a network with n nodes, constructing a solution needs n steps.

At the construction step $i = 1, 2, \dots, n$ , we choose an edge $(i, j)$ according to the probability

p (i, j) : p (i, j) = \frac{{(τ_{ij})}^{α} {(η_{ij})}^{β}}{\sum_{v_{q} \in ψ_{i}} {(τ_{iq})}^{α} {(η_{iq})}^{β}} if v_{j} \in ψ_{i}

(10)

where $ψ_{i}$ is a set of the nodes connected with node $v_{i}$ , and parameters $α$ and $β$ determine the relative importance of the pheromone and the heuristic information. After n construction steps, a solution containing n edges is constructed completely. $τ_{ij}$ is the value of pheromone on the edge $(i, j)$ , and $η_{ij}$ is the value of heuristic information of the edge $(i, j)$ .

Framework of the proposed algorithm

MACOD decomposes the MOP into pop single objective sub-problems by choosing pop weights vectors $λ_{1}, λ_{2}, \dots, λ_{pop}$ , where pop is the size of population. Before introducing the framework of the proposed algorithm, two important concepts, neighborhood and group, need to be introduced.

Neighborhood: the neighborhood of ant i contains ns ants whose sub-problems weights vectors are the ns closest to weight $λ_{i}$ among all of pop weight vectors, ns is a parameter that means the neighborhood size.

Group: A population contained pop ants are divided into gs groups through the relationship between the weight vectors, gs is a parameter. Each group approximates a small range of PF.

In the following, we introduce some terms and symbols used in the proposed algorithm in order to an easy understanding.

A population with pop ants $x^{1}, \dots, x^{pop} \in Ω$ , where $x^{i}$ is the current solution to the subproblem i:

$F^{1}, \dots, F^{pop}$ , where $F^{i} = g^{te} (y^{i} | λ_{i})$ is the Tchebycheff function value of the solution $y^{i}$ ;

$z = {(z_{1}, \dots, z_{m})}^{T}$ , where $z_{i}$ is the best value found so far for objective $f_{i}$ ;

$τ^{1}, \dots τ^{gs}$ , where $τ^{j}$ is the current pheromone matrix for group j;

$η$ is the heuristic information matrix, which is predetermined before the search and will not change until the search ends;

external population (EP) is used to store all non-dominated solutions found so far during the search.

Procedure of MACOD algorithm:
Parameters: Max iterations: maxgen, population size: pop, number of decomposed sub-problems: pop, group size: gs, neighbor size: ns, pheromone evaporation coefficient: $ρ$ , two control parameters: $α, β$ . Input: The adjacent matrix A of a network. Output: An external population (EP). Step 0 Initialization: Initialize the pheromone information matrix $τ^{j}$ for $j = 1, \dots, gs$ , and the weighted vectors $W = {λ_{1}, λ_{2}, \dots, λ_{pop}}^{T}$ ; all items of the heuristic information matrix $η$ are set 1. Step 1 Main loop: Set t=1. Step 2 Solution Construction: For each $i = 1, \dots, pop$ , ant i constructs a new solution $y^{i}$ according to equation (10). For each $k = 1, \dots, m$ , compute $f_{k} (y^{i}), \dots, f_{k} (y^{pop})$ . If t=1, for each $k = 1, \dots, m$ , the best value $f_{k (best)}$ is found from $f_{k} (y^{i}), \dots, f_{k} (y^{pop})$ , and set $z_{k} = f_{k (best)}$ . If t>1, for each $k = 1, \dots, m$ , find the best value $f_{k (best)}$ from ${f_{k}^{i} \| i = 1, \dots, N}$ , if $z_{k} < f_{k (best)}$ , set $z_{k} = f_{k (best)}$ . Compute $F^{i} = g^{te} (y^{i} \| λ_{i}, z^{})$ according to equation (7). Step 3 Update of EP: If t=1, Initialize EP as the set of all non-dominated vectors in ${F^{1}, \dots, F^{pop}}$ ; otherwise, go to Step 4. Step 4 Local search: For each j( $j = 1, \dots, gs$ ) group, find $y_{i}^{j}$ with $g^{te} (y_{i}^{j}) ⩽ g^{te} (y_{i}^{j} \| λ^{i}, z)$ , and i in the group j. To do the local search operator for each $y_{i}^{j}$ , $j = 1, \dots, gs$ , gs is the group size. Step 5 Update of Pheromone Matrix: For each $j = 1, \dots, gs$ , compute modularity of the solution $y^{j}$ , which is obtained in Step 4, then update pheromone matrix $τ^{j}$ according to equation (11). Step 6 Update neighborhood solutions: For i = 1, …, N if $g^{te} (y^{h} \| λ^{i}, z) ⩽ g^{te} (y^{i} \| λ^{i}, z)$ where the subproblem h is neighborhood of a subproblem i, set $y^{i} = y^{h}$ and $F (y^{i}) = F (y^{h})$ . Step 7: Update z use the same method in Step 2. Step 8: Compute $τ_{max}, τ_{min}$ , update pheromone matrix again. Step 9 Termination: If t > maxgen*, output EP, otherwise return to Step 2.

Procedure of MACOD algorithm:

Parameters: Max iterations: maxgen, population size: pop, number of decomposed sub-problems: pop, group size: gs, neighbor size: ns, pheromone evaporation coefficient:

ρ

, two control parameters:

α, β

.
Input: The adjacent matrix A of a network.
Output: An external population (EP).
Step 0 Initialization: Initialize the pheromone information matrix

τ^{j}

for

j = 1, \dots, gs

, and the weighted vectors

W = {λ_{1}, λ_{2}, \dots, λ_{pop}}^{T}

; all items of the heuristic information matrix

η

are set 1.
Step 1 Main loop: Set t=1.
Step 2 Solution Construction: For each

i = 1, \dots, pop

, ant i constructs a new solution

y^{i}

according to equation (10). For each

k = 1, \dots, m

, compute

f_{k} (y^{i}), \dots, f_{k} (y^{pop})

. If t=1, for each

k = 1, \dots, m

, the best value

f_{k (best)}

is found from

f_{k} (y^{i}), \dots, f_{k} (y^{pop})

, and set

z_{k} = f_{k (best)}

. If t>1, for each

k = 1, \dots, m

, find the best value

f_{k (best)}

from

{f_{k}^{i} | i = 1, \dots, N}

, if

z_{k} < f_{k (best)}

, set

z_{k} = f_{k (best)}

. Compute

F^{i} = g^{te} (y^{i} | λ_{i}, z^{*})

according to equation (7).
Step 3 Update of EP: If t=1, Initialize EP as the set of all non-dominated vectors in

{F^{1}, \dots, F^{pop}}

; otherwise, go to Step 4.
Step 4 Local search: For each j(

j = 1, \dots, gs

) group, find

y_{i}^{j}

with

g^{te} (y_{i}^{j}) ⩽ g^{te} (y_{i}^{j} | λ^{i}, z)

, and i in the group j. To do the local search operator for each

y_{i}^{j}

j = 1, \dots, gs

, gs is the group size.
Step 5 Update of Pheromone Matrix: For each

j = 1, \dots, gs

, compute modularity of the solution

y^{j}

, which is obtained in Step 4, then update pheromone matrix

τ^{j}

according to equation (11).
Step 6 Update neighborhood solutions: For i = 1, …, N if

g^{te} (y^{h} | λ^{i}, z) ⩽ g^{te} (y^{i} | λ^{i}, z)

where the subproblem h is neighborhood of a subproblem i, set

y^{i} = y^{h}

and

F (y^{i}) = F (y^{h})

.
Step 7: Update z use the same method in Step 2.
Step 8: Compute

τ_{max}, τ_{min}

, update pheromone matrix again.
Step 9 Termination: If t > maxgen, output EP, otherwise return to Step 2.

In each iteration, we choose the best solution in each group, then we can get gs solutions ${y_{1}, \dots, y_{gs}}$ , which are used to update the pheromone matrix. The pheromone update rule is given as follows

τ_{ij}^{k} = ρ \times τ_{ij}^{k} + Δ τ_{ij}^{k}

(11)

where $ρ$ is the pheromone evaporation coefficient, k = 1,…, gs. $τ^{k}$ means that the pheromone matrix of the kth group. $τ_{ij}$ is the element value of the ith row and jth column in the pheromone matrix $τ$ . If edge (i, j) is in $y^{k}$ , then $Δ τ_{ij}$ is the modularity of the solution $y^{k}$ , otherwise $Δ τ_{ij}$ is 0.

In order to avoid stagnation, we use $[τ_{\min}, τ_{\max}]$ to limit the value range of pheromone. $τ_{max} = Δ τ^{k}$ , $Δ τ^{k}$ is defined above, and $τ_{min} = 0.005 \times τ_{max}$ .

A new efficient local search algorithm

In order to make sure that the algorithm has good convergence and stability, we proposed a new efficient local search algorithm, namely, local search-based mutation method (LSMM). LSMM algorithm is simple, we sort all solutions according to their objective values in each generation, and then we get one best solution in each group. For these solutions, we use local search method.

The process of local search method:
Parameters: A maximum number of iterations: TT, which is set as 40000 in our experiments, mutation ratio: mr, which is set as 0.11 in our experiments, number of nodes: n. Input: Solution y. Output: The new solution y. Step 0: Initialize mr, compute the number of nodes in the mutation: m = n×mr; and set $t = TT$ Step 1: While $t > 1$ do Step 1.1: For $i = 1, \dots, m$ , each i, select one of the nodes in the solution y to be mutated. For the mutation operator, one node of the solution is picked randomly, denoted by i, then randomly selects one node of its neighbors linking with it. Then a new solution $y^{}$ is produced. Step 1.2: If $g^{te} (y^{} \| λ, z) < g^{te} (y \| λ, z)$ , go to Step 2; otherwise, go to Step 1.3. Step 1.3: $t = 0.99 \times t$ , go to Step 1. Step 2: Output $y^{}$ .

The process of local search method:

Parameters: A maximum number of iterations: TT, which is set as 40000 in our experiments, mutation ratio: mr, which is set as 0.11 in our experiments, number of nodes: n.
Input: Solution y.
Output: The new solution y*.
Step 0: Initialize mr, compute the number of nodes in the mutation: m = n×mr; and set

t = TT

Step 1: While

t > 1

do
Step 1.1: For

i = 1, \dots, m

, each i, select one of the nodes in the solution y to be mutated. For the mutation operator, one node of the solution is picked randomly, denoted by i, then randomly selects one node of its neighbors linking with it. Then a new solution

y^{*}

is produced.
Step 1.2: If

g^{te} (y^{*} | λ, z) < g^{te} (y | λ, z)

, go to Step 2; otherwise, go to Step 1.3.
Step 1.3:

t = 0.99 \times t

, go to Step 1.
Step 2: Output

y^{*}

Experimental results and analysis

In this section, two evaluation metrics, namely, Normalized Mutual Information (NMI) and modularity (Q) are used to validate the proposed algorithm and four existing algorithms, including complex network clustering by multiobjective discrete particle swarm optimization based on decomposition (MODPSO) (Gong et al., 2014), community detection in networks by using multiobjective evolutionary algorithm with decomposition (MOEAD-net) (Gong et al., 2012), community detection using ant colony optimization (ACO) (Chang et al., 2013) and community detection based on modularity and an improved genetic algorithm (GA-net) (Shang et al., 2013) are compared with the proposed algorithm over GN benchmark network and four real-world networks.

The proposed algorithm is written in Matlab. All experiments were carried out on a desktop computer with Intel(R) Core(TM) 2CPU (1.86GHz) and 2 GB of RAM, Running Windows XP.

Evaluation metrics

In this paper, we adopt two commonly used evaluation metrics, namely, NMI and Q to evaluate the proposed community detection algorithm.

NMI is adopted to represent the similarity between the detected community structure and the true community structure (Wu and Huberman, 2004). NMI has been proved to be reliable as a similarity measure by Danon et al. (2005). Given two partitions A and B of a network, C is the confusion matrix whose elements C_ij is the number of nodes of the community i of the partition A that are also in the community j of the partition B. The normalized mutual information is defined as follows

I (A, B) = \frac{- 2 \sum_{i = 1}^{c_{A}} \sum_{j = 1}^{c_{B}} C_{ij} \log (C_{ij} N / C_{i .} C_{. j})}{\sum_{i = 1}^{c_{A}} C_{i .} \log (C_{i .} / N) + \sum_{j = 1}^{c_{B}} C_{. j} \log (C_{. j} / N)}

(12)

Here, $C_{A}$ ( $C_{B}$ ) is the number of the classes in the partition A(B). $C_{i .}$ ( $C_{. j}$ ) is the number of elements of C in row i (column j), N is the total number of nodes. The greater similarity between A and B, the bigger the value of $I (A, B)$ . If A=B, then $I (A, B) = 1$ ; if A and B are completely different, then $I (A, B) = 0$ . For the network, the larger value of NMI represents a greater similarity between A and B.

The modularity Q, proposed by Girvan and Newman (2002), has been proved to be an effective objective function to detect community structure. The modularity Q is defined as follows

Q = \frac{1}{2 m} \sum_{i, j} (A_{ij} - \frac{k_{i} k_{j}}{2 m}) δ (i, j)

(13)

Here, m represents the total number of the edges in the community network. $i, j = 1, 2, \dots, N$ , N represents the number of nodes in the network, i and j are two nodes in the network. $A_{ij}$ is the element in the adjacent matrix. $k_{i}$ and $k_{j}$ respectively represent the degree of the node i and the node j. If the ith node and the jth node are in the same community, $δ (i, j) = 1$ ; otherwise, $δ (i, j) = 0$ . In general, the greater value of the modularity Q is, the more obvious the community structure is.

In the following experiments, the maximum of NMI and Q of each run will be maximized and averaged after 30 runs to get final results.

Comparison algorithms and parameter setting

In this paper, we compare our algorithm MACOD with four algorithms on the GN benchmark network and the four real-world networks. The four algorithms based on evolutionary mechanisms that we chose are the following: MODPSO, MOEAD-net, ACO and GA_net. In the following text, we mainly explain why the four algorithms are considered as compared algorithms.

Because both ACO and MACOD use ant colony algorithm to solve community detection, based on this, ACO algorithm is selected as a compared algorithm. Both MOEAD-net and MACOD adopt multiobjective optimization mechanism-based decomposition, so MOEAD-net algorithm is selected as another compared algorithm. GA-net algorithm is used as another compared algorithm, because it takes the modularity Q as the objective function along with MACOD algorithm. MODPSO is also taken as another compared algorithm because it is an algorithm that is known to perform well. Related parameters used in our algorithm and other comparison algorithms are shown in Table 1.

Table 1.

The parameter settings of all algorithms.

Algorithm	maxgen	pop	pc	pm	ns	$ρ$	$α$	$β$	gs
MACOD	150	100	–	–	25	0.85	1	8	15
MODPSO	150	100	–	0.1	40	–	–	–	–
MOEAD-net	150	100	1	0.06	15	–	–	–	–
ACO	150	100	–	–	–	0.9	1	8	–
GA-net	150	100	1	0.08	–	–	–	–	–

All compared algorithms use their best values of parameters, as described in the relevant literatures, except two common parameters. The two parameters are maxgen and pop, where maxgen denotes the maximum iterations of the algorithm and pop represents population size. The parameter pc is the crossover probability, pm is the mutation probability, ns is the neighborhood size. In MACOD and ACO, $ρ$ is the pheromone evaporation coefficient, $α$ and $β$ are two control parameters. The parameter gs is the number of groups in population in MACOD. We use the same parameter settings for all the test problems without allowing any hand tunings.

Experimental results on benchmark networks

Experiments on GN extended benchmark networks

In this section, we test our algorithm on the benchmark network proposed by Lancichinetti et al. (2008), which is an extension of the classic benchmark network proposed by Girvan and Newman in (2002). The network has 128 nodes that are divided into four communities, and every community has 32 nodes. Every node has an average degree of 16 and shares a fraction $μ$ of its edges with nodes in other communities, and $1 - μ$ with nodes in its own community. $μ$ ( $0 ⩽ μ ⩽ 1$ ) is the mixing parameter. We can evaluate the performance of algorithm by different value of $μ$ . When $μ$ <0.5, the number of nodes connected with a node in the same community is larger than that of nodes connected with this node in different communities. Thus, a good algorithm should detect the community structure inside the network. If $μ$ >0.5, it is generally considered that there is no community structure. So, we use the extension of GN benchmark network to judge whether an algorithm is good for detecting the community structure inside the network or not.

Eleven different networks are generated by adjusting value of $μ$ ranging from 0 to 0.5. Figure 2 shows the average value of NMI obtained by MACOD, MODPAO, MOEAD-net, ACO and the GA-net algorithms over 10 times on the GN benchmark. It is easy to see that the value of NMI obtained by MACOD is 1 when $μ$ changes from 0 to 0.4, and when $μ$ =0.45 and $μ$ =0.5, the value of NMI is also larger than other algorithms. These results show that the performance of the proposed algorithm MACOD is better than those of MODPSO, MOEAD-net, ACO and GA-net.

Figure 2.

NMI obtained by MACOD, MODPAO, MOEAD-net, ACO and the GA-net on the extension of GN benchmark networks.

Experiments on LFR benchmark networks

In LFR benchmark networks (Lancichinetti et al., 2008), the distributions of degree and community size are both power laws with tunable exponents $τ_{1}$ and $τ_{2}$ , respectively. Each vertex shares a fraction $1 - μ$ of its edges with other vertices of its community and a fraction $μ$ with the vertices of other communities; $0 ⩽ μ ⩽ 1$ is the mixing parameter. LFR benchmark networks can reflect some important features in graph representations of real systems and all vertices have similar degree, all communities have exactly the same size by construction. In our experiments, we generate 17 networks with the mixing parameter increasing from 0 to 0.8 with an interval of 0.05. Each network contains 1000 nodes and the cluster size ranges from 10 to 50. Figure 3 presents the average value of NMI obtained by the five algorithms over 10 times.

Figure 3.

NMI obtained by MACOD, MODPAO, MOEAD-net, ACO and the GA-net on LFR benchmark networks.

As shown in Figure 3, we can see that when $μ ⩽ 0.35$ , MACOD, MODPAO, MOEAD-net can figure out the true partitions (NMI is 1), however with the increasing of the mixing parameter, especially, when $μ > 0.5$ , none of them can make it. When $μ = 0.5$ the proposed algorithm still gets NMI =1, while MODPSO gets NMI = 0.9885. From Figure 3, we can see that the proposed algorithm is better than other algorithms. Among MOEAD-net, ACO and GA-net, the results of GA-net is worst. In a word, for LFR benchmark networks, the performance of proposed algorithm is competitive.

Experimental results on real-world networks

In this section, we first introduce four small real-world networks used in this study including Zachary’s Karate Club Network, Dolphins Social Network, US Politics Network and the American College Football Network.

The Zachary’s Karate Club Network was constructed by Zachary (1977), which consists of 34 nodes and 78 edges and was divided into two communities.

The Dolphins Social Network was proposed by Lusseau, et al. (2003), who observed dolphin behavior for seven years. The Dolphin Social Network consists of 62 nodes and 159 edges, and nodes are divided into two communities.

The Books about US Politics Network of political books is compiled by Kerbs. This network consists of 105 nodes and 411 edges. The network was divided into three communities by Newman (2006).

The American College Football Network (Jiang and McQuay, 2012) comes from the United States college football tournament. The nodes of the American College Football Network represent different football teams and the edges of the network represent the matches between two teams. The network consists of 115 nodes and 616 edges. These nodes are divided into 12 communities, and each of them represents a football team.

Comparison of the results of NMI

Figure 4 shows the box plot of the values of NMI over 30 runs obtained by the proposed algorithm and comparison algorithms on Zachary’s Karate Club, the Dolphin Social Network, the American College Football and the Books about US Politics, respectively. Here, on each box plot, in middle line in the rectangle is the median, the edges of the box plot are lower quartile and upper quartile, and the plus sign of the box plot denotes abnormal values or isolated values.

Figure 4.

The box plot of values of NMI obtained by five algorithms over 30 runs on the four real-world networks.

From Figure 4, it can be seen that most of the values of NMI obtained by MACOD, MODPSO and MOEAD-net are bigger than ACO and GA-net over 30 runs on the four real-world networks. In other words, the performance of MACOD, MODPSO and MOEAD-net is better than ACO and GA-net on the four networks. For the Karate Network, the values of NMI obtained by our algorithm and MODPSO, MOEAD-net, GA-net are 1 all the time in each run. This means that the four algorithms can 100% detect the community structure information on the Zachary’s Karate Club. The values of NMI obtained by ACO is smaller than 0.9, which means the performance of ACO is worse than the other four algorithms on the Karate Network. For the Dolphin Network, the performance of MACOD, MODPSO and MOEAD-net is also good, the most of values of NMI obtained by their algorithm is 1. But the values of NMI obtained by GA-net are range from 0.55 to 1, thus the performance of GA-net is worse than the three algorithms mentioned above on the Dolphin Network. The performance of ACO is still not good on the Dolphin Network. As shown in Figure 4, the values of NMI of the Football Network obtained by MACOD, MODPSO are about 0.92, the results of their algorithm are similar. MOEAD-net, ACO and GA-net are unstable compared with the first two algorithms. For the Books Network, it can be seen from Figure 3 that the result of MODPSO is better than other four algorithms. From the above analysis, we can see that the results obtained by our algorithm are relatively good.

Table 2 shows the maximum NMI and the average value NMI of MACOD, MODPSO, MOEAD-net, ACO and the GA-net on the four real-world networks in 30 runs.

Table 2.

The values of NMI on the four networks.

Networks	Index	MACOD	MODPSO	MOEAD-net	ACO	GA-net
Karate	$NM I_{max}$	1	1	1	1	1
	$NM I_{avg}$	1	1	1	0.8436	1
Dolphin	$NM I_{max}$	1	1	1	0.7813	1
	$NM I_{avg}$	0.9949	0.9907	1	0.6940	0.7107
Football	$NM I_{max}$	0.9386	0.9289	0.9367	0.9269	0.8695
	$NM I_{avg}$	0.9232	0.9262	0.9309	0.9086	0.8167
Books	$NM I_{max}$	0.6303	0.6101	0.5979	0.5589	0.6527
	$NM I_{avg}$	0.5908	0.6081	0.5845	0.5142	0.6107

As is shown in Table 2, the maximum value of NMI on the four real-world networks obtained by our algorithm is bigger than other four algorithms. For each network, different algorithms obtained different results and we cannot directly judge which is better than other algorithms from Table 2. Therefore, we will discuss each algorithm respectively in the following.

For the Karate Network, each algorithm can detect the real network structure completely every time in 30 runs except ACO. This shows that the ACO algorithm is not stable in detecting the Karate Network compared with other four algorithms. For the Dolphin Network, MODPSO, MOEAD-net, and GA-net can get the real network structure completely in 30 runs except ACO algorithm. It can be seen from Table 2, the average value of NMI obtained by MOEAD-net is 1. From this, we know that MOEAD-net can detect the real community structure all the time in 30 runs. The average values of NMI obtained by other four algorithms are 0.9949, 0.9907, 0.6939 and 0.8240, respectively, which shows that our algorithm is better than the other three algorithms in detecting the Dolphin Network. Also, our algorithm obtains good results on detecting the Football Network and Books Network; here analysis is not given in detail for lack of space.

Comparison of the results of Q

As is shown in Figure 5, for the Karate Network, the values of modularity Q obtained by five algorithms on the Karate Network and the Dolphin Network are less volatile. For the Karate Network, the best value of modularity Q obtained by MACOD, MODPSO, MOEAD-net, ACO and GA-net are the same value, that means their optimal results are the same. As shown in Figure 4, the values of Q of the Football Network obtained by MACOD, MODPSO, MOEAD-net, and ACO are about 0.6, the results of their algorithm are similar. GA-net is unstable compared with the first four algorithms. For the Books Network, the result of ACO is worse than other four algorithms. From the above analysis, we can see that the results obtained by our algorithm are relatively good.

Figure 5.

The box plot of values of Modularity Q obtained by five algorithms over 30 runs on the four real-worlds networks.

As is shown in Table 3, the maximum value of the Q and the average value of Q on the four real-world networks obtained by the five algorithms have small difference. For the Karate Network, the Football Network and the Books Network, our algorithm has better results in the maximum value of Q than other four algorithms. And for the Dolphin Network, the maximum value of the Q is same if this value keeps two decimal places. It can be seen from Table 3 that the performance of the first four algorithms is similar. The result of GA-net algorithm is not good in detecting the Karate Network and the Dolphin Network.

Table 3.

The values of Modularity Q on the four networks.

Networks	Index	MACOD	MODPSO	MOEAD-net	ACO	GA-net
Karate	$Q_{max}$	0.4198	0.4198	0.4198	0.4198	0.3718
	$Q_{avg}$	0.4198	0.4172	0.4198	0.4198	0.3718
Dolphin	$Q_{max}$	0.5268	0.5265	0.5220	0.5285	0.4027
	$Q_{avg}$	0.5210	0.5243	0.5212	0.5275	0.4027
Football	$Q_{max}$	0.6046	0.6032	0.6044	0.6046	0.6044
	$Q_{avg}$	0.6039	0.6031	0.6044	0.6027	0.5899
Books	$Q_{max}$	0.5269	0.5262	0.5269	0.5269	0.5221
	$Q_{avg}$	0.5265	0.5262	0.5269	0.5237	0.5221

Through the results in Table 2 and Table 3, and the related discussion, it is concluded that our algorithm has a good performance for community detection.

Clustering results on four real-world networks

From Figure 6, it can be seen that MACOD can successfully detect the clustering truth construction of the Karate Network and the Dolphin Network (correspond to NMI=1).

Figure 6.

Clustering results on the Karate Network and the Dolphin Network by MACOD. (a) The real structure detected by MACOD on the Karate Network. (b) The real structure detected by MACOD on the Dolphin Network.

From Figure 7, it can be seen that the real structure of Football Network has 12 communities; the structure with highest NMI value obtained by MACOD has 11 communities. By comparing Figure 7(a) and Figure 7(b), we can find that several nodes are divided into other communities; however, from the value of NMI, our proposed method is still very effective and promising.

Figure 7.

The real structure of Football Network and clustering results on the Football Network obtained by MACOD. (a) The real structure of Football Network; (b) The structure with highest NMI value on the Football Network.

From Figure 8, it can be seen that the real structure of Books Network has three communities, while the structure with highest NMI value obtained by MACOD has two communities. By comparing Figure 8(a) with Figure 8(b), we can find that the nodes of middle community are divided into two other communities. However, from the value of NMI and comparison with other algorithms, our proposed method is still very effective and promising.

Figure 8.

The real structure of Books Network and clustering results on the Books Network by MACOD. (a) The real structure of Books Network. (b) The structure with highest NMI value on the Books Network.

Results of Wilcoxon matched-pairs signed-rank test

For a further analysis of experimental results, according to the results of NMI value and Modularity Q value obtained by the proposed algorithm (MACOD) and other algorithms (denoted as Contrast) on the four real-world network in 30 runs, we check whether there exists a statistically significant difference between MACOD and other algorithms by the Wilcoxon matched-pairs signed-rank test (Demsar, 2006) with the significance level $α = 0.05$

\begin{matrix} H_{0} : μ_{MACOD} = μ_{Contrast} \\ H_{1} : μ_{MOACOD} \neq μ_{Contrast} \end{matrix}

Results are shown in Table 4 and Table 5, where we report the p-value of the statistical test. $α ⩾ p$ indicates that the hypothesis H₁ is right, that is to say, there is significant difference between the proposed algorithm and other algorithms; otherwise, the hypothesis H₀ is right and there is no difference between them.

Table 4.

The ‘p-value’ is obtained over two NMI sets obtained by MACOD and other algorithms on the four real-world networks.

Network	vs MODPSO	vs MOEAD net	vs GA_net
Karate	1	1	1
Dolphin	0.2142	0.1573	0.0000
Football	0.0038	0.0011	0.0000
Books	0.0002	0.0270	0.0002

Table 5.

The ‘p-value’ is obtained over two Modularity Q sets obtained by MACOD and other algorithms on the four real-world networks.

Network	vs MODPSO	vs MOEAD_net	vs ACO
Karate	0.0000	0.0000	1
Dolphin	0.0038	0.9590	0.0000
Football	0.0002	0.0096	0.0002
Books	0.0000	0.0000	0.0000

Through comprehensive analysis on Table 4 and Table 2, we can see that for the Karate Network, although the results of NMI value obtained by MACOD, MODPSO, MOEAD-net and GA-net are the same, the p-values obtained are 1, which means the statistical difference between the proposed algorithm and MODPSO, MOEAD-net, GA-net are not significant. For the Dolphin Network, we can see from Table 4, results obtained by comparing MACOD with MODPSO, MOEAD_net cannot reject H₀, that is to say, there is no significant difference between them for the Dolphin Network, but there are significant differences between MACOD and ACO, GA-net. In the same way, it is easy to conclude that the differences between MACOD and MODPSO, MOEAD-net, ACO, GA-net are significant with $α = 0.05$ on Football Network and Books Network in terms of NMI sets obtained by MACOD and other algorithms.

From Table 4, the differences between MACOD and MODPSO, MOEAD-net, ACO, GA-net are significant with $α = 0.05$ except MOEAD_net and ACO. We can see more clearly from Table 5 that the differences between MACOD and other four algorithms are significant on most of the testing problems used in this section.

The results of statistical tests confirm that there are significance differences between MACOD and four compared algorithms on most of the four real-world networks, which shows that the proposed algorithm is competitive.

Experimental results on large real-world networks

In this section, we try to apply MACOD on three large real-world networks including the Santa Fe Institute (SFI) network (Danon et al., 2005), the netscience network (Newman, 2006) and the power grid network (Watts and Strogatz, 1998). Table 6 shows the properties of the three networks. Since the power grid network and the netscience network are too large, its results are obtained only in 10 runs. Other parameters used here are the same as previous section.

Table 6.

Network properties.

Network	Vertex	Edge	Real clusters
SFI	118	200	unknown
Netscience	1589	2742	unknown
Power grid	4941	6594	unknown

Table 7 gives the statistical results of Modularity values obtained by MACOD, MODPSO, MOEAD-net, ACO, and GA_net over three large-scale networks. From the table, we can see that for SFI network with 118 vertexes and 200 edges, MOEAD-net obtains the maximum value of Q among five algorithms, however, the proposed shows a better stability and produces the highest average value of Q.

Table 7.

The values of Modularity Q obtained by four algorithms over three large-scale networks.

Network	Index	MACOD	MODPSO	MOEAD-net	ACO	GA_net
SFI	$Q_{max}$	0.7487	0.7436	0.7506	0.7484	0.6089
SFI	$Q_{avg}$	0.7465	0.7405	0.7450	0.7446	0.6048
Netscience	$Q_{max}$	0.9476	0.9474	0.9409	0.9455	0.8518
Netscience	$Q_{avg}$	0.9459	0.9440	0.9316	0.9378	0.8462
Power grid	$Q_{max}$	0.7987	0.8017	0.7923	0.7718	0.6187
Power grid	$Q_{avg}$	0.7952	0.7949	0.7819	0.7643	0.5762

As shown in Table 7, we can see that, for SFI network, the proposed algorithm gets the best average value of Modularity Q among five comparison algorithms while the maximum Modularity Q obtained MOEAD-net is best and the statistical difference between the proposed algorithm and MOEAD-net is not significant according to p=0.072 in Table 8. The reason why the average value of Modularity Q is better than MOEAD-net, is that the proposed algorithm is more stable and can get values of Q close to 0.7465 in 10 runs.

Table 8.

The ‘p-value’ is obtained over two Modularity Q sets obtained by MACOD and other algorithms on the three large-scale networks.

Network	vs MODPSO	vs MOEAD_net	vs ACO
SFI	0.0031	0.0720	0.0000
Netscience	0.0058	0.0043	0.0020
Power grid	0.0690	0.0013	0.0001

For netscience network, the proposed algorithm obtains the best $Q_{max}$ and the best $Q_{avg}$ , as shown in Table 7, and it outperforms all the other algorithms, which also can be confirmed by results given in Table 8– all p-value is smaller than 0.05.

The average value of Modularity Q on the Power grid network obtained by MACOD is bigger than the other four algorithms; we also see that the statistical difference between MACOD and MODPSO is not significant (p-value =0.069), since MODPSO gets best $Q_{max}$ , which also shows our method is more stable than MODPSO.

In conclusion, when dealing with large-scale networks, the performance of MACOD is still better than the other four algorithms according to the average values of Modularity Q, which shows the potential of MACOD to solve the complex network with large scale.

Conclusions

Ant colony algorithm has been extensively studied and widely used for solving hard combinatorial problems, like traveling salesman problems, vehicle routing problems and quadratic assignment problems. But there is very little research in the field of community detection. In this paper, a multi-objective ant colony optimization with decomposition for community detection in complex networks (MACOD) is proposed. MACOD adopts decomposition mechanism to decompose a two-objective community detection problem into a number of single objective optimization problems. Moreover, a new efficient local search algorithm is designed in order to improve the stability of the algorithm. The proposed MACOD has been applied to solve nine community detection problems, and experimental results have shown that MACOD can obtain a competitive and similar performance with the existing best algorithm (MODPSO) for the community detection problems. A further work will focus on improving the quality of solutions and will try to detect larger community networks.

Footnotes

Declaration of conflicting interest

The authors declare that there is no conflict of interest.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (Nos: 61876141, 61373111); the Fundamental Research Funds for the Central Universities (Nos. K50511020014, K5051302084); and the Provincial Natural Science Foundation of Shaanxi of China (No. 2014JM8321).

References

Alaya

Solnon

Ghedira

(2017) Ant colony optimization for multi-objective optimization problems. In: Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, Patras, Greece, 29–31 October 2007, pp. 450–457.

Angus

Woodward

(2009) Multiple objective ant colony optimizations. Swarm Intelligence 3(1): 69–85.

Chang

Feng

Ren

(2013) Community detection using Ant Colony Optimization. In: 2013 IEEE Congress on Evolutionary Computation, Cancún, Mexico, 20–23 June 2013, pp. 3072–3078.

Cordón

Viana

IFD

Herrera

(2002) Analysis of the best-worst ant system and its variants on the qap. Soft Computing 9(2–3): 177–192.

Danon

Díazguilera

Duch

et al . (2005) Comparing community structure identification. Journal of Statistical Mechanics Theory and Experiment 2005(9): P09008.

Demsar

(2006) Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research 7(1): 1–30.

Dorigo

(1992) Optimization, learning and natural algorithms. Thesis Politecnico Di Milano Italy.

Dorigo

Gambardella

(1997) Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1): 53–66.

Eichfelder

(2009) An Adaptive Scalarization Method in Multiobjective Optimization. SIAM Journal on Optimization 19(4): 1694–1718.

10.

García-Martínez

Cordón

Herrera

(2007) An empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. European Journal of Operational Research 180(1): 116–148.

11.

Girvan

Newman

MEJ

(2002) Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America 99(12): 7821–7826.

12.

Gong

Cai

Chen

et al . (2014) Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Transactions on Evolutionary Computation 18(1): 82–97.

13.

Gong

Jiao

et al . (2011) Memetic algorithm for community detection in networks. Physical Review E 84(5 Pt 2): 056101.

14.

Gong

Zhang

et al . (2012) Community detection in networks by using multiobjective evolutionary algorithm with decomposition. Physica A Statistical Mechanics and its Applications 391(15): 4050–4060.

15.

Guntsch

Middendorf

(2002) A Population Based Approach for ACO. In: Proceedings of the Applications of Evolutionary Computing on EvoWorkshops, Como, Italy, pp. 72–81. Berlin Heidelberg: Springer.

16.

Halalai

Lemnaru

Potolea

(2010) Distributed community detection in social networks with genetic algorithms. In: Proceedings of the 2010 IEEE 6th International Conference on Intelligent Computer Communication and Processing, 26–28 August 2010, Cluj-Napoca, pp. 35–41. IEEE.

17.

Jiang

Mcquay

(2012) Modularity functions maximization with nonnegative relaxation facilitates community detection in networks. Physica A Statistical Mechanics and its Applications 391(3): 854–865.

18.

Zhang

Battiti

(2013) Moea/d-ACO: A multiobjective evolutionary algorithm using decomposition and antcolony. IEEE Transactions on Cybernetics 43(6): 1845–1859.

19.

Kernighan

Lin

(1970) An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49(2): 291–307.

20.

Lancichinetti

Fortunato

Radicchi

(2008) Benchmark graphs for testing community detection algorithms. Physical Review E Statistical Nonlinear and Soft Matter Physics 78(4 Pt 2): 046110.

21.

Lusseau

Schneider

Boisseau

et al . (2003) The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology 54(4): 396–405.

22.

Newman

MEJ

(2003) The structure and function of complex networks. Siam Review 45(2): 167–256.

23.

Newman

MEJ

(2004) Fast algorithm for detecting community structure in networks. Physical Review E Statistical Nonlinear and Soft Matter Physics 69(6 Pt 2): 066133.

24.

Newman

MEJ

(2006) Finding community structure in networks using the eigenvectors of matrices. Physical Review E Statistical Nonlinear and Soft Matter Physics 74(3 Pt 2): 036104.

25.

Pizzuti

(2012) A multiobjective genetic algorithm to find communities in complex networks. IEEE Transactions on Evolutionary Computation 16(3): 418–430.

26.

Shang

Bai

Jiao

et al . (2013) Community detection based on modularity and an improved genetic algorithm. Physica A Statistical Mechanics and Its Applications 392(5): 1215–1231.

27.

Watts

Strogatz

(1998) Collective dynamics of ‘small-world’ networks. Nature 393(6684): 440–442.

28.

Huberman

(2004) Finding communities in linear time: A physics approach. European Physical Journal B 38(2): 331–338.

29.

Zachary

(1977) An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33(4): 452–473.

30.

Zhan

Guan

Zhang

et al . (2013) Optimal tracking performance and design of networked control systems with packet dropouts. Journal of the Franklin Institute 350(10): 3205–3216.

31.

Zhang

(2007) MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11(6): 712–731.