在Google Pregel paper中提到了半聚类算法。使用以下公式计算半聚类的得分
在哪里
Ic是所有内部边缘的权重之和
Bc是所有边界边的权重之和
Vc是半簇中的顶点数，而
fb是边界边缘得分因子(用户定义在0和1之间)
该算法非常简单，但是我不明白上面的公式是如何得出的。注意，分母是顶点的Vc数之间可能的边数。
有人可以解释一下吗？
最佳答案
如果您考虑要捕获的数量，则该分数很有意义。
此处要解决的问题是找出将图的顶点放入半群集(简单来说是一组顶点，每个顶点可以在多个半群集中)的最佳方法是在总数上设置上限半集群数。因此，找到“最佳”方式的一种方法是将分数分配给任何潜在的半集群(换句话说，将分数分配给任意任意的顶点组)。然后，问题就变成了总分最大化。
因此，半集群旨在捕获图形中的集团。例如，在社交图中，半集群可能是高中篮球队的成员。
因此，更多的内部边缘相当于“更好”的半群集。这解释了分子中的I_c。同样，您希望边界边缘很少，因为如果边界边缘很多，则意味着可能会有一个更好的半组包含正在检查的半组。这在分子中给出了-f_b * B_c。 f_b只是一个比例因子，因此您可以调整要分配边界边缘的代价。
分母也是一种比例因子。它用于规范半集群分数，以使小集群不会完全被大集群所支配。一个极端的例子是，如果您考虑世界上每个人的半数。显然没有边界边缘和大量内部边缘，但是无疑这是一个比高中篮球队更有用的半团体。
关于algorithm - Google Pregel论文中的半聚类公式的意义是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11293919/