Monte Carlo Partitioning of Graphs with a Self-Organizing Map

Eric Bonabeau () and Florian Hénaux
Additional contact information
Eric Bonabeau: Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA
Florian Hénaux: ENST 46 rue Barrault, 75634 Paris Cédex 13, France

International Journal of Modern Physics C (IJMPC), 1998, vol. 09, issue 07, 1107-1119

Abstract: 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 ofO(n3/|E|), wherenis 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.

Keywords: Graph Partitioning; Self-Organizing Map; Monte-Carlo Simulation; Scaling (search for similar items in EconPapers)
Date: 1998
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183198001011
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:09:y:1998:i:07:n:s0129183198001011

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183198001011

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().