This quality function satisfies \(-2 \le Q^S(\mathcal {P}) \le 0\) . We prove that it is additive using \(q^S(\mathcal {C}) = -\frac{1}{n} - \frac{\sigma (\mathcal {C})}{\sigma _{max}}\) . Each evaluation of \(\sigma (\mathcal {C})\)  requires \(\mathcal {O}(|\mathcal {C}|^2)\)  distance computations for an arbitrary distance. However if \(d\)  is an Euclidean distance then \(\sigma (\mathcal {C}_1 \cup \mathcal {C}_2)\)  can be obtained from \(\sigma (\mathcal {C}_1)\)  and \(\sigma (\mathcal {C}_2)\)  with only one additional distance computation. Therefore all the \(\sigma (\mathcal {C})\)  can be obtained with \(n\)  distance computations in this case. Such a distance, based on random walks, was proposed in [1]}, [2]} together with an agglomerative community detection algorithm which computes the values of \(\sigma (\mathcal {C})\) . Thus this quality function can be used within this algorithm at no additional cost.
