Abstract:Graph partitioning is the primary work of large-scale distributed graph processing, which plays a fundamental role in storage, query, processing, and mining of graph applications. Since graph data in the real world are always dynamic, the research of dynamic graph partitioning is a hot topic. This study systematically introduces the current algorithms for dynamic graph partitioning, which including streaming graph partitioning algorithm, incremental graph partitioning algorithm, and graph repartitioning algorithm. Firstly, the study introduces three different partitioning strategies, two different dynamic sources of graph and dynamic graph partitioning problem. Then, three different streaming graph partitioning algorithms are introduced, including hash algorithm, neighbor distribution-based algorithm, and novel algorithm. Secondly, two different incremental graph partitioning algorithms, single element incremental graph partitioning, and batch incremental graph partitioning are introduced. Thirdly, the repartitioning algorithm for graph structure and the repartitioning algorithm for graph computation are introduced, respectively. Finally, based on the analysis and comparison of the existing methods, the main challenges of dynamic graph partitioning are summarized and the corresponding research problems are proposed.