DFG SPP 1307 "Algorithm Engineering"
!!! For information on the SPP 1307 Clustering Workshop 2009 visit the workshop website !!!
DFG Schwerpunktprogramm 1307
"Algorithm Engineering"
Subproject "Disturbed Diffusion for Partitioning and Clustering Graphs"
Abstract:Many natrual 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.
Please visit the corresponding research website for some of our results.
Research fields:
- Diffusion
- Graph partitioning
- Load balancing of numerical simulations
- Graph clustering
Related links:
People/Contact:
- Burkhard Monien, Proposer
- Henning Meyerhenke, Scientific Staff
Publications:
- H. Meyerhenke, J. Gehweiler: On Dynamic Graph Partitioning and Graph Clustering using Diffusion. In: Algorithm Engineering, 27.06. - 02.07.2010. Dagstuhl Seminar Proceedings 10261, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2010.
- H. Meyerhenke: Beyond Good Shapes. Diffusion-based Graph Partitioning is Relaxed Cut Optimization. Accepted for publication in Proc. 21st International Symposium on Algorithms and Computation (ISAAC'10), 2010.
- J. Gehweiler, H. Meyerhenke: A Distributed Diffusive Heuristic for Clustering a Virtual P2P Supercomputer. To appear in Proc. 7th High-Performance Grid Computing Workshop (HPGC'10), in conjunction with 24th IEEE Internatl. Parallel and Distributed Processing Symposium (IPDPS'10), IEEE, 2010.
- H. Meyerhenke: Dynamic Load Balancing for Parallel Numerical Simulations based on Repartitioning with Disturbed Diffusion. In Proc. 15th Internatl. Conference on Parallel and Distributed Systems (ICPADS'09). IEEE, 2009.
- H. Meyerhenke, B. Monien, S. Schamberger: Graph Partitioning and Disturbed Diffusion. Parallel Computing, 35(10-11):544-569, 2009.
-
H. Meyerhenke: Disturbed Diffusive Schemes for Solving Partitioning Problems
on
Graphs.
Dissertation, University of Paderborn, April 2008.
[abstract (en)] [abstract (de)] [bibtex] [pdf] - H. Meyerhenke, B. Monien, T. Sauerwald: A New Diffusion-based Multilevel Algorithm for Computing Graph Partitions of Very High Quality. To appear in Proc. 22nd IEEE Internatl. Parallel and Distributed Processing Symposium (IPDPS'08). Winner of the Best Algorithms Paper Award.
-
H. Meyerhenke, T. Sauerwald: Analyzing Disturbed Diffusion on Networks. In Proc. 17th International Symposium on Algorithms and Computation (ISAAC'06), LNCS 4288, pp. 429-438. Springer-Verlag, 2006.
[pdf at SpringerLink] -
H. Meyerhenke, S. Schamberger: A Parallel Shape Optimizing Load Balancer. In Proc. 12th Int. Euro-Par Conf. 2006, LNCS 4128, pp. 232-242. Springer-Verlag, 2006.
[pdf at SpringerLink] -
H. Meyerhenke, B. Monien, S. Schamberger: Accelerating Shape Optimizing
Load Balancing for Parallel FEM Simulations by Algebraic Multigrid. In Proc. 20th IEEE Internatl. Parallel and Distributed Processing Symposium (IPDPS'06), p. 57 (CD), IEEE Computer Society, 2006.
[pdf at IEEE Xplore, © IEEE Computer Society 2006]