82 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 18, NO. 1, FEBRUARY 2014
Complex Network Clustering by Multiobjective
Discrete Particle Swarm Optimization
Based on Decomposition
Maoguo Gong, Member, IEEE, Qing Cai, Xiaowei Chen, and Lijia Ma
Abstract—The field of complex network clustering has been
very active in the past several years. In this paper, a discrete
framework of the particle swarm optimization algorithm is
proposed. Based on the proposed discrete framework, a mul-
tiobjective discrete particle swarm optimization algorithm is
proposed to solve the network clustering problem. The decom-
position mechanism is adopted. A problem-specific population
initialization method based on label propagation and a turbulence
operator are introduced. In the proposed method, two evaluation
objectives termed as kernel k-means and ratio cut are to be
minimized. However, the two objectives can only be used to
handle unsigned networks. In order to deal with signed networks,
they have been extended to the signed version. The clustering
performances of the proposed algorithm have been validated on
signed networks and unsigned networks. Extensive experimental
studies compared with ten state-of-the-art approaches prove that
the proposed algorithm is effective and promising.
Index Terms—Clustering, complex networks, evolutionary
algorithm, multiobjective optimization, particle swarm
optimization.
I. Introduction
A. Complex Network Clustering
R
ECENT years have witnessed an enormous interest in
complex networks, since many complex systems, includ-
ing collaboration networks [1], the World Wide Web [2], [3],
and neural networks [4], can be modeled as complex networks.
The task of network clustering is to partition a complex
network into several groups, which hold the conditions that,
for an unsigned network, connections between the nodes in
the same group are dense and connections between different
groups are sparse; for a signed network, links both within and
between groups are dense. Such a group is called a community,
a cluster, or a module [5]. Network clustering is essential
for understanding how a network is organized and also to
understand its functions. A number of network clustering
Manuscript received November 15, 2012; revised March 7, 2013; accepted
April 20, 2013. Date of publication April 30, 2013; date of current version
January 27, 2014. This work was supported in part by the National Natural
Science Foundation of China under Grant 61273317, the National Top Youth
Talents Support Program of China, and the Fundamental Research Fund for
the Central Universities under Grants K50510020001 and K5051202053.
The authors are with the Key Laboratory of Intelligent Perception and Image
Understanding of Ministry of Education, Xidian University, Xi’an, Shaanxi
Province 710071, China (e-mail: gong@ieee.org; 506183509@qq.com;
xiaowei7002@126.com; 723816009@qq.com).
Color versions of one or more of the figures in this paper are available
online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TEVC.2013.2260862
techniques have been developed over the last decade. A recent
survey can be found in [5].
Naturally, network clustering can be modeled as an op-
timization problem [6]. Very often, such a problem is NP-
hard. For this reason, evolutionary algorithms (EAs) have
been used for network clustering. For example, Pizzuti [7]
has proposed a single objective genetic algorithm (GA-net)
for network clustering, and Gong et al. [8] have suggested a
memetic algorithm-based network clustering method (Meme-
net). In some applications, it is desirable to consider several
conflicting objectives at the same time in network clustering.
Therefore, multiobjective evolutionary algorithms can also find
their niche in this area. Several multiobjective evolutionary
network clustering methods, such as MOGA-net [9], MOCD
[10], and MOEA/D-net [11], have recently been proposed.
B. Multiobjective Evolutionary Algorithm and Particle Swarm
Optimization
Multiobjective evolutionary algorithms (MOEAs) aim at
producing a set of Pareto optimal solutions to a multiobjective
optimization problem in a single run. Due to their wide
applications, much effort has been devoted to MOEAs and
a number of MOEAs have been developed. Most current
MOEAs can be classified into three categories. The first one
is Pareto dominance based; the well-known algorithms in this
category are NSGA-II [12], SPEA2 [13], PAES [14], and
AMOSA [15]. The second category is performance indicator
based; the hypervolume is the most popular indicator used in
these algorithms. The third category is decomposition based;
these algorithms decompose a multiobjective optimization
problem (MOP) into a number of single objective subproblems
or simple multiobjective subproblems, and use a population
search method to solve these subproblems in a collaborate
way.
Particle swarm optimization (PSO), originally proposed
for single objective continuous optimization problems, is a
population based optimization method [16]. PSO works with
a population (i.e., swarm) of particles. Particles move in the
search space to find optimal solutions. A particle adjusts its
velocity before its movement according to some simple rules.
These rules, inspired by the movement of a bird flock or fish
school, make use of the best position visited by each particle
and the global best solution produced by the swarm to drive
particles to a promising region.
1089-778X
c
2013 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications
standards/publications/rights/index.html for more information.
