Monte Carlo Partitioning of Graphs with a Self-Organizing Map
Eric W. Bonabeau, Florian Hénaux · International Journal of Modern Physics C · 1998
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(n3/|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.