as the true number of clusters.

Numerous authors have used some notion of quality of clustering, usually based on some definition of the inter- and intra-cluster distances, to identify the **number of clusters. Let**
F(k) denote this notion for a given partitioning to k clusters. F(k**) is then examined for**
various values of k. Partitionings for different values of k **can be obtained from a hierarchical** clustering, or alternatively, by several flat partitionings.

If F is not a monotonic function of k**, the approach is usually to take** k
∗ **= arg max**k F(k)
or k
∗ = arg mink F(k) (depending on the definition of F**). The majority of the methods**
discussed in [26] and [27] are of this type; Calinski and Harabasz [28], C-index [29], Baker and Hubert [30], and cubic clustering criterion [31] are among the most effective ones [26].

Tibshirani et al. [32] define F(k**) as the** gap**, that is the difference of the average pairwise**
distance of the data points of the clustering at k th **level and the expected value of the same**
measure of some reference model. This is similar to modularity [6] (discussed later) in the sense that it compares the clustering results to a reference model. None of these methods are directly applicable to graph clustering algorithms; the calculations of the defined metrics require pairwise distances which are not immediately available from a graph representation.

Possible distance metrics include the shortest path [33] or the diffusion distance [8]; however the shortest path is very sensitive to noise and the calculation of the diffusion distance requires eigendecomposition.

In the case where F is a monotonic function of k**, the only extremal values of** F(k)
correspond to trivial values of k. Hence, the value of F(k**) corresponding to two or more**
choices of k **are examined to quantify the significance of a given level of a hierarchical** clustering [34–36]. In order to assess the clustering at level k **of the hierarchy, Gnanadesikan** et al. [34] propose the fraction F(k)/F(k − 1), Arnold [37] use the value of F(k) − F(k − 1), Krzanowski and Lai [35] employ the fraction |F(k) − F(k − 1)|/|F(k + 1) − F(k)|**, and** Pederson and Kulkarni [36] suggest using the fraction 2×F(k)/ (F(k − 1) + F(k **+ 1)). The** latter two approaches are the most similar to what we propose in Section 4 in the sense that they use the preceding and succeeding levels of the hierarchy to obtain the significance of the clustering at level k**. However the approaches in [35, 36] are potentially susceptible to**
noise due to the division; small perturbations in the weights could lead **to dramatic changes** in the selected model order.

Other approaches to selecting the number of clusters are based on the adoption of (semi-
)parametric models for the structure of the graph. This allows the **application of model**
selection techniques based on concepts such as the Bayesian InformationCriterion (BIC)
[38], and Akaike Information Criterion [39]. Despite the strong theoretical support for these methods, the adoption of a parametric model for the graph structure is undesirable. The models are often overly restrictive and do not adequately capture **the properties of many** real-life networks. An example is the requirement in [40, 41] that the input data are normally distributed (after projection of the graph into a real space). The more general methods based on mixture models do not scale well to very large graphs; even the recent approaches have only been applied to graphs with a few thousand nodes [42–44].

Some heuristics are based on the sizes of the clusters that are merged at different levels of the clustering hierarchy [45, 46]. The authors in [46] suggest that when two clusters with large number of nodes are merged, a significant amount of detail is lost; hence such an instance is potentially where a hierarchical clustering algorithm should stop. The authors