Distributed balanced edge-cut partitioning of large graphs having weighted vertices

Sammanfattning: Large scale graphs are sometimes too big to store and process on a single machine. Instead, these graphs have to be divided into smaller parts and distributed over several machines, while minimizing the dependency between the different parts. This is known as the graph partitioning problem, which has been shown to be NP-complete. The problem is well studied, however most solutions are either not suitable for a distributed environment or unable to do balanced partitioning of graphs having weighted vertices. This thesis presents an extension to the distributed balanced graph partitioning algorithm JA-BE-JA, that solves the balanced partitioning problem for graph having weighted vertices. The extension, called wJA-BE-JA, is implemented in both the Spark framework and in Scala. The two main contributions of this report are the algorithm and a comprehensive evaluation of its performance, including a comparison with the recognized METIS graph partitioner. The evaluation shows that a random sampling policy in combination with the simulated annealing technique gives good results. It further shows that the algorithm is competitive to METIS, as the extension outperforms METIS in 17 of 20 tests.