For a fixed number of clusters, k**, we measure the quality of the partition via the**
normalized cut metric [9], defined as follows. For a node u**, denote the degree of** u by d(u) = Pv∈V w(u, v), and for a subset U ⊂ V of nodes, let d(U) = Pu∈U
d(u**) denote the**
cumulative degree of the subset. Similarly, for two disjoint subsets of nodes, V1 and V2**, let**
w(V1, V2) = Pu∈V1 Pv∈V2 w(u, v**) denote the sum of the weights of edges with one end in** V1 and the other end in V2. Let Ck denote the partition of nodes to k clusters, Ck = {C1**, . . . , C**k}
where Ciis the subset of nodes affiliated to cluster i**. The** *normalized cut* **metric is defined**
as

$$\mathrm{NCut}({\mathcal{C}}_{k})=\sum_{i=1}^{k}{\frac{w(C_{i},V\setminus C_{i})}{d(C_{i})}}.$$
$$\quad(1)$$. 
Minimizing the normalized cut can be interpreted as minimizing the similarity of nodes in different clusters, relative to the degree of each cluster. Alternatively, maximizing the intra-cluster similarity can be achieved by maximizing the *normalized association***, defined**
as

$${\rm NASsoc}({\cal C}_{k})=\sum_{i=1}^{\kappa}\frac{w(C_{i},C_{i})}{d(C_{i})}.\tag{2}$$

Moreover, maximizing normalized association is equivalent to minimizing normalized cut since w(Ci, Ci) +w(Ci, V \Ci) = d(Ci), and hence NAssoc(Ck) = k −NCut(Ck**). For the sake**
of readability, we adopt the maximization of normalized association as **our goal in developing** a clustering procedure.

## 4. Ganc: Greedy Agglomerative Normalized Cut

In this section, we describe a greedy algorithm for building an agglomerative clustering on a graph. Although we do not make guarantees about its accuracy, the algorithm is fast on sparse graphs and yields excellent performance on a variety of examples, as illustrated in Section 5. Moreover, GANC has a model order selection criterion and does not have to be provided with the number of clusters a priori. The algorithm consists of three steps: agglomerative clustering, model order selection, and refinement.

## 4.1. Agglomerative Clustering

We propose greedy maximization of normalized association via an agglomerative hierarchical clustering. In the following discussion, note that the number **of clusters at stage** k of the hierarchy is k. At stage k of the hierarchy, using the given partition, Ck**, two clusters are**
merged to form a new partition, Ck−1**. The two clusters to be merged are chosen greedily so**
that normalized association of stage k − **1 is maximized.**5 Initially, Cn is a function that maps nodes to unique clusters, 1, . . . , n**. The degree of**
every node u, d(u), is calculated. Furthermore, for every edge, (u, v) ∈ E, the improvement in normalized association by its contraction to obtain Cn−1 is stored in ∆(u, v) =