Francesc Comellas, Emili Sapena, A multiagent algorithm for graph partitioning.
Lecture Notes in Comput. Sci. vol. 3907, pp. 279285 (2006). ISSN: 03029743
A multiagent algorithm for graph partitioning
^{1}
Francesc Comellas, Emili Sapena
Abstract
The kcut problem is an NPcomplete 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.
1 Introduction
Graph partitioning is a problem which appears in many different
applications such as VLSI design, datamining, 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 kpartition of a graph
with a minimal number of cut edges separating the sets from each other (kcut).
As this is an NPcomplete problem [5], 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 kcut problem, there is a large literature
proposing different algorithms.
For example, in [6] an heuristic method is introduced which can find,
for the general problem, approximate solutions in time O(V^{k2}) and
in [9] the algorithm proposed can find solutions within a factor of (22/k) of the optimal
kcut requiring V1 maxflow 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 kcut 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
S_{i} such that the union of all subdomains is V, i.e. È_{i=1}^{k} S_{i}=V.
The cardinality of a subdomain is the number of vertices
in the subdomain S_{i}, and the set of intersubdomain or cut edges
(i.e. edges cut by the partition) is denoted by E_{c} and referred to as the kcut.
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 cutweight, E_{c}.
To evenly balance the partition, the cardinality of the optimal subdomain
is given by
S_{opt} =
é [(V)/(k)]
ù .
The graph partitioning problem can then be specified as:
find a partition of G such that E_{c} is minimised subject
to the constraint that S_{opt}1 £ S_{i} £ S_{opt} for 1 £ i £ k.
In this paper we find partitions with a perfect balance.
3 The ants algorithm
The partitioning or kcut problem described in the previous section,
as many other problems in graph theory,
is an NPcomplete problem [5].
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
antcolony 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 [3].
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
these actions.
The agent or ant moves to the worst
adjacent vertex with a probability p_{m} (it moves randomly to any other adjacent vertex with probability 1p_{m}),
and assigns the best color, under probability p_{c} (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 kcuts 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 p_{m} and p_{c}
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 p_{m} and p_{c} 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
ANTS algorithm:
Initialize
n (number of ants), k, p_{m}, p_{c}
Put each ant on a randomly chosen vertex
Color each vertex of the graph at random forming k balanced sets
For all vertices
Initialize local_cost_function
End for
Initialize global_cost_function
best_cost := global_cost_function
While (best_cost > 0) do
For all ants
If (random < p_{m})
Move the ant to the worst adjacent vertex
Else
Move randomly to any adjacent vertex
End if
If (random < p_{c})
Change vertex color to the best possible color
Else
Change to a randomly chosen color
End if
Keep balance (Change a random new color vertex to the old color )
For the chosen vertices and all adjacent vertices
Update local_cost_function
Update global_cost_function
End for
If (global_cost_function < best_cost )
best_cost = global_cost_function
End if
End for
End while
4 Results
We tested the algorithm using a set of benchmark graphs which are available from the
Graph Partitioning Archive, a website maintained by Chris Walshaw [13].
The graphs can also be downloaded from Michael Trick's website [11].
Many of these graphs were collected together for the second DIMACS implementation challenge "NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability", see [4].
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 p_{m} and
p_{c} 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 DevC++.
Most of the improvements were on results obtained previously with
CHACO (Ch2.0), a multilevel KernighanLin (recursive bisection [7] and
iterated JOSTLE (iJ), an iterated multilevel KernighanLin (kway)[12].
In three cases we improved on results obtained with JOSTLE Evolutionary (JE), a combined evolutionary/multilevel scheme [10], and
in six more cases we matched results obtained with JOSTLE (J2.2), a multilevel
KernighanLin (kway)[14].
In our experiments, the algorithm ants obtains better solutions
for the colouring test suite (16 subdomains, perfect balance)
of graphs considered in [12] in 27 cases and an equivalent solution in 7 cases (out of the 89 graph instances).
5 Conclusion
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 nonbalanced cases.
Note also that adapting the algorithm for graphs with weighted vertices and edges would be
straighforward.
Graph  vertices  edges  domain size  cut size [13]  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 

Table 1:
Best partitions found with ants corresponding to perfect balance for 16 subdomains using benchmark graphs[13]. 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 KernighanLin (recursive bisection), version 2.0 (October 1995) [7]. J2.2, JOSTLE, multilevel KernighanLin (kway), version 2.2 (March 2000) [14]. iJ, iterated JOSTLE, iterated multilevel KernighanLin (kway) [12]. JE, JOSTLE Evolutionary, combined evolutionary/multilevel scheme [10].
References
 [1]

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. 143153 (2003).
 [2]

J. Abril, F. Comellas, A. Cortés, J. Ozón, M. Vaquer.
A multiagent system for frequency assignment in cellular radio networks.
IEEE Trans. Vehic. Tech. 49(5) pp. 15581565 (2000).
 [3]

F. Comellas and J. Ozón,.
Graph coloring algorithms for assignment problems in radio networks.
Proc. Applications of Neural Networks to Telecommunications 2, pp. 4956.
J. Alspector, R. Goodman and T.X. Brown (Eds.), Lawrence Erlbaum Ass. Inc. Publis., Hillsdale, NJ (1995)
 [4]

The Second DIMACS Implementation Challenge: 19921993: NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability. Organized by M. Trick (accessed January 8, 2006).
http://dimacs.rutgers.edu/Challenges/index.html
 [5]

M.R. Garey and D.S. Johnson.
Computers and Intractability: A Guide to the Theory of NPCompleteness,
New York: W.H. Freeman, 1979, ISBN 0716710447.
 [6]

O. Goldschmidt and D.S. Hochbaum.
Polynomial algorithm for the kcut problem.
Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 444451.
(1988).
 [7]

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.
 [8]

P. Korosec, J. Silc, B. Robic.
Solving the meshpartitioning problem with an antcolony algorithm.
Parallel Computing 30(56) pp. 785801 (2004).
 [9]

H. Saran and V. Vazirani.
Finding kcuts within twice the optimal.
Proc. 32nd Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 743751 (1991)
 [10]

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. 225241 (2004).
 [11]

M. Trick. Graph coloring instances (web page), accessed January 8, 2006.
http://mat.gsia.cmu.edu/COLOR/instances.html
 [12]

C. Walshaw.
Multilevel refinement for combinatorial optimisation problems.
Annals Oper. Res. 131 pp. 325372 (2004).
 [13]

C. Walshaw. The graph partioning archive (web page), accessed January 8, 2006.
http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/
 [14]

C. Walshaw and M. Cross.
Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm.
SIAM J. Sci. Comput. 22(1) pp. 6380 (2000).
Footnotes:
^{1}Research supported by the Ministerio de Educación y Ciencia, Spain, and the European Regional Development Fund under project TIC200200155.
File translated from
T_{E}X
by
T_{T}H,
version 3.64.
On 12 Feb 2006, 11:50.