FCM for Graph Partitioning

Claudia Leopold (claudia@idec04.inf.uni-jena.de)
Fri, 1 Mar 1996 22:53:51 +0100


Has anybody done work on applying fuzzy c-means clustering (FCM) to graph
partitioning?

(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