VSCT algorithm for graph partitioning based on volume, size, cuts and time. Issue 3 (4th May 2023)

• Record Type: Journal Article
• Authors: Sakouhi, Chayma; Khaldi, Abir; Ben Ghezala, Henda
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 38:Issue 3(2023)
• Page Start: 181
• Page End: 197
• Publication Date: 2023-05-04
• Subjects: Graph partitioning algorithms -- distributed graph processing systems -- volume -- size -- cuts -- time; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2023.2174540
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : Dealing with large-scale graphs requires an efficient graph partitioner that produces balanced partitions with fewer cut edges/vertices in a reasonable amount of time. Despite several algorithms that have been proposed, it is still insufficient. Even with the continuous growth of graph volume, they do not consider the graph volume during graph partitioning. Therefore, these algorithms generate an imbalanced workload. We propose a graph partitioner algorithm VSCT based essentially on four key metrics: Volume, Size, Cuts, and Time to maintain high-quality graph partitioning. Using real-world datasets, we show that VSCT performs an efficient partitioning quality against the existing graph partitioning algorithms.