2w(u, v)/ (d(u) + d(v)), so that a matrix of the improvements is constructed. Here we assume that initially there are no self-loops, but if there are, the value **of improvements are**
computed by (4) presented shortly. Throughout the agglomerative clustering procedure, d(·), w(·, ·), and ∆(·, ·**) are updated at each stage as described below.**
At each iteration, the pair (u
∗
, v∗) = argmax(u,v)∆(u, v**) is selected for merging to create**
a larger cluster, uv∗. The degree is computed for the newly constructed cluster, d(uv∗) =
d(u
∗
)+d(v
∗
**). The weights and the improvement matrices are updated by removing the rows**
and columns corresponding to u
∗ and v
∗
**, and inserting a new row and column corresponding**
to uv∗**(rows and columns are not removed or added in our implementation, but this is the**
practical effect). The weight matrix is updated as follows:

$$w(u v^{*},x)=w(x,u v^{*})=w(u^{*},x)+w(v^{*},x),$$
$$\left({\boldsymbol{3}}\right)$$
$$\quad(4)$$
, x), (3)
and the improvement matrix update is:

$$\Delta(u v^{*},x)=\frac{w(u v^{*},u v^{*})+w(x,x)+2w(u v^{*},x)}{d(u v^{*})+d(x)}-\frac{w(u v^{*},u v^{*})}{d(u v^{*})}-\frac{w(x,x)}{d(x)},$$
, (4)
for all the clusters, x**, adjacent to either** u
∗ or v
∗
**. The self-weights are also calculated by:**

$$w(u v^{*},u v^{*})=w(u^{*},u^{*})+w(v^{*},v^{*})+2w(u^{*},v^{*}).$$
$$\left(5\right)$$
, v∗). (5)
For all pairs of nodes (u, v**) not adjacent to** u
∗ and v
∗
, the weights w(u, v) and improvements ∆(u, v) remain unchanged. The above sequence of steps is repeated n − **1 times to** form the clustering hierarchy.

## 4.2. Model Order Selection

Many of the clustering algorithms require the number of clusters to **be provided to the**
algorithm a priori. However such information is often not available in practical situations making the decision about the number of clusters an issue in itself.

It is worth noting that the stage number (k) that maximizes NAssoc(Ck) does not necessarily correspond to a meaningful number of clusters.6 **Here we propose a simple but effective**
approach to model order selection. Let C
∗

k = argmaxCkNAssoc(Ck**) denote the partition that**
maximizes normalized assocation over all partitions of V into k **clusters. To carry out model**
order selection, we examine the *curvature*7**of NAssoc(**C
∗

k
) which we define as

$$\begin{array}{r l}{\operatorname{Curv}(k)={\big(}\operatorname{NAssoc}({\mathcal{C}}_{k}^{*})-\operatorname{NAssoc}({\mathcal{C}}_{k-1}^{*}){\big)}-{\big(}\operatorname{NAssoc}({\mathcal{C}}_{k+1}^{*})-\operatorname{NAssoc}({\mathcal{C}}_{k}^{*}){\big)}}\\ {=}2\operatorname{NAssoc}({\mathcal{C}}_{k}^{*})-\operatorname{NAssoc}({\mathcal{C}}_{k-1}^{*})-\operatorname{NAssoc}({\mathcal{C}}_{k+1}^{*}).}\end{array}$$

$$({\hat{0}})$$
