Google Pregel论文中半聚类公式的意义何在？

Question

Google Pregel论文中提到了半聚类算法.使用以下公式计算半聚类的得分

哪里

Ic是所有内部边缘
的权重之和Bc是所有边界边缘的权重之和
Vc是半群集中的顶点数量,
fb是边界边缘分数因子(用户定义在0和1之间)

该算法非常简单,但我无法理解上述公式是如何到达的.请注意,分母是Vc顶点数之间可能的边数.

有人可以解释一下吗？

Answer 1

如果你考虑它要捕获的数量,那么分数是有意义的.

这里要解决的问题是弄清楚将图的顶点放置到半集群中的最佳方法是什么(简单地是一组顶点,其中每个顶点可以在多个半集群中),并且在总数上有一些上限.半群集.因此,找到"最佳"方法的一种方法是将分数分配给任何潜在的半群(换句话说,分配给任意任意一组顶点).然后问题变成最大化总分.

因此,半群集旨在捕获图表中的派系.例如,在社交图中,半群可能是高中篮球队的成员.

因此,更多的内部边缘等同于"更好"的半群.这解释I_c了分子中的内容.类似地,你想要有很少的边界边,因为如果有很多边界边,那么这意味着可能有一个更好的半群包含你正在检查的那个.这给出-f_b * B_c了分子.f_b只是一个缩放因子,因此您可以调整分配边界边缘的惩罚.

分母也是一种缩放因子.它用于标准化半群集分数,以便小群集不会被较大群集完全控制.一个极端的例子是,如果你考虑世界上每个人的半群体.显然,没有边界边缘和大量的内部边缘,但毫无疑问,它是一个不如高中篮球队有用的半群体.