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 1

Francesc Comellas, Emili Sapena

Abstract

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.

1  Introduction

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 [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 k-cut 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 (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 |Sopt| = é [(|V|)/(k)] ù . 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 [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 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 [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 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 ANTS algorithm:

Initialize
 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
  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 < pm)
   Move the ant to the worst adjacent vertex
  Else
   Move randomly to any adjacent vertex
  End if
  If (random < pc)
   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 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 [7] and iterated JOSTLE (iJ), an iterated multilevel Kernighan-Lin (k-way)[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 Kernighan-Lin (k-way)[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 non-balanced 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 Kernighan-Lin (recursive bisection), version 2.0 (October 1995) [7]. J2.2, JOSTLE, multilevel Kernighan-Lin (k-way), version 2.2 (March 2000) [14]. iJ, iterated JOSTLE, iterated multilevel Kernighan-Lin (k-way) [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. 143-153 (2003).
[2]
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).
[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. 49-56. J. Alspector, R. Goodman and T.X. Brown (Eds.), Lawrence Erlbaum Ass. Inc. Publis., Hillsdale, NJ (1995)
[4]
The Second DIMACS Implementation Challenge: 1992-1993: 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 NP-Completeness, New York: W.H. Freeman, 1979, ISBN 0-7167-1044-7.
[6]
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. (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 mesh-partitioning problem with an ant-colony algorithm. Parallel Computing 30(5-6) pp. 785-801 (2004).
[9]
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)
[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. 225-241 (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. 325-372 (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. 63-80 (2000).

Footnotes:

1Research supported by the Ministerio de Educación y Ciencia, Spain, and the European Regional Development Fund under project TIC2002-00155.

File translated from TEX by TTH, version 3.64.
On 12 Feb 2006, 11:50.