A Star-Based Graph Partitioning Approach to Support “Master–Slave” Parallel Computing

Graph partitioning is a key step in the parallel and distributed processing of big graphs, aimed at improving efficiency while balancing load and reducing communication overhead. However, conventional partitioning methods often produce irregular inter-block communication patterns, leading to complex coordination costs. To address this issue, we propose a star-based graph partitioning approach that organizes partition blocks into a master–slave topology, where all inter-block communication is centralized through a master block. This structured design simplifies communication patterns and enhances parallel execution efficiency. Based on a cost-aware representation of graph processing, we formulate a partitioning objective that minimizes the overhead of the master block while maintaining balanced slave partitions. To achieve this, we develop a two-stage framework including initial partition generation and iterative refinement. The refinement stage incorporates a master minimization strategy and a slave balancing strategy to further improve partition quality. Extensive experiments on multiple benchmark datasets demonstrate that the proposed method effectively reduces communication overhead, improves parallelism, and provides an interpretable partitioning structure for distributed graph processing.