Disturbed Diffusion for Partitioning and Clustering Graphs
Description
Prof. Dr. Burkhard Monien; Universität Paderborn
Project website
Many natural and scientific transport phenomena can be modelled by diffusive processes. These processes perform exchanges of loads between neighboring entities in order to obtain a balanced load distribution. We have modified the first order diffusion scheme (FOS) on graphs with a suitable disturbance such that its convergence state results in a non-balanced load distribution. These loads then reflect structural properties of the graph, which makes it possible to identify densely connected regions. This idea has been used successfully to develop an algorithm for graph partitioning and for balancing workloads of processors in parallel numerical simulations. Compared to classical methods, our new algorithm shows significant advantages regarding partitioning quality and migration costs. However, its running time is not satisfactory yet.
In this project we examine the new diffusion-based algorithm thoroughly on a theoretical and practical basis. We see promising approaches to solve the running time problems while keeping the quality improvements. This aims at the development of a graph partitioner which results in a signficantly more efficient parallel implementation and execution of parallel adaptive numerical simulations than before. Apart from that, the disturbed diffusion concept is also to be used for the automatic identification of tightly coupled groups (clusters) of different sizes in static and dynamic graphs and networks with local knowledge only. The resulting algorithms will be theoretically analyzed, implemented, parallelized, and finally, after a thorough experimental evaluation, made available as libraries.
Publications
- D. Ajwani and H. Meyerhenke. "Realistic Computer Models". M. Müller-Hannemann and S. Schirra eds. Springer-Verlag. 2010. pp. 194-236. [More]
- H. Meyerhenke. "Beyond Good Shapes: Diffusion-based Graph Partitioning is Relaxed Cut Optimization". Proc. 21st International Symposium on Algorithms and Computation (ISAAC'10). 2010. [More]
- J. Gehweiler and H. Meyerhenke. "A Distributed Diffusive Heuristic for Clustering a Virtual P2P Supercomputer". Proc. 7th High-Performance Grid Computing Workshop (HGCW'10) in conjunction with 24th Intl. Parallel and Distributed Processing Symposium (IPDPS'10). 2010. [More]
- H. Meyerhenke. "Dynamic Load Balancing for Parallel Numerical Simulations Based on Repartitioning with Disturbed Diffusion". Proc. Internatl. Conference on Parallel and Distributed Systems (ICPADS'09). 2009. pp. 150-157. [More]
- H. Meyerhenke, B. Monien and S. Schamberger. "Graph Partitioning and Disturbed Diffusion", Parallel Computing, Vol. 35. 2009, pp. 544-569. [More]
- H. Meyerhenke, B. Monien and T. Sauerwald. "A New Diffusion-based Multilevel Algorithm for Computing Graph Partitions", Journal of Parallel and Distributed Computing, Vol. 69. 2009, pp. 750-761. [More]
- H. Meyerhenke. "Disturbed Diffusive Processes for Solving Partitioning Problems on Graphs". Universität Paderborn. 2008. [More]
- H. Meyerhenke, B. Monien and T. Sauerwald. "A New Diffusion-based Multilevel Algorithm for Computing Graph Partitions of Very High Quality". Proc. 22nd International Parallel and Distributed Processing Symposium, (IPDPS'08). 2008. [More]