Engineering Parallel Algorithms for Partitioning Problems in Graphs

 

Graphs are frequently used abstractions of real-world data. Cutting a graph into smaller pieces is a fundamental algorithmic operation, which is often used for complexity reduction or parallelization. We experience steadily growing instance sizes in diverse application areas such as scientific simulation, social networks, or road networks. Thus, good solvers for partitioning problems become increasingly important and challenging.

In this talk we focus on practical algorithms for two partitioning tasks, the balanced graph partitioning problem and modularity maximization.

The traditional definition of balanced graph partitioning asks for a division of the vertex set into k subsets of (nearly) equal size such that the number of edges between different subsets is minimized. With very different approaches, some of which are particularly suitable for dynamic graphs, the portrayed techiques offer inherent parallelism and/or solutions with a high quality.

Modularity is a widely used quality measure for community detection, a related partitioning problem into an unknown number of subsets. We present parallel heuristics for maximizing modularity and the network analysis tool suite they are embedded into. Finally, we outline algorithmic connections between solvers for the two tasks of balanced graph partitioning and modularity maximization in complex networks.