Finding a Maximum Clique using Ant Colony Optimization and Particle Swarm
Optimization in Social Networks

Mohammad Soleimani-Pouri

Alireza Rezvanian

Mohammad Reza Meybodi

Department of Electrical, Computer
and Biomedical Engineering, Qazvin
branch, Islamic Azad University,
Qazvin, Iran
m.soleimani@qiau.ac.ir

Computer and Information
Technology Engineering Department
Amirkabir University of Technology,
Tehran, Iran
a.rezvanian@aut.ac.ir

Computer and Information
Technology Engineering Department
Amirkabir University of Technology,
Tehran, Iran
mmeybodi@aut.ac.ir

Abstract—Interaction between users in online social networks
plays a key role in social network analysis. One on important
types of social group is full connected relation between some
users, which known as clique structure. Therefore finding a
maximum clique is essential for some analysis. In this paper,
we proposed a new method using ant colony optimization
algorithm and particle swarm optimization algorithm. In the
proposed method, in order to attain better results, it is
improved process of pheromone update by particle swarm
optimization. Simulation results on popular standard social
network benchmarks in comparison standard ant colony
optimization algorithm are shown a relative enhancement of
proposed algorithm.
Keywords- social network analysis; clique problem; ACO;
PSO.

I.

INTRODUCTION

Today online social networks are formed a new type of
life due to some facilities and services for a wide ranges of
ages such as young to old. There is no doubt about either
influence or growth of social networks. Therefore, several
many of researchers are focused on social network analysis
aspects. It seems to be useful, studying structure of relation
between users in social networks. One of the important user
group structure associated with a full connected of some
users, which known as clique structure [1]. Several
applications of finding clique are reported by researchers
such as social networks analysis [2], online shopping
recommendation [3] and evolution of social networks [12].
In literature, finding clique is categorized as NP-complete
problems in graph theory [4].
Evolutionary
algorithms
(EAs)
are
stochastic
optimization techniques based on the principles of natural
evolution which applied several NP problems [13-15] such
as clique problem. Various types of algorithms have been
presented to solve clique problem, while evolutionary
algorithms such as genetic algorithm (GA) and ant colony
optimization (ACO) have been used more. Popular algorithm
named Ant-clique algorithm, which make a maximal clique
using sequential greedy heuristics based on ant colony
optimization by adding vertices to the partial cliques
iteratively [5]. Besides, another ACO based method

hybridized by simulated annealing (SA) [6] and tabu search
[7]. Although new hybrid algorithm obtained good results,
they have a high complexity in practice.
In this study, Particle Swarm Optimization (PSO)
algorithm has been applied as the heuristic to enhance the
performance of ACO algorithm for finding a maximal clique
in social network graph. Simulation results on social network
benchmark are shown the better results in comparison with
standard ACO algorithm. In the rest of this paper, section II
and III are consisted of ACO and PSO introduction
respectively, in section IV, proposed method is discussed.
Simulation results on social networks datasets are reported in
section V.
II.

ANT COLONY OPTIMIZATION (ACO)

Ant Colony optimization (ACO) algorithm works well
for solving several discrete problems. The basic algorithm of
ACO was proposed by Dorigo as a multi agent approach in
order to solve traveling salesman problem (TSP) [8]. The
main idea of ACO algorithm is inspired from the behavior of
seeking out food by colonies of ants. Ants search their
environment randomly to find food. They return some of the
food to their nest once found a food and leave pheromone in
their return path. The amount of pheromone left on their path
depends on quality and size of the food source and it
evaporates gradually. Remaining pheromones will persuade
other ants to follow the path and just after a short time,
majority of the ants will trace the shorter path which is
marked with stronger pheromone. Procedure of ACO
algorithm has been presented in Figure 1.
Procedure ACO_MetaHeuristic
while(termination_conditions)
generateSolutions()
daemonActions() {Optional}
pheromoneUpdate()
end while
end procedure
Figure 1. Pseudo-code of ACO algorithm [9]

During running of the algorithm, ants first produce
different solutions randomly in the main loop after

initialization. Afterwards, the solutions are improved by
updating the pheromones and using a local search optionally.
According to the problem and graph traverse, pheromones
set on vertices or edges of graph. Traversing the edge
between vertices i and j depends on the probability of edge
which is calculated as below:

(τ )
∑ (τ )
α

p ijk =

ij

(1)

α

Where, pijk is probability of traversing the edge between
vertices i and j, while τijα is amount of pheromone present on
the above mentioned edge. An optional local search can
contribute to improvement of the results prior to updating the
pheromones. However, method of updating the pheromones
can be like this:

τ

= (1 − ρ )τ + Δτ
t
ij

t
ij

(2)

Where, ρ is evaporation rate of pheromone, τijt+1 is
amount of new pheromone for edge between i and j, τijt is
amount of current pheromone for edge between i and j, Δτijt
is amount of reinforced pheromone for proper solutions
which can be calculated from the following equation.

⎪⎧1
Δτ ijt = ⎨
⎪⎩0
III.

if

(

vi t +1 = wvit + c1r1 ( pbest it - x it ) + c2r2 gbest it - x ti
x it +1 = x it + v it

)

i = 1, ..., m

(4)
(5)

th

ij

t +1
ij

implementing the algorithm after finding the best local and
global values.

τ ijt ∈ good s olution
Otherwise

(3)

PARTICLE SWARM OPTIMIZATION (PSO)

Particle swarm optimization (PSO) is a population based
optimization technique developed by Eberhart and Kennedy
in 1995, which inspired from social behavior of birds
seeking for food. In this method, group of birds seek for food
in a specified space randomly. Birds follow the bird with the
shortest distance to food in order to find position of the food
[10].
Every solution in PSO algorithm which is called a
particle corresponds to a bird in their pattern of social
movement. Each particle has a value of fitness calculated by
a fitness function. A particle bears greater fitness once it is
located in a closer position to the target (food in the model of
moving birds) within search space. Moreover, any particle
represents a speed which is responsible to direct the particle.
A particle will keep going through the problem space by
following the optimum particle at current state [16].
A group of particles (solutions) are created randomly at
the beginning of particle swarm optimization algorithm and
they try to find the optimum solution through being updated
among generations. A particle is updated in each step using
the best local and global solution. The best position a particle
has ever succeeded to reach is called pbest and saved while
the best position achieved by the population of particles is
named gbest. Velocity and location of each particle will be
updated using Equations (4) and (5) in each step of

Where, vi is the velocity of i particle and xi is the current
position of it. r1 and r2 are random values in the range of
(0,1). c1 and c2 are learning parameters usually assumed
equal (c1=c2). w is inertia weight which is considered as a
constant or variable coefficient as random, linear, nonlinear
and adaptive [11]. PSO has been used in various applications
and this research utilizes it to improve amount of
pheromones.
IV.

PROPOSED ALGORITHM

High complexity was a major drawback of the previous
heuristic methods for solving the clique problem since it
significantly adds to the volume of calculations. All methods
provided so far apply the following relation to calculate Δτ
although the proposed algorithm take the advantage of PSO
algorithm to improve results and reduce complexity.
Δτ t +1 =

1
(1 + G -best - best-tour )

(6)

This algorithm has used the hybrid of ACO and PSO
algorithms in order to find the maximal clique in a graph. For
this purpose, some ants are placed initially on the graph and
follow paths to find the maximal clique. After evaporation of
existing pheromones, proper path is updated by its amount
on the edges using particle swarm optimization algorithm.
This procedure is repeated until the optimum clique is
obtained on the desired graph. Determining the amount of
pheromone through PSO is such that the total pheromone
measured at this step and the total pheromone associated
with the best answer up to present step will be calculated
taking into account the amount of pheromones at current
step. Now, Δτ for the reinforced pheromone of the desired
clique will be calculated with PSO algorithm using the
following equation:

Δτ t +1 = Δτ t +V

t

(7)

Where, Δτijt is amount of reinforcement for current
pheromone and Δτijt+1 is amount of reinforcement for new
pheromone, while Vt gives the amount of change which can
be achieved from this equation:

V t +1 = c1r1 (pτ - Δτ) + c 2 r2 (gτ - Δτ) + c3 V t

(8)

Where, Vt+1 is the new value of Vt. r1 and r2 are two
random values within range of (0,1), while c1, c2 and c3 are
learning parameters (c1=c2=c3). pτ and gτ are considered as
the pheromone correspondent with the best current clique
and the best clique found so far, respectively. In this case,

discovering the changed amount of pheromone will be
implemented much more intelligent.
Taking into consideration the mentioned items, general
routine of proposed the algorithm can be summarized as
below:
1. Initialize the parameters
2. Repeat steps 3 to 5 until reaching conditions of
termination
3.
4.
5.
6.

Traverse the graph by ants and create sub-graphs as
clique
Evaluate the obtained cliques
Update pheromones by PSO according to equation
(8)
End.
Figure 2. Zachary's karate club social network

V.

SIMULATION RESULTS

For evaluation of the proposed method, experiments applied
on some popular social network datasets. The description of
popular social networks is listed in the table 1.
TABLE I.
I
II
III
IV
V
VI
VII
VIII
IX
X
XI
XII

SOCIAL NETWORKS DESCRIPTIONS

Dataset
Zachary's karate club
Common adjective and nouns
in "David Copperfield"
Neural network
of
the
nematode C. Elegans
social network of dolphins,
Doubtful Sound, New Zealand
Pajek
network:
Erdos
collaboration network 971
Pajek
network:
Erdos
collaboration network 991
Pajek network: World Soccer,
Paris 1998
Pajek network: graph and
digraph glossary
Pajek network: Slovenian
journals 1999-2000
co-authoship of scientists in
network theory & experiments
Pajek
network:
SmaGri
citation network
email interchange network,
Univ. of Rovira i Virgili,
Tarragona

Nodes
34

Edges
78

112

425

297

8479

62

159

472

1314

492

1417

35

295

72

118

124

823168

1589

1190

1059

4919

1133

5451

Topology of zachary’s karate club and social network of
dolphins are presented in figure 2 and 3 respectively as the
most popular of the social network datasets.

Figure 3. Dolphins social network

The setting of parameters for experiment is listed in
below. It is noted that choosing different values for
improving the results is also possible.
In this paper has used 30 ants with ρ=0.95, Φ=0.0002,
Δτinitial=0, τmin=0.01, τmax=6.
Meanwhile, parameters of PSO were initialized as V=0,
c1=c3=0.3, and c2=1-c1. α and ρ were given the following
values based on the experiments done and t is the number of
iterations.
⎧1
⎪2
⎪
α (t ) = ⎨
⎪3
⎪⎩4

t ≤ 100

⎫
100 < t ≤ 400 ⎪⎪
⎬
400 < t ≤ 800 ⎪
t > 800
⎭⎪

⎧(1-ϕ )ρ (t)
⎩0.95 if ρ (t)>0.95

ρ (t + 1) = ⎨

(9)

(10)

Average of 10 independent runs with 1000 iterations for
each implementation have been listed in table 2 and table 3
for proposed method (ACO-PSO) and ACO algorithm
respectively, including the maximum (Best), average (Avg),

standard deviation (Std) and run-time of algorithm for
finding a maximum clique in each graph datasets.
TABLE II.

REFERENCES
[1]

SIMULATION RESULTS OF ACO-PSO FOR FINDING A
MAXIMUM CLIQUE

Graph
I
II
III
IV
V
VI
VII
VIII
IX
X
XI
XII
TABLE III.

Best
5
5
7
5
7
7
5
4
4
3
8
12

Avg
4.995
4.783
5.543
4.998
5.848
6.011
4.118
3.985
3.185
2.253
6.409
7.997

Std
0.070
0.412
1.482
0.044
0.6673
0.819
0.322
0.121
0.299
0.371
0.765
2.241

[2]
Run-time
11.84
23.37
49.47
15.69
105.11
111.89
10.742
12.94
22.07
118.59
481.34
529.04

SIMULATION RESULTS OF ACO FOR FINDING A
MAXIMUM CLIQUE

Graph
I
II
III
IV
V
VI
VII
VIII
IX
X
XI
XII

Best
5
5
7
5
7
7
5
4
4
3
8
12

Avg
4.991
4.709
5.521
4.991
8.753
5.961
3.910
3.943
3.017
2.175
6.025
7.562

Std
0.082
0.495
1.568
0.094
0.861
0.924
0.293
0.232
0.316
0.434
0.815
2.374

Run-time
64.03
355.81
1121.71
132.12
5853.59
6281.35
55.15
153.66
438.87
2142.03
9153.65
11109.17

Table 2 and table 3 indicate that the proposed method
(ACO-PSO) produces better results in comparison with ACO
method since the proposed approach is an appropriate
method to update pheromones of the traversed paths for ants
in calculating the optimum clique.
VI. CONCLUSION
A new hybrid algorithm has been presented in this paper
using ACO and PSO (ACO-PSO) for finding a maximum
clique in social networks. Traditional algorithms suffered
high complexity while the hybrid proposed algorithm just
change the process of update pheromone. It has been shown
that the new algorithm was able to improve the basic ACO
algorithm as simply and quickly. Simulation results on
popular social networks datasets indicate the improved
results for proposed algorithm in comparison with the ACO
algorithm.

[3]

[4]
[5]

[6]

[7]

[8]
[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

D. Easley, and J. Kleinberg, Networks, Crowds, and Markets:
Reasoning About a Highly Connected World. Cambridge University
Press, 2010.
S. Sadi, S. O g u du cu , and A. Uyar, “An efficient community
detection method using parallel clique-finding ants,” Proc. 2010 IEEE
Congress on Evolutionary Computation (CEC 2010), IEEE Press,
July 2010, pp. 1-7, doi: 10.1109/CEC.2010.5586496.
Q. Yang, P. Zhou, H. Zhang, and J. Zhang, “Clique Discovery Based
on User Similarity for Online Shopping Recommendation,”
Information Technology Journal, vol. 10, pp. 1587-1593, 2011.
J. Kleinberg, and E. Tardos, Algorithm Design. Addison Wesley,
2005.
S. Fenet, and C.Solnon, “Searching for Maximum Cliques with Ant
Colony Optimization,” Applications of Evolutionary Computing,
LNCS 2611, pp. 236-245, 2003.
X.Xu, J.Ma, and J. Lei, “An Improved Ant Colony Optimization for
the Maximum Clique Problem,” Proc. Third International Conference
on Natural Computation (ICNC 2007), IEEE Press, Aug. 2007, pp.
766-770, doi: 10.1109/ICNC.2007.205.
M.Al-Fayoumi, S.Banerjee, and P. K. Mahanti, “Analysis of Social
Network Using Clever Ant Colony Metaphor,” World Academy of
Science, Engineering and Technology, vol. 5, pp. 970-974, 2009.
E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm intelligence.
Oxford University Press, 1999.
K. Socha, and M. Dorigo, “Ant colony optimization for continuous
domains,” European Journal of Operational Research, vol. 185, no. 3,
pp. 1155-1173, 2008.
J. Kennedy, and R.C. Eberhart, “Particle Swarm Optimization,” Proc.
IEEE International Conference on Neural Networks (ICNN 1995),
IEEE
Press,
Nov/Dec.
1995,
pp.
1942-1948,
doi:
10.1109/ICNN.1995.488968.
S. Nabizadeh, K. Faez, S. Tavassoli, and A. Rezvanian, “A novel
method for multi-level image thresholding using particle swarm
Optimization algorithms,” Proc. 2010 2nd International Conference
on Computer Engineering and Technology (ICCET 2010), IEEE
Press,
Apr.
2010,
pp.
V4-271-V4-275,
doi:
10.1109/ICCET.2010.5485600.
F. Yan, S. Cai, M. Zhang, G. Liu, and Z. Deng, “A cliquesuperposition model for social networks,” Science China Information
Sciences, pp. 1-19, 2012. doi: 10.1007/s11432-011-4526-y, In press.
A. Rezvanian, and M. R. Meybodi, “An adaptive mutation operator
for artificial immune network using learning automata in dynamic
environments,” 2010 Second World Congress on Nature and
Biologically Inspired Computing (NaBIC 2010), Dec. 2010, pp. 479483, doi: 10.1109/NABIC.2010.5716360.
A. Rezvanian, and M. R. Meybodi, “Tracking Extrema in Dynamic
Environments Using a Learning Automata-Based Immune
Algorithm,” Grid and Distributed Computing, Control And
Automation, Communications in Computer and Information Science,
2010, vol. 121, pp. 216-225, doi: 10.1007/978-3-642-17625-8_22.
A. Rezvanian, and M. R. Meybodi, “LACAIS: Learning Automata
Based Cooperative Artificial Immune System for Function
Optimization,” Contemporary Computing, Communications in
Computer and Information Science, 2010, vol. 94, pp. 64-75, doi:
10.1007/978-3-642-14834-7_7.
A. B. Hashemi, and M. R. Meybodi, “A note on the learning automata
based algorithms for adaptive parameter selection in PSO,” Applied
Soft Computing, vol. 11, no. 1, pp. 689-705, 2011.

