Minimization of the criterion proposed by Rosvall and Bergstrom [7] results in a coarsegrained representation of the information flow through the network. Their proposed clustering objective aims to compress the underlying random walk on a graph without losing important network structures. To facilitate this, a coding is designed as follows: every cluster is assigned to a unique code; in a given cluster, every node is also assigned to a unique code. However two nodes in different clusters are allowed to be assigned to the same code.

The algorithm then strives to minimize the average description length **of a single step of a** random walk.

The algorithm by Blondel et al. targets maximizing modularity [56]. Modularity (Q**) is**
defined as the total fraction of intra-cluster sum-weight minus the expected fraction if the edges (and weights) were distributed randomly while the node degrees were preserved:

$$Q=\sum_{i=1}^{k}\left(\frac{w(C_{i},C_{i})}{M}-\frac{d(C_{i})^{2}}{M^{2}}\right),\tag{19}$$

where M =Pi Pj w(i, j**). Modularity provides a valuable metric of the connectedness of**
clusters, but a number of authors have demonstrated that it suffers from a resolution limit when used to select the number of clusters [59]. The partitioning that maximizes modularity will generally not isolate clusters if the number of edges in the cluster **is a small fraction of the**
total number of edges in the graph. The reason behind the resolution limit of modularity is the second term in the summation of (19); when the network gets larger, M **increases** monotonically. However the cluster degrees are not necessarily a function of the network size and are often bounded, regardless of the number of nodes [60]. This results in d(Ci)
2/M2 ≪ 1 and hence the value of modularity becomes dependent only on w(Ci)/M**. By normalizing**
the summation by d(Ci**) as suggested in [12], the resolution limit phenomena is resolved; but**
we have

$$Q_{\rm normalized}=\sum_{i=1}^{k}\frac{1}{d(C_{i})}\left(\frac{w(C_{i},C_{i})}{M}-\frac{d(C_{i})^{2}}{M^{2}}\right)=\frac{1}{M}\left[{\rm NAssoc}({\cal C}_{k})-1\right].\tag{20}$$

i.e., maximization of Qnormalized **and normalized association are equivalent.**
5.2. Synthetic Graphs We first analyze the performance on synthetic graphs, for which the true clustering behavior is known. We use benchmark graphs developed by Lancichinetti, Fortunato, and Radicchi [61] (LFR graphs). These random graphs are designed based on the planted partition model [62]. Each node is assigned to one of k **clusters. When edges are added to the**
graph, the probability that the edge is between nodes in the same cluster is 1 − µ **and the** probability that the edge joins nodes from different clusters is µ**. The LFR benchmarks have**
heterogeneous cluster sizes with user-specified lower bound and upper bound, cmin and cmax, respectively. Furthermore the node degrees are upper-bounded by dmax **and the average node** degree is denoted by davg . As µ **decreases, edges are increasingly likely to be intra-cluster,**
making the partitioning task easier.

The Meila-Shi algorithm performs at least as well as the other spectral clustering algorithms (Ng-Jordan-Weiss [19] and Shi-Malik [9]) and hence we only display the Meila-Shi results. The local search of Dhillon-Guan-Kulis is also excluded often, because it results in negligible improvement while it introduces a very large computational overhead.