cluster-analysis - 玩具图聚类中“ufactor”的解释

Question

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

然后，我尝试使用不同ufactor的值 143，METIS开始执行预期的集群，如下所示 -

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

Answer 1

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

 imbalance*(number of vertex/number of cluster)

对于第一张图片（默认聚类）- 大聚类中的顶点数- 1*(14/2)=7，因此第二个聚类也在14-7=7 第二张图片中（ufactor 143）-

imbalance=1+143/1000=1.143

so, 1.143*(14/2)=8.001

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