
## 2. Related Work

The identification of clusters in graphs and networks has received significant attention. In our review we focus on a representative set of algorithms that minimize the normalized cut with or without spectral decomposition. We also review the existing methods for selecting the number of clusters.

## 2.1. Optimization Of Normalized Cut

Spectral partitioning of graphs was first proposed by Donath and **Hoffman in the 1970's [14].**
Interest in the techniques was renewed in the 1990's when Pothen et al. described an algorithm for bi-partitioning using the Fiedler vector [15]. Hendrickson et al. and Karypis et al.

contributed with multilevel algorithms for more efficient spectral partitioning [16, 17].

The normalized cut metric was introduced by Shi and Malik in [9]. They demonstrated how the bipartitioning task, with the objective of minimizing the normalized cut, could be relaxed to construct a generalized eigenvalue problem, and was thus related to spectral partitioning. The eigenvector corresponding to the second-smallest eigenvalue of the graph Laplacian identifies the bipartitioning (the real values in the eigenvector must be mapped to two discrete values for partitioning). This established the connection between minimization of normalized cut and spectral partitioning. Shi and Malik proposed a recursive bipartitioning scheme in order to partition a graph into k **clusters. In [18], Meila and Shi proposed an**
algorithm that calculates k eigenvectors (thereby associating k **real values with each node** in the graph) and then uses a clustering algorithm, such as k**-means, to do the partitioning** in ℜ
k**. Ng et al. observed in [19] that the algorithm in [18] is susceptible to failure when**
there is substantial variation in the degree of connectivity between clusters. They proposed an alternative algorithm that uses a different normalization in both the eigenvalue problem and the construction of feature vectors prior to the application of k**-means.**
All of these algorithms involve a computationally expensive eigendecomposition. To address the computational difficulties for large graphs, Fowlkes et **al. described a procedure** that uses the Nystr¨om method to reduce the complexity of the eigenvalue problem [10].

This does significantly reduce the computational overhead, but it is **not enough to make the**
eigendecomposition algorithms scalable to large graphs. Yan et al. recently described an algorithm for fast approximate spectral clustering [20], but the focus is not on clustering for graphs (rather it addresses real-valued feature vectors).

Dhillon et al. introduced a much faster algorithm for minimizing normalized cut in [11];
the graph is first greedily coarsened, then the coarsened graph is **partitioned using a region** growing procedure [17] and finally weighted kernel k**-means clustering is applied to each** partition to refine the clustering.

Other methods also exist that strive to optimize related cost functions; for example Sharon et al. proposed a scalable hierarchical clustering using *ratio association* (the normalization term is the number of nodes in clusters) [21]. Other examples **include the work by**
Ding et al. [22], Sharon et al. [23], Akselrod-Ballin et al. [24], and Corso et **al. [25] that use**
the sum of internal weights of clusters as the normalization term.

## 2.2. Model Order Selection

The problem of selecting the number of clusters is almost as old as clustering itself. In the following discussion, k
∗ **denotes the number of clusters that a given approach identifies**