Framework de benchmark para seleção de algoritmos de particionamento de grafos

Abstract

Sensor networks, social networks, computer systems, road networks, route maps, and scientific datasets can be represented as graphs, that is, sets of elements connected by relationships. In such systems, graph partitioning means dividing the network into balanced parts while reducing the connections cut between them. This task belongs to combinatorial optimization and appears in practical problems involving data organization, computational load distribution, network analysis, and communication reduction between components of a system. Because different graph structures, numbers of parts, and time limits may favor different strategies, the choice of a partitioning algorithm is not universal. This work investigates this variation through an experimental benchmarking framework for the graph partitioning problem, combining graph optimization, controlled experimentation, algorithm selection, and machine learning. The study compared the multilevel partitioners METIS and KaHIP with four metaheuristics implemented in Rust: simulated annealing, tabu search, iterated local search, and GRASP. The campaign evaluated 60 real and synthetic graphs, 298 combinations between graph and number of parts, and seven time limits, resulting in 2,071 complete comparisons. The results show a heterogeneous scenario in which the best choice depends on the instance and the time limit. The metaheuristics obtained 950 strict wins across 45 graphs, with an increase from 30.3 percent at 1 second to 52.0 percent from 60 seconds onward, while the multilevel methods maintained an advantage in other evaluated regions. In a paired comparison with all six algorithms, the inclusion of iterated local search and GRASP produced 135 changes in the winning algorithm, including 74 cases in which the best family changed from multilevel to metaheuristic. To turn these results into interpretable support for decision-making, classification and regression trees were trained as a machine learning technique that produces interpretable rules. These models achieved balanced accuracy between 0.7958 and 0.8810 on the reference binary targets, indicating that part of the observed variation can be described by patterns associated with graph properties, the number of parts, and the time limit. The work delivers an experimental dataset, a temporal comparison protocol between distinct algorithm families, and an interpretable analysis to support instance-specific algorithm selection. The conclusions are limited to the evaluated panel, implementations, and execution environment.