|
|
|
Rodriguez Zalipynis Ramon Antonio |
raro@ua.fm
|
|||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
New graph coarsening method which exploits ant colony model has been developed for multilevel graph partitioning paradigm. It succeeded to improve qualities of solutions yielding by METIS – one of the best and the fastest packages for graph partitioning – up to 40% for some graphs. Graph Partitioning ProblemGraph partitioning problem arises in many areas including sparse matrix reordering, robotics, database querying, image processing, computer networks, parallel computations, VLSI design, operating systems, etc. [1, 2, 3, 4, 5, 6, 7]. For undirected graph with weights on its vertices and edges the task is to find a partition of the set of its vertices onto balanced subsets so as to minimize the total weight of edges connecting vertices from different subsets. The subset is balanced if the sum of the weights of its vertices lies in a predefined interval. Graph Partitioning ApproachesMultilevel graph partitioning algorithm from [8] starting from original graph creates a sequence of graphs in which each successive graph is a coarse replica of the previous graph obtained by pairwise contraction of vertices. A partition of the coarsest graph is calculated and projected back to its parent graph assigning to vertices v and w contracted into vertice u the same partition subset to which u belongs to.The process of pairwise contraction of vertices when performing graph coarsening in multilevel paradigm has a probabilistic nature and locality in some sense thus depending upon vertice numbering. There is a tendency to contract vertices which should be placed in different subsets which results in degrading the overall solution quality. In the developed algorithm it is proposed to contract several vertices at once (clusters) when coarsening a graph. A cluster differs from its neighboring vertices by its connectivity or by the total weight of the edges which it contains. The proposed approach eliminates the dependence of vertice numbering and improves the overall solution quality. Scientists revealed high organization level of ant colonies comparing to the relative simplicity in behavior of separate ants. Ants are able to build shortest paths among food and their nest, sort larvae according to their size, cluster objects. Ants deposit chemical substance – pheromone which they lie on the ground when moving. Pheromone trails form paths for ants. When moving ants tend to choose – with certain probability – paths with strong pheromone concentrations [9]. Author has developed new ant algorithm for graph partitioning. Its main idea is to modify weight of edge (v, w) so that its weight turned to be proportional to the probability of being v and w in the same partition subset. It is reasonable to put tightly connected vertices in the same partition subset. Ants move from one vertice to another seeking such vertices and incrementing pheromone concentration on the edges they visit. Areas of vertices with heavy edges are contracted in a single vertice. The obtained coarsened graph is sent to METIS which rapidly finds good partitions. Nevertheless, quality of partitions found by METIS can be improved up to 40% for some graphs using the described scheme.
Using new edges weights it is possible to extract vertices belonging to the same cluster and contract them into single vertice.
The new species of artificial ants has been developed – trofo-ants. Their structure and behavior differ from ordinary ants. Trofo-ants do not deposit pheromone but instead of it they eat pheromone. The work of the trofo-ants is the new unique distributed scheme of pheromone evaporation. Some weights of edges of a big cluster may receive much more pheromone than the others in the same cluster. Trofo-ants distribute pheromone more smoothly among the cluster edges increasing the probability of detecting a big cluster entirely in a single coarsening step instead of coarsening its parts during several coarsening steps. Experimental ResultsExperiments where held on graphs from C. Walshaw archive [10] using METIS. Table 1 – Main results
Where Cut(A) - the edge cut of a partition found by METIS running on original graph, and Cut(B) - the edge cut of a partition found by METIS running on a graph coarsend by the proposed algorithm. ConclusionThe graph partitioning problem was investigated. For graph coarsening in multilevel graph partitioning paradigm new ant algorithm has been developed. It contracts groups of vertices (clusters) which have high probability of being placed in the same partition subset. The new heuristics comparing to existing ones for seeking clusters have been developed. It was able to achieve high quality solutions for many graphs spending only several hours. Some evolutionary schemes demonstrate better results [11], but they work up to several weeks on a single graph. The further improvement is to parallelize the proposed algorithm for a computer cluster.
Literature
|
|
