(The problem is: Given an edge-weighted graph G and a number c. Partition the
nodes of G into c approximately equal-sized disjoint groups (clusters) such
that the total weight of those edges that connect nodes from different
clusters is minimal.)
I have a paper by Jin-Tai Yan and Pei-Yung Hsiao on the related problem of
graph bisectioning ('A fuzzy clustering algorithm for graph bisection',
Information Processing Letters 52 (1994)), but I would be interested in
alternative approaches and/or experimental results.
Also, in my application, the graph partitioning problem can be weakened in
that clusters need not be disjoint, but the nodes may to a certain degree
belong to several clusters (i.e., clusters are fuzzy sets), such that the sum
of the membership values is one, for each node. I would also be interested in
other approaches than FCM to this fuzzy graph partitioning problem.
Thanks for any help,
Claudia