Abstract:The quality of graph partitioning greatly affects the communication overhead and load balance among computers, which is crucial for the performance of large-scale parallel graph computation. However, as the scale of graph data continues to increase, the execution time and memory overhead of graph partitioning algorithms have become inevitable. Therefore, it is necessary to study how to optimize the execution efficiency of graph partitioning algorithms. This study proposes a heuristic graph partitioning method based on weighted graph generation by breadth-first traversal, which introduces only a small amount of preprocessing time overhead while achieving lower communication overhead and better load balance. Experimental results show that our partitioning method reduces replication factors, lowers communication overhead, and only introduces a small amount of time overhead.