Interpretation of 'ufactor' on a toy graph

2020-04-01 07:54发布

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.

enter image description here

Then, i tried with different ufactor and at value 143, METIS starts to do the expected cluster like the following-

enter image description here

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.

1条回答
家丑人穷心不美
2楼-- · 2020-04-01 08:26

Imbalance=1+(ufactor/1000). By default imbalance=1. Number of vertex in largest cluster-

 imbalance*(number of vertex/number of cluster)

For first picture(default clustering)- number of vertex in larges cluster- 1*(14/2)=7, so the second cluster is also 14-7=7 In the second picture(ufactor 143)-

imbalance=1+143/1000=1.143

so, 1.143*(14/2)=8.001

That allows the largest cluster to have 8 vertex.

查看更多
登录 后发表回答