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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.