Monte Carlo Partitioning of Graphs with a Self-Organizing Map

A Monte Carlo algorithm for partitioning graphs is presented. The algorithm is based on the self-organizing map, an unsupervised, competitive neural network. A mean-field analysis suggests that the complexity of the algorithm is at most is on the order of O(n³/|E|), where n is the number of vertices of the graph, and |E| the number of edges. This prediction is tested on a class of random graphs. Scaling laws that deviate from the mean-field prediction are obtained. Although the origin of these scaling laws is unclear, their consequences are discussed.