玩具图聚类上“ ufactor”的解释 [英] Interpretation of 'ufactor' on a toy graph clustering

问题描述

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

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.

然后，我尝试使用其他 ufactor 和值143， METIS 开始使
像以下内容一样完成预期的群集-

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

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

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）。默认情况下 imbalance = 1 。最大簇中的顶点数-

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

 imbalance*(number of vertex/number of cluster)

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

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

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

That allows the largest cluster to have 8 vertex.

这篇关于玩具图聚类上“ ufactor”的解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！