DEPL: A Dual-Balanced Streaming Edge Partitioning in Linear Runtime
摘要
Partitioning a large graph into multiple edge-balanced subgraphs by minimizing the number of cutting vertices (replication factor), plays a crucial role in distributed graph computing tasks. However, existing methods often overlook that vertex imbalance can also lead to workload imbalance, and their partitioning time becomes prohibitively long when the number of partitions is large. To address these issues, this paper investigates a dual-balanced edge partitioning problem, aiming to minimize the replication factor while satisfying both vertex and edge balance. We propose DEPL, a lightweight two-phase dual-balanced partitioner. In the first phase, vertices are grouped into clusters using a streaming clustering algorithm. In the second phase, the generated clusters are leveraged to assign edges by a partitioning strategy. Experimental results demonstrate that DEPL achieves better dual balance than state-of-the-art partitioners, while also maintaining a low replication factor. When the number of partitions is large, its runtime can be an order of magnitude lower than that of stateful streaming partitioners.