Home | english  | Impressum | Sitemap | KIT

Edge-Based Graph Partitioning

Edge-Based Graph Partitioning
Forschungsthema:Graph Partitioning

Sebastian Schlag, Christian Schulz, Darren Strash

Topic Description

Edge-based partitioning is a relatively new formulation that partitions the edges of the input graph into k blocks of roughly the same number of edges. The goal now is to minimize the number of different partitions in which each vertex is a member. This formulation was introduced for PowerGraph, an extension of the think-like-a-vertex (TLAV) model of computation, that focuses on dividing edges among machines, which requires vertex-centric computations to be duplicated across machines to avoid communication overhead introduced by high-degree nodes in power-law graphs.  In this model, a balanced edge-based partition ensures that little communication occurs between machines containing the same vertex.

This problem, however, can be solved by using vertex-based partitioning approaches by creating a new graph with the split-and-connect transformation that has recently been introduced. In this thesis, we want to integrate this model into ParHIP (a parallel partitioning code that has been developed at KIT) to arrive at a distributed memory parallel algorithm for the problem.

You should have:

  • solid knowledge in algorithms and data structures
  • good knowledge in C++ and OpenMPI
  • motivation!