Francesc Comellas, Emili Sapena, A multiagent algorithm for graph partitioning.
Lecture Notes in Comput. Sci. vol. 3907, pp. 279--285 (2006). ISSN: 0302-9743
A multiagent algorithm for graph partitioning
Francesc Comellas, Emili Sapena
The k-cut problem is an NP-complete problem which
consists of finding a partition of a graph into k balanced
parts such that the number of cut edges is minimized. Different
algorithms have been proposed for this problem based on heuristic,
geometrical and evolutionary methods. In this paper we present
a new simple multiagent algorithm, ants, and we test
its performance with standard graph benchmarks.
The results show that this method can outperform several
current methods while it is very simple to implement.
Graph partitioning is a problem which appears in many different
applications such as VLSI design, data-mining, finite elements and communication in parallel computing. In the latter case, for example, the subdomains are mapped
to processors and to avoid bottlenecks, the assignment should be as
uniform as possible and the data exchange between processors minimized.
In terms of graphs, the goal is to find a balanced k-partition of a graph
with a minimal number of cut edges separating the sets from each other (k-cut).
As this is an NP-complete problem , for graphs with a large order
we cannot be sure we can find an optimal solution
in a reasonable computation time: when the size of the graph increases,
the execution time of an algorithm capable of solving the problem
can be assumed to grow exponentially.
Therefore the problem is practically unsolvable for most networks and
for this reason heuristic and probabilistic methods are implemented
to obtain solutions close to the optimal in a reasonable time.
The only way to guarantee the optimal solution is an exhaustive search.
Nevertheless, this is only applicable to very simple problems in which
the number of nodes is small.
Given the importance of the k-cut problem, there is a large literature
proposing different algorithms.
For example, in  an heuristic method is introduced which can find,
for the general problem, approximate solutions in time O(|V|k2) and
in  the algorithm proposed can find solutions within a factor of (2-2/k) of the optimal
k-cut requiring |V|-1 max-flow computations.
Recent more efficient methods are based on multilevel paradigms [1,12],
in some cases combined with evolutionary algorithms [10,8].
In this paper we use a multiagent algorithm, ants, for the k-cut problem.
This algorithm has proved
useful in coloring and frequency assignment problems [3,2].
The method is simple to understand and to implement and the results obtained
with standard benchmarks show that it can outperform current algorithms.
2 Graph partitioning
Let G = G(V,E) be an undirected graph where V is the vertex set and
E the edge set. Although in the general partitioning problem both vertices and edges
can be weighted, here as in most of the literature, they are given unit weights.
A partition of the graph is a mapping of V into k disjoint subdomains
Si such that the union of all subdomains is V, i.e. Èi=1k Si=V.
The cardinality of a subdomain is the number of vertices
in the subdomain Si, and the set of inter-subdomain or cut edges
(i.e. edges cut by the partition) is denoted by Ec and referred to as the k-cut.
The objective of graph partitioning is to find a partition
which evenly balances the cardinalities of each subdomain whilst minimizing
the total number of cut edges or cut-weight, |Ec|.
To evenly balance the partition, the cardinality of the optimal subdomain
is given by
The graph partitioning problem can then be specified as:
find a partition of G such that |Ec| is minimised subject
to the constraint that |Sopt|-1 £ |Si| £ |Sopt| for 1 £ i £ k.
In this paper we find partitions with a perfect balance.
3 The ants algorithm
The partitioning or k-cut problem described in the previous section,
as many other problems in graph theory,
is an NP-complete problem .
Efficient algorithms for this problem
are known only for very particular classes of graphs.
When exact methods are not possible,
sometimes it is sufficient to obtain an
approximate solution with a fast and easy
to implement method. This is the case of
simulated annealing, genetic algorithms, neural
networks, ant colony based systems, or multiagent
methods like the one described here.
To implement any of these optimization methods
we need a way to encode the problem which has
to be solved, and a system to quantify how
"good" a solution is. In our case a possible solution may
be encoded using a list such that each position is
associated to a vertex of the graph and its value
to a color which represents the subdomain to which it belongs.
The global cost function simply counts the number of
times that an edge joins vertices with different
color. We use also a local cost function associated to
each vertex defined as the ratio between the number of neighbors that
have different colors to the total number of neighbors.
The ants algorithm is a multiagent system based on the idea of parallel search.
Unlike other algorithms with a similar name which are generically known as
ant-colony optimization, our algorithm does not use "pheromones" or local memory.
Thus it is easier to implement.
A generic version of the algorithm was proposed in .
The mechanism of the algorithm is as follows: Initially the graph is k vertex colored
at random keeping the number of vertices for each color balanced.
A given number of agents (ants) is placed on the vertices, also at random.
Then the ants move around the graph and change the coloring according to a
local optimization criterion.
At a given iteration each ant moves from the current position to the adjacent vertex
with the greatest number of constraints (neighbors with a different color), and replaces
its color with a new color which lowers this number.
At the same time, and to keep the balance, the algorithm chooses -at random- a vertex
with the new color and a lower value of the local cost function and changes
the color to the old color.
This local cost function is then updated (for the vertex and its adjacent vertices) after a change of color.
Figure 1: Movement of an ant towards the worst local node.
These actions are randomly repeated for each ant.
An essential characteristic of the algorithm comes from the stochastic nature of
The agent or ant moves to the worst
adjacent vertex with a probability pm (it moves randomly to any other adjacent vertex with probability 1-pm),
and assigns the best color, under probability pc (otherwise it assigns any color at random).
Both probabilities are adjustable parameters and allow the algorithm to escape from
local minima and obtain partitions with k-cuts close to the absolute minimum.
The process is repeated until a solution fulfilling all the constraints is found
or the algorithm converges.
The number of ants in the algorithm is another adjustable parameter
that should increase with the diameter of the graph
(maximum of the distances between pairs of vertices).
In the same way as in an insect colony the action of different agents with simple
behaviors gives rise to a structure capable of carrying out complicated tasks,
the algorithm presented here, which is based on a series of simple local actions
that might evenbe carried out in parallel, can obtain restrictive graph partitions.
Note that our algorithm is not a simple sum of local searches, as they would
quickly reach a local solution. The probabilities pm and pc
play an important role to avoid the minima, however their values are not critical and
affect essentially the convergence time of the algorithm which is shorter for larger
values of pm and pc as the index of local improvement at each iteration increases.
An outline of the ants algorithm is shown here in pseudocode.
mm¯ mm¯ mmm¯ mm¯ mm¯ m
n (number of ants), k, pm, pc
Put each ant on a randomly chosen vertex
Color each vertex of the graph at random forming k balanced sets
For all vertices
best_cost := global_cost_function
While (best_cost > 0) do
For all ants
If (random < pm)
Move the ant to the worst adjacent vertex
Move randomly to any adjacent vertex
If (random < pc)
Change vertex color to the best possible color
Change to a randomly chosen color
Keep balance (Change a random new color vertex to the old color )
For the chosen vertices and all adjacent vertices
If (global_cost_function < best_cost )
best_cost = global_cost_function
We tested the algorithm using a set of benchmark graphs which are available from the
Graph Partitioning Archive, a website maintained by Chris Walshaw .
The graphs can also be downloaded from Michael Trick's website .
Many of these graphs were collected together for the second DIMACS implementation challenge "NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability", see .
For the test we considered the most difficult case of perfect balance and choose a partition into 16 sets.
The number of ants ranged from 3 to 9 depending on the order of the graph. The probabilities pm and
pc were 0.9 and 0.85, respectively. We repeated the algorithm 20 times
for each graph (80 times for small graphs) and recorded the best solutions.
Each algorithm run takes around one minute, for a C program (400 lines)
compiled on a PC Pentium IV 2.8 GHz under Windows XP using Dev-C++.
Most of the improvements were on results obtained previously with
CHACO (Ch2.0), a multilevel Kernighan-Lin (recursive bisection  and
iterated JOSTLE (iJ), an iterated multilevel Kernighan-Lin (k-way).
In three cases we improved on results obtained with JOSTLE Evolutionary (JE), a combined evolutionary/multilevel scheme , and
in six more cases we matched results obtained with JOSTLE (J2.2), a multilevel
In our experiments, the algorithm ants obtains better solutions
for the colouring test suite (16 subdomains, perfect balance)
of graphs considered in  in 27 cases and an equivalent solution in 7 cases (out of the 89 graph instances).
The results show that our implementation of the multiagent algorithm ants for the graph partitioning problem provides, for the balanced case, a new method which matches and in some cases outperforms the best known methods.
Given the simplicity of the algorithm and its performance in the difficult case of
balanced sets, it is a promising method for graph partioning in the non-balanced cases.
Note also that adapting the algorithm for graphs with weighted vertices and edges would be
Best partitions found with ants corresponding to perfect balance for 16 subdomains using benchmark graphs. We provide for the graphs of reference the total of vertices and edges, optimal subdomain size, cut size, new cut size and the algorithm used to find the old cut size. Boldface denotes those values for which the ants algorithm has outperformed the known result. Algorithms:
Ch2.0, CHACO, multilevel Kernighan-Lin (recursive bisection), version 2.0 (October 1995) . J2.2, JOSTLE, multilevel Kernighan-Lin (k-way), version 2.2 (March 2000) . iJ, iterated JOSTLE, iterated multilevel Kernighan-Lin (k-way) . JE, JOSTLE Evolutionary, combined evolutionary/multilevel scheme .
|Graph ||vertices ||edges ||domain size ||cut size  ||new cut size ||algorithm |
|C2000.5 ||2000 ||999836 ||125 ||923294 ||922706 ||Ch2.0|
|C4000.5 ||4000 ||4000268 ||250 ||3709887 ||3708532 ||Ch2.0|
|DSJC125.1 ||125 ||736 ||8 ||524 ||522 ||iJ|
|DSJC1000.1 ||1000 ||40629 ||63 ||43078 ||43001 ||Ch2.0|
|DSJC1000.5 ||1000 ||249826 ||63 ||229362 ||228850 ||Ch2.0|
|jean ||80 ||254 ||5 ||161 ||161 ||Ch2.0|
|flat1000_50_0 ||1000 ||245000 ||63 ||224403 ||224378 ||Ch2.0|
|flat1000_60_0 ||1000 ||245830 ||63 ||225546 ||225183 ||Ch2.0|
|flat1000_76_0 ||1000 ||246708 ||63 ||226371 ||225962 ||Ch2.0|
|le450_5a ||450 ||5714 ||29 ||4063 ||4030 ||JE|
|le450_5b ||450 ||5734 ||29 ||4065 ||4055 ||iJ|
|le450_5c ||450 ||9803 ||29 ||7667 ||7656 ||iJ|
|le450_15a ||450 ||8168 ||29 ||5636 ||5619 ||iJ|
|le450_15b ||450 ||8169 ||29 ||5675 ||5641 ||iJ|
|le450_15c ||450 ||16680 ||29 ||13512 ||13509 ||iJ|
|le450_15d ||450 ||16750 ||29 ||13556 ||13550 ||iJ|
|le450_25a ||450 ||8260 ||29 ||5325 ||5302 ||J2.2|
|le450_25b ||450 ||8263 ||29 ||5041 ||5037 ||JE|
|le450_25c ||450 ||13343 ||29 ||13457 ||13456 ||iJ|
|le450_25d ||450 ||17425 ||29 ||13584 ||13539 ||iJ|
|miles500 ||128 ||1170 ||8 ||771 ||770 ||JE|
|miles750 ||128 ||2113 ||8 ||1676 ||1673 ||iJ|
|miles1000 ||128 ||3216 ||8 ||2770 ||2768 ||iJ|
|miles1500 ||128 ||5198 ||8 ||4750 ||4750 ||J2.2|
|mulsol.i.1 ||197 ||3925 ||13 ||3275 ||3270 ||Ch2.0|
|mulsol.i.5 ||185 ||3973 ||12 ||3371 ||3368 ||Ch2.0|
|myciel4 ||23 ||71 ||2 ||64 ||64 ||J2.2|
|myciel5 ||47 ||236 ||3 ||205 ||205 ||J2.2|
|myciel7 ||191 ||2360 ||12 ||1921 ||1920 ||iJ|
|queen5_5 ||25 ||160 ||2 ||151 ||151 ||J2.2|
|queen8_8 ||64 ||728 ||4 ||632 ||632 ||Ch2.0|
|queen8_12 ||96 ||1368 ||6 ||1128 ||1128 ||Ch2.0|
|queen12_12 ||144 ||2596 ||9 ||2040 ||2020 ||iJ|
|queen16_16 ||256 ||6320 ||16 ||4400 ||4400 ||J2.2|
R. Baños, C. Gil, J. Ortega, and F. G. Montoya.
Multilevel heuristic algorithm for graph partitioning.
In 3rd European Workshop on Evolutionary Computation in Combinatorial Optimization.
Lecture Notes in Comput. Sci. 2611 pp. 143-153 (2003).
J. Abril, F. Comellas, A. Cortés, J. Ozón, M. Vaquer.
A multi-agent system for frequency assignment in cellular radio networks.
IEEE Trans. Vehic. Tech. 49(5) pp. 1558-1565 (2000).
F. Comellas and J. Ozón,.
Graph coloring algorithms for assignment problems in radio networks.
Proc. Applications of Neural Networks to Telecommunications 2, pp. 49-56.
J. Alspector, R. Goodman and T.X. Brown (Eds.), Lawrence Erlbaum Ass. Inc. Publis., Hillsdale, NJ (1995)
The Second DIMACS Implementation Challenge: 1992-1993: NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability. Organized by M. Trick (accessed January 8, 2006).
M.R. Garey and D.S. Johnson.
Computers and Intractability: A Guide to the Theory of NP-Completeness,
New York: W.H. Freeman, 1979, ISBN 0-7167-1044-7.
O. Goldschmidt and D.S. Hochbaum.
Polynomial algorithm for the k-cut problem.
Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 444-451.
B. Hendrickson and R. Leland.
A multilevel algorithm for partitioning graphs.
In S. Karin, editor, Proc. Supercomputing '95, San Diego. ACM Press, New York, 1995.
P. Korosec, J. Silc, B. Robic.
Solving the mesh-partitioning problem with an ant-colony algorithm.
Parallel Computing 30(5-6) pp. 785-801 (2004).
H. Saran and V. Vazirani.
Finding k-cuts within twice the optimal.
Proc. 32nd Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 743-751 (1991)
A. J. Soper, C. Walshaw, and M. Cross.
A combined evolutionary search and multilevel optimisation approach to graph partitioning.
J. Global Optimization 29(2) pp. 225-241 (2004).
M. Trick. Graph coloring instances (web page), accessed January 8, 2006.
Multilevel refinement for combinatorial optimisation problems.
Annals Oper. Res. 131 pp. 325-372 (2004).
C. Walshaw. The graph partioning archive (web page), accessed January 8, 2006.
C. Walshaw and M. Cross.
Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm.
SIAM J. Sci. Comput. 22(1) pp. 63-80 (2000).
1Research supported by the Ministerio de Educación y Ciencia, Spain, and the European Regional Development Fund under project TIC2002-00155.
File translated from
On 12 Feb 2006, 11:50.