A Star-Based Graph Partitioning Approach to Support “Master–Slave” Parallel Computing
Applied Sciences · 22.10.2026 · 16 (21) · 10457
DOI: 10.3390/app162110457 ↗Kurz gefasst
Fachartikel in der Zeitschrift Applied Sciences, online erschienen am 22.10.2026. Verfasst von Guosun Zeng und 2 weiteren Autor:innen. Die Arbeit nennt 40 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, National Key Research and Development Program of China.
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
- National Key Research and Development Program of China
Zitieren
APA
Zeng, G., Cheng, T., & Jin, Y. (2026). A Star-Based Graph Partitioning Approach to Support “Master–Slave” Parallel Computing. Applied Sciences, 16(21), 10457. https://doi.org/10.3390/app162110457
Vancouver
Zeng G, Cheng T, Jin Y. A Star-Based Graph Partitioning Approach to Support “Master–Slave” Parallel Computing. Applied Sciences. 2026;16(21):10457. doi:10.3390/app162110457
BibTeX
@article{Zeng2026,
author = {Zeng, Guosun and Cheng, Tengteng and Jin, Yufei},
title = {A Star-Based Graph Partitioning Approach to Support “Master–Slave” Parallel Computing},
journal = {Applied Sciences},
year = {2026},
volume = {16},
number = {21},
pages = {10457},
doi = {10.3390/app162110457}
}
EUVIMED