I am trying to do a imbalanced partition by METIS. I do not need equal number of vertices in each cluster(which is done by default in METIS). My graph has no constraints, it's a undirected unweighted graph. Here is a example toy graph clustered by METIS without no ufactor
parameter.
Then, i tried with different ufactor
and at value 143, METIS
starts to
do the expected cluster like the following-
Can anybody interpret this. Eventually, I want to find a way to guess an ufactor
from any unbalanced and undirected graph that will minimize the normalized cut without doing any balance necessarily.
Imbalance=1+(ufactor/1000)
. By defaultimbalance=1
. Number of vertex in largest cluster-For first picture(default clustering)- number of vertex in larges cluster-
1*(14/2)=7
, so the second cluster is also14-7=7
In the second picture(ufactor 143)-That allows the largest cluster to have 8 vertex.