Graph Partitioning Algorithm For Distributed Graph Computation

With the advent of the information age,a large amount of graph data has been accumulated in real life.To achieve better performance,distributed graph computation systems process large scale graphs on a cluster of machines.For such systems,graph partitioning plays a significant role in improving their computing performance.The existing graph partitioning algorithms can be classified into offline graph partitioning algorithms and streaming graph partitioning algorithms.The first category requires global information for a graph during the partitioning,which is expensive in terms of time and memory for large-scale graphs.The second category,however,creates partitions based solely on the received edge information,which may result in lower performance than the offline methods.To address the problems mentioned above,two graph partitioning algorithms are proposed in this thesis,which can achieve high-quality partitions based on the local graph data information.The main contributions of this thesis can be summarized as follows.(1)A local graph partitioning with a two-stage heuristic method is proposed.The concept of local graph partitioning is introduced to consider only local information,i.e.,a part of the graph,instead of the graph as a whole,during the partitioning.Based on this idea,we propose a two-stage local partitioning algorithm,where the partitioning process is divided into two stages according to the structural changes of the current partition,and two different strategies are introduced to deal with the respective stages.Experimental results with real-world graphs demonstrate that the proposed algorithm outperforms the rival algorithms in most cases.(2)An adaptive local graph partitioning algorithm is proposed.The local graph partitioning is improved by partitioning several nodes at each step,instead of partitioning only one node,which can enhance the partitioning efficiency.Moreover,an adaptive local graph partitioning method is proposed.Experimental results demonstrate the adaptive local graph partitioning algorithm performs better than state-of-art in all cases,including the two-stage local graph partitioning algorithm.