Graph partitioning using homotopy based fast annealed neural networks

Graph partitioning is a typical combinatorial optimization problem and has many practical applications. Due to its combinatorial nature, graph partitioning problem is very difficult to solve using most of the standard optimization algorithms. Some algorithms for graph partitioning problem, such as Simulated Annealing(SA) involve large computation. In [I], Mean Field Annealing(MFA) neural networks was applied to graph partitioning problem and simulation results were very good. The execution times of MFA in graph partitioning problem is proportional to N, the number of nodes in a graph, which would result in large computation for a large scale graph. It will save time if we can find a faster algorithm. In this paper, we treat MFA algorithm as a homotopy problem and derive the ordinary differential equations which MFA approach should obey. Based on this, an adaptive cooling coefficient control algorithm is proposed. Simulation results indicate the proposed algorithm can save a lot of time and behaves almost the same as MFA.