# how to appropriately determine the number of clusters in the graph partition problem?

As the title said: how to appropriately determine the number of clusters in the graph partition problem?

Here is the problem definition from multi-level graph partition:

The k-way graph partitioning problem is defined as follows: given a graph $$G = (V,E)$$ with |$$V$$| = $$n$$, partition $$V$$ into $$k$$ subsets, $$V_{1}, V_{2},...,V_{k}$$ such that $$V_{i}∩V_{j} = ∅$$ for $$i<> j$$, $$|V_{i}| = n/k$$, and the number of edges of $$E$$ whose incident vertices belong to different subsets is minimized.

The existing works have addressed the problem of given $$k$$ clusters, how to partition the vertices of graph $$G$$ to $$k$$ clusters.

However, for now, I don't know how to determine $$k$$ appropriately. And I believe $$k$$ is also the important parameter.

For example, for a relatively large $$k$$, it will result in a larger number of edge cut when the number of vertices is small. So in this case, smaller $$k$$ may be more suitable.

A straight forward way is to exhaustively enumerate all of possible $$k$$ which is lower than the maximum $$K$$. However, the overhead is too much. So is there any latest work about this problem?

Thanks very much!

• why this is related to the tag "Cluster Algebras"? – Wenze 'Sylvester' Zhang May 14 at 2:22