Google Pregel论文中的半聚类公式的意义是什么？

Question

在Google Pregel paper中提到了半聚类算法。使用以下公式计算半聚类的得分

​

​

哪里

Ic是所有内部边的权重之和

Bc是所有边界边的权重之和。

Vc是半簇中的顶点数，并且

fb是边界边缘分数因子(用户在0和1之间定义)

算法非常简单，但我不能理解上面的公式是如何得出的。请注意，分母是Vc顶点数之间可能的边数。

有没有人能解释一下？

Answer 1

如果你考虑它要捕获的数量，那么这个分数是有意义的。

这里要解决的问题是找出将图的顶点放置到semi-clusters (简单的一组顶点，其中每个顶点可以位于多个半簇中)中的最佳方法，并在半簇总数上设置一些上限。因此，找到“最佳”方法的一种方法是将分数分配给任何潜在的半群集(换句话说，分配给任意一组顶点)。然后，问题就变成了最大化总分的问题。

因此，半簇是用来捕获图中的集团的。例如，在社交图中，半群集可能是高中篮球队的成员。

因此，更多的内部边等同于一个“更好的”半群集。这解释了分子中的I_c。类似地，你想要有很少的边界边，因为如果有很多边界边，那么这意味着可能有一个更好的半群包含你正在检查的那个。这给出了分子中的-f_b * B_c。f_b只是一个比例因子，这样您就可以调整要指定边界边的惩罚程度。

分母也是一种比例因子。它用于归一化半聚类得分，以便小聚类不会完全被较大聚类所支配。一个极端的例子是，如果你考虑世界上每个人的半群体。显然，没有边界边缘和大量的内部边缘，但毫无疑问，它是一个没有高中篮球队那么有用的半群。

Answer 2

它与集团有关。

V_c * (V_c - 1)是大小为V_c的集团中的边数。

因此，如果您对组I_c中的所有边求和，这是获得算术平均值的适当归一化。

即I_c / (V_c * (V_c - 1))是集团内部的平均权重。

现在，- f_B * B_c项是对传出边的惩罚。我的意思是，它应该只除以V_c，但这是个人喜好，因为我假设预期的传出边缘与集团成员的数量成比例，而不是与这个的平方。