Google Pregel 论文中提到了半聚类算法。使用以下公式计算半集群的分数
在哪里
Ic 是所有内部边
的权重之和 Bc 是所有边界边的权重之和
Vc 是半簇中的顶点数
fb 是边界边得分因子（用户定义在 0 和 1 之间）
该算法非常简单，但我无法理解上述公式是如何得出的。请注意，分母是 Vc 个顶点之间可能的边数。
有人可以解释一下吗？
问问题
869 次
2 回答
9
如果您考虑要捕获的数量，则该分数是有意义的。
这里要解决的问题是找出将图的顶点放入半簇（只是一组顶点，其中每个顶点可以位于多个半簇中）的最佳方法，并且总数量有一些上限半集群。因此，找到“最佳”方法的一种方法是将分数分配给任何潜在的半集群（换句话说，分配给任意一组顶点）。那么问题就变成了最大化总分的问题。
因此，半集群旨在捕获图中的集团。例如，在社交图谱中，半集群可能是高中篮球队的成员。
因此，更多的内部边缘等同于“更好”的半集群。这解释了I_c分子中的 。同样，您希望边界边缘很少，因为如果有很多边界边缘，那么这意味着可能会有一个更好的半组包含您正在检查的那个。这给出了-f_b * B_c分子中的 in。f_b只是一个比例因子，以便您可以调整要分配边界边缘的惩罚量。
分母也是一种比例因子。它用于标准化半集群分数，以便小集群不会完全被大集群控制。一个极端的例子是，如果你考虑世界上每个人的半群体。显然没有边界边缘和大量的内部边缘，但毫无疑问，它是一个没有高中篮球队有用的半组。
于 2012-07-05T08:31:02.837 回答
1
它与派系有关。
V_c * (V_c - 1) 是大小为 V_c 的团中的边数。
因此，如果您对组 I_c 中的所有边求和，则这是获得算术平均值的适当归一化。
即 I_c / (V_c * (V_c - 1)) 是clique 内的平均重量。
现在 - f_B * B_c 项是对出边的惩罚。恕我直言，它应该只除以 V_c，但这是个人喜好，因为我假设预期的传出边与集团成员的数量成比例，而不是与这个的平方成比例。
于 2012-07-07T23:30:23.290 回答