in maximum improvement. If u is moved from Ci to Cj**, the corresponding cluster degrees**
and associations are updated:

$$\begin{array}{l}{{d(C_{i})^{\mathrm{new}}=d(C_{i})^{\mathrm{old}}-d(u)}}\\ {{d(C_{j})^{\mathrm{new}}=d(C_{j})^{\mathrm{old}}+d(u)}}\\ {{w(C_{i},C_{i})^{\mathrm{new}}=w(C_{i},C_{i})^{\mathrm{old}}-2I(u,i)^{\mathrm{old}}}}\\ {{w(C_{j},C_{j})^{\mathrm{new}}=w(C_{j},C_{j})^{\mathrm{old}}+2B(u,j)^{\mathrm{old}},}}\end{array}$$

and for all the neighboring nodes of u denoted by v, entries of B and I **are updated as** follows:

$$\begin{array}{c}{{I(v)^{\mathrm{new}}=I(v)^{\mathrm{old}}+w(u,v)}}\\ {{B(v,i)^{\mathrm{new}}=B(v,i)^{\mathrm{old}}-w(u,v)\Bigg\}}\\ {{I(v)^{\mathrm{new}}=I(v)^{\mathrm{old}}-w(u,v)}}\\ {{B(v,j)^{\mathrm{new}}=B(v,j)^{\mathrm{old}}+w(u,v)\Bigg\}}\\ {{B(v,i)^{\mathrm{new}}=B(v,i)^{\mathrm{old}}-w(u,v)\Bigg\}}\\ {{B(v,j)^{\mathrm{new}}=B(v,j)^{\mathrm{old}}+w(u,v)\Bigg\}}\end{array}$$
if v ∈ Cj, (13) if v ∈ Ci, (14)
$${\mathrm{if~}}v\not\in C_{i}{\mathrm{~and~}}v\not\in C_{j},$$

and finally

$$\left(13\right)$$
$$\left(14\right)$$
$$\left(15\right)$$
$$\begin{array}{l}{{B(u,i)^{\mathrm{new}}=I(u)^{\mathrm{old}},}}\\ {{I(u)^{\mathrm{new}}=B(u,j)^{\mathrm{old}},}}\\ {{B(u,j)^{\mathrm{new}}=0.}}\end{array}$$
$$\begin{array}{l}{(16)}\\ {(17)}\\ {(18)}\end{array}$$

While performing the updates (9) to (18), the set of boundary nodes is also updated.

Whenever a node is moved from cluster i to cluster j, its neighbors in cluster i **are added** to the set of boundary nodes. For some node v neighboring u, moving u **might result in** B(**v, i**)
new becoming zero in (15) for all i**; i.e., some nodes might be removed from the set of**
boundary nodes.

One pass through all the boundary nodes is considered a single refinement *iteration*.

When an iteration causes no positive improvement, the refinement procedure is stopped. Alternatively, one could specify the maximum number of refinement iterations. Note that although we prohibit the refinement step from emptying any cluster, we have not observed such an attempt in our experiments. 4.4. Implementation and Computational Complexity of GANC
We take a similar approach to [57] when implementing the agglomerative clustering procedure of GANC. Max-heaps and balanced binary trees are used to **store the rows of the ∆**
matrix and the adjacency matrix. A separate heap is also used to store the maximum of each row of ∆. This leads to the complexity of O(mh log(n**)) for the agglomerative clustering**
procedure, where h is the height of the generated dendrogram and m **is the number of edges** with non-zero weight (see [57] for details).

The model order selection step of the algorithm requires O(n) computations. The computational requirements are much less than those of the methods **analyzing the eigenvalue**