
## Algorithm 1 **Ganc: Greedy Agglomerative Normalized Cut** Greedy Agglomeration

1: Build the initial ∆ matrix, and NAssoc(Cn) ←Pu∈V w(**u, u**)/d(u)
2: for k = n − **1 to 1** do 3: (i
∗
, j∗) ← arg maxi,j ∆(**i, j**)
4: NAssoc(Ck) ← NAssoc(Ck+1**) + ∆(**i
∗
, j∗)
5: **Update rows and columns of ∆, the weights, and the degrees corresponding to clusters**
i
∗ and j
∗
**(3 - 5)**
6: **end for**
MODEL ORDER SELECTION
1: for k = n − **1 to 2** do 2: Calculate Curv(k**) (6)**
3: **end for**
4: k
∗ ← arg maxk Curv(k**) or provided by the user**
REFINEMENT
1: **Obtain flat partitioning for level** k
∗

2: Build the initial B and I **(7), and** *refine* ← **true**
3: **while** *refine* do 4: ¯δ ← 0 5: for u **= 1 to** n do 6: if u ∈ Ciis on the boundary and maxj δ(u, i, j) > 0 **then**
7: Move u **from** Ci to Cj
∗**, where** j
∗ = arg maxj δ(**u, i, j**)
8: Update B, I**, the weights, and the degrees (9 - 18)**
9: ¯δ ← ¯δ + δ(**u, i, j**∗)
10: **end if**
11: **end for**
12: if ¯δ = 0 **then**
13: *refine* ← **false**
14: **end if**
15: **end while**
fall-off which require eigendecomposition (e.g., [49] and [47]). Performing an eigendecomposition to study the eigenvalue fall-off for all of the eigenvalues requires O(n 3**) operations.**
To implement the refinement step, we use the map data structure to store and update B. Every row of B **is stored in a map (C++ STL implementation of the map data structure** is used [58]). Updates (9) to (12) are performed in constant time. To access each map entry of a row of B to insert, update, or delete, no more than O(log k**) operations are required,** because the maximum number of clusters connected to a boundary **node is strictly less than** k. Updates (13), (14), and (15) each take no more than O(log k**) operations and are repeated**
for all neighbors of a node that is moved. We have observed through experiments that nodes with larger degrees do not tend to be on the boundaries and hence the average number of neighbors to be updated is practically smaller than the average node **degree. (16), (18), and** any insertion to or deletion from the set of boundary nodes are performed in O(log k**) time.**