玩具图聚类上 'ufactor' 的解释

Question

我正在尝试通过 METIS 进行不平衡分区。我不需要每个集群中的顶点数量相等（在 METIS 中默认完成）。我的图没有约束，它是一个无向的未加权图。这是一个由 METIS 聚类的玩具图示例，没有 ufactor 参数。

然后，我尝试使用不同的 ufactor，在值 143 处，METIS 开始 像下面这样做预期的集群-

任何人都可以解释这个。最终，我想找到一种从任何不平衡和无向图中猜测 ufactor 的方法，该方法将最小化归一化切割而无需进行任何平衡。

Answer 1

Imbalance=1+(ufactor/1000)。默认 imbalance=1。最大簇中的顶点数-

 imbalance*(number of vertex/number of cluster)

对于第一张图片（默认聚类）- larges cluster 中的顶点数- 1*(14/2)=7，所以第二个簇也是14-7=7 第二张图(ufactor 143)-

imbalance=1+143/1000=1.143

so, 1.143*(14/2)=8.001

这允许最大的簇有8个顶点。