Graph Partitioning with Self-Organizing Maps

Eric Bonabeau and Florian Henaux

Working Papers from Santa Fe Institute

Abstract: Self-organizing maps with variable local topology are shown to constitute a reasonably good heuristic to find approximate solutions to the NP-complete k-way graph partitioning problem, where a weighted graph has to be divided into k clusters of equal size while minimizing the total weight of inter-cluster edges. The equal size constraint is implemented through a distribution of training points that the map tends to approximate, and the minimal cut constraint is implemented through the simultaneous update of neighboring nodes. A mean-field analysis suggests that the complexity of the algorithm is at most in , where n is the number of vertices of the graph, and the number of edges. This prediction is tested on a class of random graphs.

Submitted to: Neurocomputing.

Keywords: Neural networks; self-organizing maps; graph partitioning (search for similar items in EconPapers)
Date: 1998-07
New Economics Papers: this item is included in nep-cmp and nep-evo
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:wop:safiwp:98-07-062

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().