# Moving Clusters within a Memetic Algorithm for Graph Partitioning

Authors: Inwook Hwang; Yong-Hyuk Kim; Yourim Yoon
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Most memetic algorithms (MAs) for graph partitioning reduce the cut size of partitions using iterative improvement. But this local process considers one vertex at a time and fails to move clusters between subsets when the movement of any single vertex increases cut size, even though moving the whole cluster would reduce it. A new heuristic identifies clusters from the population of locally optimized random partitions that must anyway be created to seed the MA, and as the MA runs it makes beneficial cluster moves. Results on standard benchmark graphs show significant reductions in cut size, in some cases improving on the best result in the literature.


---

## Body

## 1. Introduction

Consider an unweighted undirected graphG
=
(
V
,
E
), where V is a set of n vertices, and E is the set of edges that connect them. A k
-way partition
{
P
1
,
P
2
,
…
,
P
k
} of the graph G is a partitioning of the vertex set V into k disjoint subsets. A partition is said to bebalanced if the difference in size between the largest and the smallest subset is at most 1, that is, for all 1
≤
i
,
j
≤
k,  P
i
-
P
j
≤
1. Thecut size of a partition is defined to be the number of edges connecting vertices in different subsets of the partition. The k
-way graph partitioning problem is the problem of finding a balanced k-way partition with the minimum cut size. If k
=
2, it can be called bipartitioning and if k
>
2, multiway partitioning. These problems arise in applications such as sparse matrix factorization, network partitioning, layout and floor planning, circuit placement, social network analysis, and software-defined networking [1, 2].For general graphs, partitioning is known to be NP-hard [3]. Bui and Jones [4] have shown that even finding good approximate solutions is also NP-hard.Therefore, many heuristic methods have been proposed: some of them work well, but they cannot of course guarantee optimality. The simplest heuristic is iterative improvement partitioning (IIP) [5, 6], exemplified by the Kernighan-Lin (KL) [7] and the Fiduccia-Mattheyses (FM) algorithms [8], but these algorithms only produce solutions which are approximations tolocal optima; however, this limitation can be overcome by hybridizing them with metaheuristics, such as simulated annealing [9], genetic algorithms (GAs) [10], tabu search [11, 12], or ant colony optimization [13]. Recently, a number of techniques based on GAs have achieved notable results for k
=
2 [14–19] and k
>
2 [20–26]. Kim et al. [27] have surveyed this work.The use of IIP for local optimization of partitioning produced by a GA becomes less effective as the graph becomes larger. We will show that this is because IIP often fails to move densely interconnected subgraphs, calledclusters, between partitions, and hence fails to find partitions with small cut sizes.The goal of the work reported in this paper is to overcome the barriers to effective search which are presented by clusters, by modifying the GA so that it contributes to move clusters appropriately. We present a memetic algorithm (MA), which is a GA combined with local optimization, in which a heuristic finds clusters in some of the positions in each generation, by examining population of individuals, each of which represents a position, rather than trying to identify them directly from a single graph. It moves some of these clusters. This heuristic supplements the well-known ability of MAs to provide attractive initial points for local optimization. Experimental results show that this approach can substantially improve the performance of an MA. The contributions of this work are summarized as follows.(i)
We provide a detailed explanation of the difficulty of moving clusters in graph partitioning and provide experimental results quantifying the impact of clusters on the search for partitions with a small cut size.
(ii)
We present a heuristic for detecting and moving clusters, which is based on a new, population-based, measure of the distance between vertices calledgenic distance.
(iii)
We show that this heuristic substantially improves the ability of an MA to find good partitions.The remainder of this paper is organized as follows. In Section2 we briefly introduce IIP algorithms and the test graphs used in our experiments. In Section 3 we investigate the difficulty of moving clusters in graph partitioning. In Section 4 we describe our new cluster-handling heuristic, and an MA that uses this heuristic is described in Section 5. In Section 6 we present experimental results, and draw conclusions in Section 7.


## 2. Preliminaries

### 2.1. Iterative Improvement Algorithms in Bipartitioning

Iterative improvement partitioning starts with a random partition. This is refined in a series of passes. At the start of each pass, all the vertices are free to move between subsets. IIP selects vertices and moves them, but each vertex is only moved once during a pass. At the end of the pass, the best partition found during the pass is identified and used as the input to the next pass. Passes continue until there is no further improvement.There are a number of IIP algorithms, of which KL [7] is often considered to be the first reasonable heuristic for bipartitioning. In KL, the movement of vertices during a pass is restricted to the swapping of a pair of vertices between subsets.Let{
A
,
B
} be a partition of V into two subsets A and B. We define the gain g
v associated with a vertex v to be the reduction in cut size obtained by moving v to the other subset. By extension, the gain g
(
a
,
b
) obtained by swapping vertices a
∈
A and b
∈
B can be expressed as follows:(1)
g
a
,
b
=
g
a
+
g
b
-
2
δ
a
,
b
,where(2)
δ
a
,
b
=
1
,
i
f
a
,
b
∈
E
,
0
,
o
t
h
e
r
w
i
s
e
. KL selects the pair (
a
,
b
) with the highest value of g
(
a
,
b
) and effects the exchange. The vertices a and b are not considered again during the current pass. A sequence of pairs (
a
1
,
b
1
)
,
(
a
2
,
b
2
)
,
…
,
(
a
n
/
2
-
1
,
b
n
/
2
-
1
) are selected in this way. The algorithm chooses l that maximizes ∑
i
=
1
l
‍
g
(
a
i
,
b
i
) and exchanges {
a
1
,
a
2
,
…
,
a
l
} and {
b
1
,
b
2
,
…
,
b
l
}. KL performs further passes until no improvement is possible.FM is another widely used IIP algorithm, which is similar to KL, except that it only moves one vertex at a time. This makes FM faster than KL, with little loss in partition quality. Several variants of KL and FM exist [15, 28, 29].


### 2.2. Local Optimization Algorithms for Multiway Partitioning

There are three main schemes for multiway partitioning, which are developments of the recursive, pair-wise, and direct approaches [21] to bipartitioning. The recursive KL algorithm bisects the graph recursively until there are k subsets. The pair-wise KL [7] starts with an arbitrary k-way partition. It picks two subsets at a time from the k subsets and performs bipartitioning to reduce the cut size between those pairs. Sanchis [30] extended the FM algorithm to multiway partitioning and showed that the direct method performed better than recursion. The extended algorithm considers moving each vertex from its current subset to every other subset. To perform local optimization in the proposed MA for multiway partitioning, we use a variant of this algorithm, called EFM (extended FM) [21]. The time complexity of EFM is O
(
k
|
E
|
).


### 2.3. Local Search in Memetic Algorithms

It is already clear that combining a GA with local optimization algorithms is an effective approach to the graph partitioning problem [15]. Some authors have explored fast but weak local optimization algorithms. For example [31, 32], 2-opt was used to relocate border vertices, which are those with edges that connect to vertices in other subsets. Bui and Moon [10] obtained better results with KL by allowing only a single pass, while restricting the number of vertices to be swapped. Conversely, other authors have reported notable improvements by enhancing local optimization algorithms. For bipartitioning, Kim and Moon [15] suggested a new KL-based local optimization algorithm, formulated using a new type of gain, calledlock gain, which only takes into account the edges that connect a vertex to the vertices that have already been moved. Combined with a GA, this algorithm obtained impressive results on most benchmark graphs. For multiway partitioning, the combination of MAs with specialized local optimization algorithms showed good results [20, 21]. Steenbeek et al. [18] proposed what they called a cluster enhancement heuristic, which they combined with an MA, and reported successful results. Their MA uses a vertex swap heuristic to identify clusters. The MA only handles the moving of clusters between subsets.


### 2.4. Test Graphs

We tested our MA on Johnson’s benchmark graphs [9], which have been widely used in other studies [10, 11, 14–17, 20, 21, 23, 33–36]. They are composed of 8 random graphs Gn
.
d and 8 random geometric graphs Un
.
d. The two different classes of graphs are briefly described below.(i)
Gn
.
d: a random graph on n vertices, with an independent probability p that any two vertices are connected by an edge. The probability p is biased so that the expected vertex degree, p
(
n
-
1
), is d.
(ii)
Un
.
d: a random geometric graph on n vertices that lie in the unit square and whose coordinates are chosen uniformly from the unit interval. Every pair of vertices separated by a distance of t or less is connected by an edge. The expected degree of a vertex is n
π
t
2.


## 2.1. Iterative Improvement Algorithms in Bipartitioning

Iterative improvement partitioning starts with a random partition. This is refined in a series of passes. At the start of each pass, all the vertices are free to move between subsets. IIP selects vertices and moves them, but each vertex is only moved once during a pass. At the end of the pass, the best partition found during the pass is identified and used as the input to the next pass. Passes continue until there is no further improvement.There are a number of IIP algorithms, of which KL [7] is often considered to be the first reasonable heuristic for bipartitioning. In KL, the movement of vertices during a pass is restricted to the swapping of a pair of vertices between subsets.Let{
A
,
B
} be a partition of V into two subsets A and B. We define the gain g
v associated with a vertex v to be the reduction in cut size obtained by moving v to the other subset. By extension, the gain g
(
a
,
b
) obtained by swapping vertices a
∈
A and b
∈
B can be expressed as follows:(1)
g
a
,
b
=
g
a
+
g
b
-
2
δ
a
,
b
,where(2)
δ
a
,
b
=
1
,
i
f
a
,
b
∈
E
,
0
,
o
t
h
e
r
w
i
s
e
. KL selects the pair (
a
,
b
) with the highest value of g
(
a
,
b
) and effects the exchange. The vertices a and b are not considered again during the current pass. A sequence of pairs (
a
1
,
b
1
)
,
(
a
2
,
b
2
)
,
…
,
(
a
n
/
2
-
1
,
b
n
/
2
-
1
) are selected in this way. The algorithm chooses l that maximizes ∑
i
=
1
l
‍
g
(
a
i
,
b
i
) and exchanges {
a
1
,
a
2
,
…
,
a
l
} and {
b
1
,
b
2
,
…
,
b
l
}. KL performs further passes until no improvement is possible.FM is another widely used IIP algorithm, which is similar to KL, except that it only moves one vertex at a time. This makes FM faster than KL, with little loss in partition quality. Several variants of KL and FM exist [15, 28, 29].


## 2.2. Local Optimization Algorithms for Multiway Partitioning

There are three main schemes for multiway partitioning, which are developments of the recursive, pair-wise, and direct approaches [21] to bipartitioning. The recursive KL algorithm bisects the graph recursively until there are k subsets. The pair-wise KL [7] starts with an arbitrary k-way partition. It picks two subsets at a time from the k subsets and performs bipartitioning to reduce the cut size between those pairs. Sanchis [30] extended the FM algorithm to multiway partitioning and showed that the direct method performed better than recursion. The extended algorithm considers moving each vertex from its current subset to every other subset. To perform local optimization in the proposed MA for multiway partitioning, we use a variant of this algorithm, called EFM (extended FM) [21]. The time complexity of EFM is O
(
k
|
E
|
).


## 2.3. Local Search in Memetic Algorithms

It is already clear that combining a GA with local optimization algorithms is an effective approach to the graph partitioning problem [15]. Some authors have explored fast but weak local optimization algorithms. For example [31, 32], 2-opt was used to relocate border vertices, which are those with edges that connect to vertices in other subsets. Bui and Moon [10] obtained better results with KL by allowing only a single pass, while restricting the number of vertices to be swapped. Conversely, other authors have reported notable improvements by enhancing local optimization algorithms. For bipartitioning, Kim and Moon [15] suggested a new KL-based local optimization algorithm, formulated using a new type of gain, calledlock gain, which only takes into account the edges that connect a vertex to the vertices that have already been moved. Combined with a GA, this algorithm obtained impressive results on most benchmark graphs. For multiway partitioning, the combination of MAs with specialized local optimization algorithms showed good results [20, 21]. Steenbeek et al. [18] proposed what they called a cluster enhancement heuristic, which they combined with an MA, and reported successful results. Their MA uses a vertex swap heuristic to identify clusters. The MA only handles the moving of clusters between subsets.


## 2.4. Test Graphs

We tested our MA on Johnson’s benchmark graphs [9], which have been widely used in other studies [10, 11, 14–17, 20, 21, 23, 33–36]. They are composed of 8 random graphs Gn
.
d and 8 random geometric graphs Un
.
d. The two different classes of graphs are briefly described below.(i)
Gn
.
d: a random graph on n vertices, with an independent probability p that any two vertices are connected by an edge. The probability p is biased so that the expected vertex degree, p
(
n
-
1
), is d.
(ii)
Un
.
d: a random geometric graph on n vertices that lie in the unit square and whose coordinates are chosen uniformly from the unit interval. Every pair of vertices separated by a distance of t or less is connected by an edge. The expected degree of a vertex is n
π
t
2.


## 3. Difficulty of Moving Clusters

Suppose that the cluster shown in Figure1(a) is involved in a bipartitioning problem. The four vertices in this cluster are fully interconnected, and they all belong to the same subset. Moving this cluster to the other subset, across the dotted line in Figure 1(b) will reduce the cut size of the partition by 4. However, there is no motivation to move any single vertex, because they all have negative gain: the gains of v
1, v
2, v
3, and v
4 are −1, −4, −2, and −1, respectively. This example illustrates how IIP algorithms may miss a significant reduction in cut size that could be achieved by moving several vertices together.Figure 1
An example of cluster moving, in which the cut size of a partition is reduced by 4.
(a)
Before moving a cluster
(b)
After moving a clusterThe baleful effect of clusters on local search algorithms trying to solve the graph partitioning problem motivated this study. Kim [37, 38] indicated that graph partitioning is hard primarily due to the difficulty of moving clusters. Dutt and Deng [39, 40] have also observed that an IIP method applied to circuit partitioning can fail because of the difficulty of dealing with clusters that straddle subsets.


### 3.1. Experimental Support

We designed experiments to quantify the effect of clusters on IIP algorithms, represented by the KL algorithm. Using the cluster detection method to be described in Section4.1, we find clusters in the graph and select one randomly. We then take a locally optimum bipartition s obtained by KL and move the selected cluster to the other subset, creating a perturbed partition t
c
l
u
s
t
e
r. Applying KL to t
c
l
u
s
t
e
r, we obtain a new local optimum u
c
l
u
s
t
e
r.Assuming thatq, the number of vertices in the clusters, is small, u
c
l
u
s
t
e
r can be expected to match s if KL is successful in moving the cluster back. However, if KL fails to return the perturbed cluster to its original subset, the cut size of the partition may increase. Repeating this experiment, we derive P
c
l
u
s
t
e
r, as an approximation of the probability that the cut size of u
c
l
u
s
t
e
r is larger than that of s.For comparison, we perturbedq vertices randomly selected within a locally optimized partition, by moving them to the other subset. We call this partition t
r
a
n
d
o
m. We apply the KL algorithm to t
r
a
n
d
o
m and then obtain a new locally optimum partition u
r
a
n
d
o
m. Repeating this experiment, we derive P
r
a
n
d
o
m, as an approximation of the probability that the cut size of u
r
a
n
d
o
m is larger than that of s.Table1 shows the values of P
c
l
u
s
t
e
r and P
r
a
n
d
o
m for 16 benchmark graphs. We see that P
c
l
u
s
t
e
r is always larger than P
r
a
n
d
o
m, as we would expect. We notice that the gap between P
c
l
u
s
t
e
r and P
r
a
n
d
o
m is larger on the geometric graphs (Un
.
d) than on the random graphs (Gn
.
d).Table 1
Probability that KL fails to return vertices moved from one subset of a partition to the other, when the vertices are in cluster (P
cluster) or chosen at random (P
random), over 1,000 runs.
Graph
P
cluster (%)
P
random (%)
Average number of vertices moved (q)
G500.2.5
16.90
2.50
6.41
G500.05
5.70
1.30
5.50
G500.10
1.90
0.30
5.05
G500.20
0.50
0.10
4.78
G1000.2.5
12.80
1.90
5.89
G1000.05
2.90
0.80
5.61
G1000.10
0.60
0.20
4.67
G1000.20
0.30
0.00
4.91
U500.05
39.10
1.00
7.41
U500.10
26.20
0.50
12.05
U500.20
8.60
0.20
14.10
U500.40
10.40
0.40
49.36
U1000.05
37.90
0.80
7.81
U1000.10
28.50
0.60
12.47
U1000.20
11.60
0.10
22.19
U1000.40
9.10
0.40
35.88


## 3.1. Experimental Support

We designed experiments to quantify the effect of clusters on IIP algorithms, represented by the KL algorithm. Using the cluster detection method to be described in Section4.1, we find clusters in the graph and select one randomly. We then take a locally optimum bipartition s obtained by KL and move the selected cluster to the other subset, creating a perturbed partition t
c
l
u
s
t
e
r. Applying KL to t
c
l
u
s
t
e
r, we obtain a new local optimum u
c
l
u
s
t
e
r.Assuming thatq, the number of vertices in the clusters, is small, u
c
l
u
s
t
e
r can be expected to match s if KL is successful in moving the cluster back. However, if KL fails to return the perturbed cluster to its original subset, the cut size of the partition may increase. Repeating this experiment, we derive P
c
l
u
s
t
e
r, as an approximation of the probability that the cut size of u
c
l
u
s
t
e
r is larger than that of s.For comparison, we perturbedq vertices randomly selected within a locally optimized partition, by moving them to the other subset. We call this partition t
r
a
n
d
o
m. We apply the KL algorithm to t
r
a
n
d
o
m and then obtain a new locally optimum partition u
r
a
n
d
o
m. Repeating this experiment, we derive P
r
a
n
d
o
m, as an approximation of the probability that the cut size of u
r
a
n
d
o
m is larger than that of s.Table1 shows the values of P
c
l
u
s
t
e
r and P
r
a
n
d
o
m for 16 benchmark graphs. We see that P
c
l
u
s
t
e
r is always larger than P
r
a
n
d
o
m, as we would expect. We notice that the gap between P
c
l
u
s
t
e
r and P
r
a
n
d
o
m is larger on the geometric graphs (Un
.
d) than on the random graphs (Gn
.
d).Table 1
Probability that KL fails to return vertices moved from one subset of a partition to the other, when the vertices are in cluster (P
cluster) or chosen at random (P
random), over 1,000 runs.
Graph
P
cluster (%)
P
random (%)
Average number of vertices moved (q)
G500.2.5
16.90
2.50
6.41
G500.05
5.70
1.30
5.50
G500.10
1.90
0.30
5.05
G500.20
0.50
0.10
4.78
G1000.2.5
12.80
1.90
5.89
G1000.05
2.90
0.80
5.61
G1000.10
0.60
0.20
4.67
G1000.20
0.30
0.00
4.91
U500.05
39.10
1.00
7.41
U500.10
26.20
0.50
12.05
U500.20
8.60
0.20
14.10
U500.40
10.40
0.40
49.36
U1000.05
37.90
0.80
7.81
U1000.10
28.50
0.60
12.47
U1000.20
11.60
0.10
22.19
U1000.40
9.10
0.40
35.88


## 4. Cluster-Handling Heuristic

Cluster analysis is a well-known problem for which plenty of algorithms exist, many of which require a lot of computation. The insight that motivates our heuristic is that the application of a local optimization process, such as IIP, to a randomly partitioned graph creates a modified partition in which clusters tend to be wholly allocated to one subset or another (and are then difficult to move, as we have already observed). A single partition of this sort is of little help in identifying clusters, because the clusters are not separated at all within each subset; but if we create many random partitions and optimize them, we can reasonably infer that vertices that find themselves in the same subset in most of these partitions belong to the same cluster. We can make this inference in a structured way using the “genic distance” metric that we will introduce. This approach to cluster analysis may seem indirect, but it is efficient in the context of an evolutionary approach to graph partitioning, because the set of partitions required for finding clusters using genic distance is also the population which we must create to be evolved by our MA.One way of dealing with clusters is to devise a local optimization heuristic that can identify clusters [18, 19, 38]. However, this prevents us from building on previous studies of IIP algorithms.Our approach is to add an additional heuristic to our MA, which finds and moves clusters. The heuristic identifies clusters in the population of partitions which have already been optimized locally. It selects clusters with higher gains and moves them. IIP local optimization is then applied again.


### 4.1. Cluster Detection

LetI
(
·
) be anindicator function, that is, I
(
t
r
u
e
)
=
1 and I
(
f
a
l
s
e
)
=
0. Then, we can trivially establish the following.Fact 1.
Ifp
→
q is true, then I
(
p
)
≤
I
(
q
).Proof.
From Table2.Table 2
Truth table for Fact1.
p
q
p
→
q
I
(
p
)
I
(
q
)
True
True
True
1
1
True
False
False
1
0
False
True
True
0
1
False
False
True
0
0Fact 2.
I
(
p
∨
q
)
≤
I
(
p
)
+
I
(
q
).Proof.
From Table3.Table 3
Truth table for Fact2.
p
q
I
(
p
)
I
(
q
)
p
∨
q
I
(
p
∨
q
)
I
(
p
) + I
(
q
)
True
True
1
1
True
1
2
True
False
1
0
True
1
1
False
True
0
1
True
1
1
False
False
0
0
False
0
0We now define a metric calledgenic distance, which measure the extent to which two vertices connected by an edge can be considered to belong to the same cluster. We denote the genic distance of an edge {
v
i
,
v
j
} within a population {
p
1
,
p
2
,
…
,
p
m
} of locally optimized partitions as d
g
(
v
i
,
v
j
), which can be expressed as follows: (3)
d
g
v
i
,
v
j
:
=
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
j
,where g
i and g
j are the genes corresponding to v
i and v
j, respectively. The value of gene g
i (i.e., the partition number that vertex v
i belongs to) in the lth individual is p
l
(
g
i
). For convenience, we assume that each vertex has an edge that connects it to itself, so that {
v
,
v
}
∈
E for each vertex v. Then, the following proposition holds.Proposition 1.
For each population,d
g becomes a pseudometric on V.Proof.
SinceI
(
·
)
≥
0, d
g
(
v
i
,
v
j
)
=
∑
l
=
1
m
‍
I
(
p
l
(
g
i
)
≠
p
l
(
g
j
)
)
≥
0 for each {
v
i
,
v
j
}
∈
E. It is enough to show the following three conditions.(i)
d
g
(
v
i
,
v
i
)
=
0: (4)
d
g
v
i
,
v
i
=
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
i
=
∑
l
=
1
m
‍
I
f
a
l
s
e
=
0
.
(ii)
Symmetry. Let {
v
i
,
v
j
} be in E: (5)
d
g
v
i
,
v
j
=
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
j
=
∑
l
=
1
m
‍
I
p
l
g
j
≠
p
l
g
i
=
d
g
v
j
,
v
i
.
(iii)
Triangle Inequality. Consider each group of three edges {
v
i
,
v
j
}
,
{
v
i
,
v
k
}
,
{
v
k
,
v
j
}
∈
E. If p
l
(
g
i
)
=
p
l
(
g
k
) and p
l
(
g
k
)
=
p
l
(
g
j
), then p
l
(
g
i
)
=
p
l
(
g
j
) for each l. By contraposition, if p
l
(
g
i
)
≠
p
l
(
g
j
), then p
l
(
g
i
)
≠
p
l
(
g
k
) or p
l
(
g
k
)
≠
p
l
(
g
j
).
For eachl, (6)
I
p
l
g
i
≠
p
l
g
j
≤
I
p
l
g
i
≠
p
l
g
k
∨
p
l
g
k
≠
p
l
g
j
∵
F
a
c
t
1
≤
I
p
l
g
i
≠
p
l
g
k
+
I
p
l
g
k
≠
p
l
g
j
∵
F
a
c
t
2
.
By summing the above inequalities for alll, (7)
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
j
≤
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
k
+
I
p
l
g
k
≠
p
l
g
j
=
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
k
+
∑
l
=
1
m
‍
I
p
l
g
k
≠
p
l
g
j
.
Therefore we have(8)
d
g
v
i
,
v
j
≤
d
g
v
i
,
v
k
+
d
g
v
k
,
v
j
.That is, d
g satisfies the triangle inequality.Proposition1 suggests that the measure d
g is reasonable. A pseudometric space is a generalization of a metric space, in which points need not be distinguishable; thus it is possible that d
g
(
v
i
,
v
j
)
=
0 for some edge {
v
i
,
v
j
}, with distinct vertices v
i
≠
v
j.Our heuristic detects clusters by collecting a number of local optima and computes genic distances for all the edges in each graph. This takesO
(
m
|
E
|
) time, but this cost is negligible since this computation is a preprocess performed before the MA runs. The heuristic temporarily eliminates edges with genic distances that are greater than a threshold value θ. We set θ to be the smallest value that satisfies (9)
e
∈
E
:
d
g
e
≤
θ
≤
0.1
V
. Each remaining connected component containing more than three vertices is considered to be acluster.Figure2 shows how our heuristic detects clusters. Figure 2(a) shows an example graph with 11 vertices and 15 edges. Four individuals, corresponding to locally optimized partitions, from the population are shown in Figure 2(b). In Figure 2(c), each edge is labeled with its genic distance. If the threshold value of genic distance is 1, then the edges with larger genic distances, indicated by dotted line, are eliminated. Then four connected components remain: {
v
3
,
v
7
,
v
8
,
v
9
}, {
v
2
,
v
4
,
v
6
,
v
11
}, {
v
1
,
v
5
}, and {
v
10
}. The last two of these connected components are considered too small to be clusters. Thus clusters {
v
3
,
v
7
,
v
8
,
v
9
} and {
v
2
,
v
4
,
v
6
,
v
11
}, shaded in Figure 2(c), remain as candidates for moving.Figure 2
An example of cluster detection.
(a)
Example graph
(b)
Four locally optimized partitions in the population (subsets 0 and 1)
(c)
Two detected clusters


### 4.2. Cluster-Moving Scheme

Our heuristic improves the offspring of each generation after crossover by moving the clusters that were detected using the technique described in the previous subsection. To select the clusters to be moved and their target subsets, we introduce a measure calledcluster gain, such that c
g
(
x
,
a
) is the reduction in the cut size of the partition when all the vertices in cluster x are moved to the subset a. For example, moving the cluster in Figure 1(a) to the other subset in the partition is associated with a cluster gain of 2.This cluster-moving scheme, described in Algorithm1, is applied to each individual generated by crossover, which is a partition that may be unbalanced. However, cut size and cluster gain are well defined on unbalanced partitions. Our scheme does not consider moving every cluster in every partition, because we found that making all clusters movable causes the premature convergence of the MA. Thus, our heuristic selects N clusters at random as candidates for moving. In our experiments, we set N to 5. We compute the cluster gain that results from moving each candidate cluster to each of the other k
-
1 subsets. The candidate cluster x and destination subset a with the highest cluster gain are selected. Assume that c
g
(
x
,
a
) is positive, all the vertices in cluster x are moved to subset a, and cluster x is removed from the set of candidate clusters. This process is repeated until no candidates remain, or no move yields a positive cluster gain. No attempt is made to balance the partition during cluster-moving; this is performed later.Algorithm 1:Our cluster-moving scheme.
Select clusters:S
←
N clusters selected at random;
do  {
Calculatecg
(
x
,
a
) for all x
∈
S
,
1
≤
a
≤
k;
c
g
∗
←
max
x
,
a
⁡
cg
(
x
,
a
);
(
x
¯
,
a
¯
)
←
arg
⁡
max
x
,
a
⁡
cg
(
x
,
a
);
if  c
g
∗
>
0  then  {
Move clusterx
¯ to partition a
¯;
S
←
S
∖
{
x
¯
};
}
}until  (S
=
∅ or c
g
∗
≤
0)


## 4.1. Cluster Detection

LetI
(
·
) be anindicator function, that is, I
(
t
r
u
e
)
=
1 and I
(
f
a
l
s
e
)
=
0. Then, we can trivially establish the following.Fact 1.
Ifp
→
q is true, then I
(
p
)
≤
I
(
q
).Proof.
From Table2.Table 2
Truth table for Fact1.
p
q
p
→
q
I
(
p
)
I
(
q
)
True
True
True
1
1
True
False
False
1
0
False
True
True
0
1
False
False
True
0
0Fact 2.
I
(
p
∨
q
)
≤
I
(
p
)
+
I
(
q
).Proof.
From Table3.Table 3
Truth table for Fact2.
p
q
I
(
p
)
I
(
q
)
p
∨
q
I
(
p
∨
q
)
I
(
p
) + I
(
q
)
True
True
1
1
True
1
2
True
False
1
0
True
1
1
False
True
0
1
True
1
1
False
False
0
0
False
0
0We now define a metric calledgenic distance, which measure the extent to which two vertices connected by an edge can be considered to belong to the same cluster. We denote the genic distance of an edge {
v
i
,
v
j
} within a population {
p
1
,
p
2
,
…
,
p
m
} of locally optimized partitions as d
g
(
v
i
,
v
j
), which can be expressed as follows: (3)
d
g
v
i
,
v
j
:
=
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
j
,where g
i and g
j are the genes corresponding to v
i and v
j, respectively. The value of gene g
i (i.e., the partition number that vertex v
i belongs to) in the lth individual is p
l
(
g
i
). For convenience, we assume that each vertex has an edge that connects it to itself, so that {
v
,
v
}
∈
E for each vertex v. Then, the following proposition holds.Proposition 1.
For each population,d
g becomes a pseudometric on V.Proof.
SinceI
(
·
)
≥
0, d
g
(
v
i
,
v
j
)
=
∑
l
=
1
m
‍
I
(
p
l
(
g
i
)
≠
p
l
(
g
j
)
)
≥
0 for each {
v
i
,
v
j
}
∈
E. It is enough to show the following three conditions.(i)
d
g
(
v
i
,
v
i
)
=
0: (4)
d
g
v
i
,
v
i
=
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
i
=
∑
l
=
1
m
‍
I
f
a
l
s
e
=
0
.
(ii)
Symmetry. Let {
v
i
,
v
j
} be in E: (5)
d
g
v
i
,
v
j
=
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
j
=
∑
l
=
1
m
‍
I
p
l
g
j
≠
p
l
g
i
=
d
g
v
j
,
v
i
.
(iii)
Triangle Inequality. Consider each group of three edges {
v
i
,
v
j
}
,
{
v
i
,
v
k
}
,
{
v
k
,
v
j
}
∈
E. If p
l
(
g
i
)
=
p
l
(
g
k
) and p
l
(
g
k
)
=
p
l
(
g
j
), then p
l
(
g
i
)
=
p
l
(
g
j
) for each l. By contraposition, if p
l
(
g
i
)
≠
p
l
(
g
j
), then p
l
(
g
i
)
≠
p
l
(
g
k
) or p
l
(
g
k
)
≠
p
l
(
g
j
).
For eachl, (6)
I
p
l
g
i
≠
p
l
g
j
≤
I
p
l
g
i
≠
p
l
g
k
∨
p
l
g
k
≠
p
l
g
j
∵
F
a
c
t
1
≤
I
p
l
g
i
≠
p
l
g
k
+
I
p
l
g
k
≠
p
l
g
j
∵
F
a
c
t
2
.
By summing the above inequalities for alll, (7)
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
j
≤
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
k
+
I
p
l
g
k
≠
p
l
g
j
=
∑
l
=
1
m
‍
I
p
l
g
i
≠
p
l
g
k
+
∑
l
=
1
m
‍
I
p
l
g
k
≠
p
l
g
j
.
Therefore we have(8)
d
g
v
i
,
v
j
≤
d
g
v
i
,
v
k
+
d
g
v
k
,
v
j
.That is, d
g satisfies the triangle inequality.Proposition1 suggests that the measure d
g is reasonable. A pseudometric space is a generalization of a metric space, in which points need not be distinguishable; thus it is possible that d
g
(
v
i
,
v
j
)
=
0 for some edge {
v
i
,
v
j
}, with distinct vertices v
i
≠
v
j.Our heuristic detects clusters by collecting a number of local optima and computes genic distances for all the edges in each graph. This takesO
(
m
|
E
|
) time, but this cost is negligible since this computation is a preprocess performed before the MA runs. The heuristic temporarily eliminates edges with genic distances that are greater than a threshold value θ. We set θ to be the smallest value that satisfies (9)
e
∈
E
:
d
g
e
≤
θ
≤
0.1
V
. Each remaining connected component containing more than three vertices is considered to be acluster.Figure2 shows how our heuristic detects clusters. Figure 2(a) shows an example graph with 11 vertices and 15 edges. Four individuals, corresponding to locally optimized partitions, from the population are shown in Figure 2(b). In Figure 2(c), each edge is labeled with its genic distance. If the threshold value of genic distance is 1, then the edges with larger genic distances, indicated by dotted line, are eliminated. Then four connected components remain: {
v
3
,
v
7
,
v
8
,
v
9
}, {
v
2
,
v
4
,
v
6
,
v
11
}, {
v
1
,
v
5
}, and {
v
10
}. The last two of these connected components are considered too small to be clusters. Thus clusters {
v
3
,
v
7
,
v
8
,
v
9
} and {
v
2
,
v
4
,
v
6
,
v
11
}, shaded in Figure 2(c), remain as candidates for moving.Figure 2
An example of cluster detection.
(a)
Example graph
(b)
Four locally optimized partitions in the population (subsets 0 and 1)
(c)
Two detected clusters


## 4.2. Cluster-Moving Scheme

Our heuristic improves the offspring of each generation after crossover by moving the clusters that were detected using the technique described in the previous subsection. To select the clusters to be moved and their target subsets, we introduce a measure calledcluster gain, such that c
g
(
x
,
a
) is the reduction in the cut size of the partition when all the vertices in cluster x are moved to the subset a. For example, moving the cluster in Figure 1(a) to the other subset in the partition is associated with a cluster gain of 2.This cluster-moving scheme, described in Algorithm1, is applied to each individual generated by crossover, which is a partition that may be unbalanced. However, cut size and cluster gain are well defined on unbalanced partitions. Our scheme does not consider moving every cluster in every partition, because we found that making all clusters movable causes the premature convergence of the MA. Thus, our heuristic selects N clusters at random as candidates for moving. In our experiments, we set N to 5. We compute the cluster gain that results from moving each candidate cluster to each of the other k
-
1 subsets. The candidate cluster x and destination subset a with the highest cluster gain are selected. Assume that c
g
(
x
,
a
) is positive, all the vertices in cluster x are moved to subset a, and cluster x is removed from the set of candidate clusters. This process is repeated until no candidates remain, or no move yields a positive cluster gain. No attempt is made to balance the partition during cluster-moving; this is performed later.Algorithm 1:Our cluster-moving scheme.
Select clusters:S
←
N clusters selected at random;
do  {
Calculatecg
(
x
,
a
) for all x
∈
S
,
1
≤
a
≤
k;
c
g
∗
←
max
x
,
a
⁡
cg
(
x
,
a
);
(
x
¯
,
a
¯
)
←
arg
⁡
max
x
,
a
⁡
cg
(
x
,
a
);
if  c
g
∗
>
0  then  {
Move clusterx
¯ to partition a
¯;
S
←
S
∖
{
x
¯
};
}
}until  (S
=
∅ or c
g
∗
≤
0)


## 5. Memetic Search Framework

CMPA (cluster-moving memetic partitioning algorithm) is a memetic algorithm that we have designed for graph partitioning. In this MA, an individual is ak-way partition. Each gene in an individual corresponds to a vertex and has a value between 0 and k
-
1, which indicates the subset to which the vertex belongs; that is, the ith gene g
i
=
j
⇔
v
i
∈
P
j
+
1. It is a steady-state MA, meaning that there is only one offspring from population in each generation. Crossover is followed by a cluster-moving step and then local optimization.Algorithm2 shows the processes that make up CMPA, which we now describe in detail.(i)
Initialization. When the MA starts, m individuals (i.e., partitions) are created at random. Then each individual is improved by local optimization. We set m to be 30 for bipartitioning and 50 for multiway partitioning (with k
=
8 or k
=
32).
(ii)
Selection. We used the roulette-wheel-based proportional selection. The probability that the best individual is chosen was set to four times the probability that the worst is chosen. The fitness value f
i of the ith individual is expressed as (
c
w
-
c
i
)
+
(
c
w
-
c
b
)
/
3, where c
b, c
w, and c
i are the cut sizes of the partitions corresponding to the best, the worst, and the ith individual, respectively.
(iii)
Normalization. Laszewski [31] first used normalization to improve the performance of GA and its variants have been suggested in [23, 26, 41, 42]. The parent individuals are normalized before crossover following Laszewski [31, 33]. The subset of one parent which shares the largest number of vertices with subsets of the other parent is selected, and that subset is numbered 0. This process is repeated, incrementing the index, until all subsets are numbered.
(iv)
Crossover and Cluster Moving. We used a standard five-point crossover. After crossover, the cluster-handling heuristic described in Section 4.2 is applied to the individual. At this point, individuals usually correspond to unbalanced partitions. We select a random location in the individual and adjust the values of the genes, which are the subsets to which the corresponding vertices belong, to the right of this location (in a typical circular string) until the partition is balanced. This is effectively a mutation effect, and no further mutation was introduced.
(v)
Local Optimization. KL [7] was used for the bisection problems and EFM (extended FM) [21] was used for multiway partitioning (k
=
8 or k
=
32).
(vi)
Replacement. We used a replacement scheme due to Bui and Moon [10]. If an offspring is better than its closer parent, the MA replaces that parent. If it is better than its other parent, then that parent is replaced. Otherwise it replaces the worst individual in the population.
(vii)
Stopping Condition. This is based on consecutive failures to replace an individual’s parents. Termination is triggered by consecutive failures: 30 in bipartitioning and 50 in multiway partitioning.Algorithm 2:The process in CMPA.
Create initial population of fixed size;
Apply local optimization to each member of population;
Calculate genic distance from population;
Find clusters and store their information;
do  {
Selectp
a
r
e
n
t
1 and p
a
r
e
n
t
2 from population;
Normalization(p
a
r
e
n
t
1, p
a
r
e
n
t
2);
offspring
← Crossover(p
a
r
e
n
t
1, p
a
r
e
n
t
2);
Cluster-moving(offspring);
Local-optimization(offspring);
Replace(population,offspring);
}until (stopping condition);
return the best solution;


## 6. Experimental Results

We conducted experiments on 2-way, 8-way, and 32-way partitioning. Table4 shows the performance of MA combined with KL (denoted KL-MA) and CMPA on bipartitioning. Table 5 shows the performance of the genetic extended FM algorithm (GEFM) [21], one of the most effective approaches, and CMPA on 8-way partitioning, and Table 6 gives the results for 32-way partitioning. CMPA uses a cluster-handling heuristic but KL-MA and GEFM do not. We performed 1,000 runs for bipartitioning and 100 runs for 8-way and 32-way partitioning. All the programs were written in the C language and compiled using GNU’sgcc compiler. It was run on a Pentium IV 2.8 GHz computer with Linux. In the tables, the bold-faced numbers indicate the lower of the average cut sizes obtained by the two algorithms. CMPA outperformed KL-MA and GEFM on most graphs, with comparable running times.Table 4
Comparison of KL-MA and CMPA on bipartitioning.
Graph
Best known1
KL-MA
CMPA
Best2
Ave2
CPU3 (Gen4)
Best2
Ave2
CPU3 (Gen4)
G500.2.5
49
49
51.34
0.32 (595)
49
51.22
0.34 (558)
G500.05
218
218
218.65
0.59 (700)
218
218.45
0.64 (682)
G500.10
626
626
627.55
1.02 (681)
626
627.46
1.10 (672)
G500.20
1744
1744
1745.83
1.93 (694)
1744
1745.62
2.09 (687)
G1000.2.5
93
93
97.26
0.96 (745)
93
97.08
1.04 (722)
G1000.05
445
445
451.50
2.07 (884)
445
450.92
2.22 (860)
G1000.10
1362
1362
1366.68
4.07 (969)
1362
1366.18
4.45 (977)
G1000.20
3382
3382
3385.61
7.42 (971)
3382
3385.26
8.13 (987)
U500.05
2
2
4.96
0.55 (793)
2
3.94
0.66 (803)
U500.10
26
26
26.31
0.45 (459)
26
26.04
0.57 (465)
U500.20
178
178
178.06
0.42 (300)
178
178.00
0.53 (271)
U500.40
412
412
412.00
0.34 (190)
412
412.00
0.37 (102)
U1000.05
1
1
11.67
1.71 (1077)
1
8.81
2.12 (1068)
U1000.10
39
39
46.27
1.51 (645)
39
44.15
1.95 (653)
U1000.20
222
222
222.19
1.13 (347)
222
222.07
1.51 (327)
U1000.40
737
737
737.00
1.20 (243)
737
737.00
1.77 (205)
1Best result from the literature.
2Best and average results from 1,000 runs.
3CPU seconds on a Pentium IV 2.8 GHz.
4Average number of generations over 1,000 runs.Table 5
Comparison of GEFM and CMPA on 8-way partitioning.
Graph
GEFM [21]
CMPA
Best1
Ave1
CPU2 (Gen3)
Best1
Ave1
CPU2 (Gen3)
G500.2.5
111
115.21
42.03 (2090)
111
114.51
40.25 (2091)
G500.05
465
468.16
85.65 (2314)
465
467.63
72.96 (2239)
G500.10
1254
1259.53
144.54 (2347)
1254
1258.47
135.04 (2297)
G500.20
3348
3354.80
293.18 (2437)
3348
3353.71
285.09 (2317)
G1000.2.5
212
216.30
146.76 (3043)
211
216.57
148.42 (3023)
G1000.05
930
938.11
247.20 (3148)
931
939.26
234.67 (3069)
G1000.10
2714
2726.33
408.96 (3146)
2711
2725.52
416.98 (3083)
G1000.20
6525
6536.55
791.29 (3303)
6520
6538.35
781.67 (3141)
U500.05
16
18.80
70.87 (2629)
16
17.22
55.89 (2137)
U500.10
143
145.12
98.75 (2277)
143
144.26
90.50 (1984)
U500.20
612
614.57
121.22 (1690)
611
612.93
97.53 (1483)
U500.40
1867
1872.60
157.94 (1396)
1867
1871.73
129.62 (1204)
U1000.05
21
33.66
180.35 (3638)
20
28.53
209.53 (3172)
U1000.10
176
183.70
243.08 (3105)
176
182.30
257.02 (2857)
U1000.20
812
814.05
231.08 (1824)
812
813.00
232.93 (1756)
U1000.40
2562
2563.05
249.46 (1353)
2562
2562.85
273.51 (1238)
1Best and average results from 100 runs.
2CPU seconds on a Pentium IV 2.8 GHz.
3Average number of generations over 100 runs.Table 6
Comparison of GEFM and CMPA on 32-way partitioning.
Graph
Best known1
GEFM [21]
CMPA
Best2
Ave2
CPU3 (Gen4)
Best2
Ave2
CPU3 (Gen4)
G500.2.5
177
177
181.69
78.98 (1491)
177
180.82
74.30 (1382)
G500.05
623
624
630.47
162.26 (2197)
623
629.92
159.18 (2035)
G500.10
1573
1574
1581.94
300.83 (2364)
1572∗
1579.72
355.73 (2332)
G500.20
4034
4037
4045.06
681.53 (2565)
4035
4042.81
673.19 (2479)
G1000.2.5
312
313
320.99
335.79 (2798)
313
320.25
356.44 (2648)
G1000.05
1217
1208
1218.72
698.67 (3133)
1205∗
1216.89
738.06 (3203)
G1000.10
3360
3353∗
3367.31
1171.48 (3294)
3355
3366.08
1323.59 (3267)
G1000.20
7818
7817
7829.81
2012.78 (3475)
7815∗
7830.48
2363.69 (3342)
U500.05
109
112
116.39
138.29 (1640)
109
113.18
121.15 (1595)
U500.10
523
531
537.75
225.52 (1512)
526
531.84
166.26 (1222)
U500.20
1825
1831
1841.39
285.07 (1344)
1823∗
1831.88
299.47 (1197)
U500.40
5328
5364
5380.01
561.74 (1381)
5348
5369.83
523.15 (1331)
U1000.05
117
118
126.02
451.03 (3137)
115∗
123.49
464.35 (2967)
U1000.10
577
576
583.26
599.01 (2599)
571∗
578.16
743.50 (2603)
U1000.20
2367
2375
2396.33
798.77 (1963)
2373
2388.93
930.43 (1848)
U1000.40
7329
7399
7417.49
1421.78 (1634)
7382
7407.18
1493.10 (1573)
1Best known values [20–22, 24, 33].
2Best and average results from 100 runs. Asterisked numbers are new best values.
3CPU seconds on a Pentium IV 2.8 GHz.
4Average number of generations from 100 runs.CMPA underperformed on some random graphs, which may be due to the weak cluster structures in these graphs. CMPA’s average performance was better on all the geometric graphs. This suggests that effective cluster handling is more important on the geometric graphs, as we suggested in Section3.1.The local optimization algorithm is much more expensive than the cluster-handling heuristic; thus, CMPA does not take much longer to run than KL-MA or GEFM. On average, CMPA required 14.14% more time than KL-MA for the bipartitioning problems, and 2.02% more than GEFM in 32-way partitioning. CMPA ran 5.52% faster in 8-way partitioning.


## 7. Concluding Remarks

We devised a cluster-moving heuristic and combined it with a memetic algorithm (MA) for graph partitioning. Experiments on 2-way, 8-way, and 32-way partitioning showed that this heuristic significantly improved the performance of the MA, especially on the 32-way partitioning.The method of moving clusters that we have introduced addresses a significant weakness in standard IIP algorithms. The idea of adding an operation to complement a local optimization algorithm might be used to address other deficiencies in MAs.Our method of cluster detection is based on a measure that we call genic distance, which is designed to reflect the extent to which two vertices connected by an edge belong to the same cluster. Instead of computing genic distances once in an initialization phase, an MA could recompute these distances as it progresses: this might improve the accuracy of cluster detection, at some cost in time. We believe that genic distance might also be useful in solving other problems involving clusters, such as the maximum clique problem.



---

*Source: 238529-2015-09-20.xml*