# What is the significance of the semi clustering formula in the Google Pregel paper?

Semi clustering algorithm is mentioned in the Google Pregel paper. The score of a semi cluster is calculated using the below formula

$\qquad \displaystyle S_c =\frac{I_c - f_BB_c}{\frac{1}{2}V_c(V_c - 1)}$

where

• $I_c$ is sum of the weights of all the internal edges,
• $B_c$ is the sum of the weights of all the boundary edges,
• $V_c$ is the number of edges in the semi cluster and
• $f_b$ is the boundary edge score factor (user defined between 0 and 1).

The algorithm is pretty straight forward, but I could not understand how the above formula was derived. Note that the denominator is the number of edges possible between $V_c$ number of vertices.

Think about what a "good" cluster is. It is a set of nodes which

• are strongly interconnected (strong cohesion) and
• weakly connected with nodes outside of the cluster (weak coupling).

In particular, the connection among the nodes should be stronger than the connection with the outside. And this is what they do there: $I_c$ is a measure for cohesion -- more and stronger edges inside the cluster mean more cohesion -- and similarly $B_c$ is a measure for coupling. $f_B$ is used to control the influence of coupling.

As for the denominator, they justify it in the slides:

The score is normalized by dividing with the number of vertices in the clique, so that large clusters do not receive artificially high scores.

That's actually wrong, but the idea is the same: they divide by the number of edges there could be -- which makes sense because they "count" edges in the numerator, too -- in order to get rid of size effects. Without this rescaling, a large cluster (with many edges) would have a higher score than a smaller on with the same or even better properties. You only want to score the quality of the clusters, though, so rescaling is in order.

I daresay that $\frac{I_c}{f_B B_c}$ would also make sense (and scale itself). Usually, such scores are formulated ad-hoc and their usefulness validated by experiments (over time). That is, somebody wrote it down, used it for clustering, looked at images and was satisfied with the result. Depending on what semantic the edge weights have, the score may also be a "good" approximation for a more complicated one that is harder to compute or makes clustering (computationally) harder. That said, most clustering algorithms in use are approximations -- because clustering is NP-hard -- so the choice of auxiliary score may influence runtime and result quality of those algorithms.

• I think the score is calculated using the mentioned formula and then divided by the # of vertices in the semi cluster. The denominator signifies the total # of edges possible in the cluster. What is the formula notation which you have used to change in the original query? Jul 5 '12 at 14:48
• @PraveenSripati: 1) Right, I adapted my answer. Did not read what they wrote carefully enough, trusting them -- my bad. 2) That's (a restricted version of) LaTeX. You can check out your post's source to see what I did there. See also here.
– Raphael
Jul 5 '12 at 21:46
• 1) Makes sense - not sure why they divided by the # of vertices again? 2) LaTex is nice, but the original query was more visual :) From a quick glance I could understand that it is. Maybe, I will get used to it. Thanks for the nice response. Jul 6 '12 at 1:13