English
DonNTU
Masters' Portal
Abstract Library Links Search report Assembly, Forum, Sevastopol
Abstract
Library Links Search report Zavtra.UA
Rodriguez Zalipynis
Ramon Antonio
mail: raro@ua.fm
DonNTU Master Rodriguez Zalipynis Ramon Antonio
Abstract Abstract
Methods of solving graph partitioning tasks using computer cluster network
Ladizenskiy Youriy Valentinovich
Faculty of computers and information science
Software support of automated systems

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 Problem

Graph 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 Approaches

Multilevel 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.

Ants - animation
Ants incrementing weights of edges belonging to the cluster (30 frames, 10 times repeat, 83.7Kb).

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 Results

Experiments where held on graphs from C. Walshaw archive [10] using METIS.

Table 1 Main results

Graph name

Number of vertices

Number of edges

Cut(A)

Cut(B)

improving, %

Cti

16840

48232

401

399

0.50

598a

110971

741934

2600

2563

1.42

bcsstk30

28924

1007284

6509

6400

1.67

bcsstk29

13992

302748

3217

3086

4.07

cs4

22499

43858

427

406

4.92

t60k

60005

89440

109

103

5.50

wing_nodal

10937

75488

1982

1798

9.28

fe_sphere

16386

49152

488

442

9.43

brack2

62631

366559

827

744

10.04

bcsstk32

36519

144794

6230

5338

14.32

bcsstk33

8738

291583

13393

11168

16.61

add32

4960

9462

12

10

16.67

bcsstk31

35588

572914

4953

2991

39.61

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.

Conclusion

The 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

  1. Olson E. et al., Single-Cluster Spectral Graph Partitioning for Robotics Applications, Massachusetts Institute of Technology
  2. Douglas et al., Cache Optimization for Structured and Unstructured Grid Multigrid, 2000
  3. A Parallel Structured Flow Solver URANUS, Russian-German School on HPC Systems, Novosibirsk, 2005
  4. Spatial Color Component Matching of Images, 2001
  5. Zabih R., Kolmogorov V., Spatially Coherent Clustering Using Graph Cuts, 2004
  6. Chamberlain B., Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations, 1998
  7. Yelick K., CS 267: Applications of Parallel Computers. Graph Partitioning, 2004
  8. Karypis G., Kumar V., Multilevel k-way partitioning scheme for irregular graphs, 1998
  9. Dorigo M., Maniezzo V., Colorni A., The ant system: optimization by a colony of cooperative agents, 1996
  10. C. Walshaw Graph Partitioning Archive, http://staffweb.cms.gre.ac.uk/~c.walshaw
  11. Soper A.J, Walshaw C., Cross M., A Combined Evolutionary Search and Multilevel Optimization Approach to Graph Partitioining, 2004.



English
DonNTU
Masters' Portal
Abstract Library Links Search report Assembly, Forum, Sevastopol
Abstract
Library Links Search report Zavtra.UA