Graph partitioning using a Simulated Bee Colony algorithm

Graph partitioning is a problem which has great practical importance. Because graph partitioning is an NP-complete problem, there has been much research attention focused on developing heuristics which find reasonably good approximations to optimal solutions. This study presents a Simulated Bee Colony (SBC) graph partitioning algorithm which is based on the foraging behavior of honey bees. A computer program which implemented the SBC algorithm was executed against 12 benchmark graph partitioning problems. The SBC algorithm produced partitions with better quality than the best published results for 10 of the 12 benchmark problems. The results suggest that Simulated Bee Colony algorithms are a highly effective technique for partitioning graphs in situations where partition quality is more important than real-time performance and that using SBC graph partitioning algorithms may be particularly useful in problem scenarios where the partition result is intended for reuse such as analyses of large communication graphs.