Universität Paderborn - Home Universität Paderborn
Die Universitä der Informationsgesellschaft

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"

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:

Related links:



Index A – Z | Impressum | Webmaster