Date of Submission: 07.12.2015

High-quality graph partitionings are useful for a wide range of applications, from distributing data of a social network to route planning to simulations using the finite element method. In the graph partitioning problem, the goal is to distribute all vertices of a given graph onto k blocks in a way that ensures every block has a weight below the maximum allowed weight of (1+ε) times the average block weight and optimizes a certain metric- often minimizes the global cut, meaning the sum of the weights of all edges that run between distinct blocks. In this thesis, we engineer a multi-level graph partitioning algorithm in Giraph using the perspective of a vertex so that no global view of the graph is necessary. Shortly summarized, our algorithm uses a label propagation algorithm to iteratively compute a clustering of the process graph and contract this clustering, partitions the coarsest level of that contraction using a centralized partitioning algorithm and then performs a local search iteratively on each level using the same label propagation algorithm as before to improve the partitioning. After introducing an