Tables 1 and 2 compare the performance of GANC with other clustering algorithms for these small, well-known datasets. The tables provide the average NAssoc per cluster
(NAssoc/k) and the Jaccard index. The "true" number of clusters is indicated within parentheses beside the name of each network11**. In Table 1, all algorithms (including GANC) are**
informed of the true number of clusters and instructed to generate a partitioning with that number of clusters. Table 1 indicates that the spectral clustering algorithms (Ng-JordanWeiss, Meila-Shi, and Shi-Malik) achieve similar performance in terms of **NAssoc. We note**
that when k is specified for these three networks, GANC identifies partitionings **with average**
NAssoc as large or larger than those of the partitionings identified by the spectral clustering techniques, with the exception of Shi-Malik in the case of the football network.

Table 1: Small real networks: k **known in advance (average NAssoc per cluster/Jaccard index). Maximum** NAssoc is indicated by bold text.

Karate(k = 2) Football(k = 11) PolBooks(k **= 3)**

GANC (refined) 0.872/0.89 0.704/0.820 0.88**/0.67**

Dhillon-Guan-Kulis 0.820/0.64 0.700/0.820 **0.87/0.64**

Ng-Jordan-Weiss 0.872/1.00 0.701/0.825 **0.82/0.57**

Meila-Shi 0.869/0.89 0.696/0.820 0.88**/0.67**

Shi-Malik 0.872/1.00 0.706/0.825 **0.86/0.67**

Table 2 compares the performance of algorithms that select the number of clusters based on some aspect of the data. The number of clusters selected by each algorithm is shown within parentheses after the Jaccard index. Rosvall's algorithm uses a description length metric to select the number of clusters [7]; Blondel's algorithm chooses the partitioning that maximizes the modularity [56]. A direct comparison of NAssoc is not valid when k **is not** fixed. The first row of this table shows the performance of GANC when the curvature plot is used to select the number of clusters. Although the selected number of clusters does not correspond to the true number of clusters for any of the networks, all three values can be explained. In the karate club network there is a group of students **who have weak ties to**
other members of the network and these are identified as a third cluster; in the football network, GANC isolates the independent teams; in the political books network, GANC does not identify a neutral cluster and assigns each of the neutral books to either the liberal or conservative cluster.

| Table 2: Small real networks: Jaccard index for the estimated model orders. Karate Football PolBooks GANC (curv) 0.80 (k = 3) 0.76 (k = 13) 0.69 (k = 2)) Blondel et al. 0.53 (k = 4) 0.70 (k = 11) 0.67 (k = 3) Rosvall-Bergstrom 0.71 (k = 3) 0.83 (k = 12) 0.63 (k = 5)   |
|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
