arXiv:1604.03993v1 [math.PR] 13 Apr 2016

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM
GEOMETRIC GRAPHS
ERIK DAVIS AND SUNDER SETHURAMAN

Abstract. We consider a large class of random geometric graphs constructed
from samples Xn = {X1 , X2 , . . . , Xn } of independent, identically distributed
observations of an underlying probability measure ν on a bounded domain
D ⊂ Rd . The popular ‘modularity’ clustering method specifies a partition Un
of the set Xn as the solution of an optimization problem. In this paper, under
conditions on ν and D, we derive scaling limits of the modularity clustering
on random geometric graphs. Among other results, we show a geometric form
of consistency: When the number of clusters is a priori bounded above, the
discrete optimal partitions Un converge in a certain sense to a continuum
partition U of the underlying domain D, characterized as the solution of a
type of Kelvin’s shape optimization problem.

1. Introduction
One of the basic tasks in understanding the structure and function of complex networks is the identification of community structure or modular organization, where by a community we mean a subset of densely interconnected nodes,
only sparsely connected to outsiders (cf. [33], [66]). A widely popular approach to
community detection is the method of modularity clustering, introduced by Newman and Girvan (cf. [60], [57]), which specifies an optimal clustering – that is, a
partition of the network – as the solution of a certain optimization problem (see
Section 2 for precise definitions). In particular, the method is used for a variety
of networks arising in scientific contexts, including metabolic networks [44], epigenetic networks [55], brain networks [47], and networks encoding ecological [31] and
political interactions [65].
On the other hand, a popular model of complex networks with geometric structure is the random geometric graph, where vertices are sampled from a geometric
domain and edge weights are determined by a function of the distance between vertices [34], [54], [62]. We note, a well-studied case is the unweighted version, when
the connectivity function is a threshold function of distance. These graphs are wellestablished mathematical models of various physical phenomena, such as continuum
percolation. They have also found use in a number of applied settings, including
the modeling of ad-hoc wireless networks [46], [11], [35], protein-protein interaction
networks [67], as well as the study of combinatorial optimization problems [26], [27].
In clustering studies of these graphs and their variants, the modularity functional
is often used to assess the quality of the clustering obtained [6], [25].
2010 Mathematics Subject Classification. 60D05,62G20,05C82,49J55,49J45,68R10.
Key words and phrases. modularity, community detection, consistency, random geometric
graph, gamma convergence, Kelvin’s problem, scaling limit, shape optimization, optimal transport, total variation, perimeter.
1

2

ERIK DAVIS AND SUNDER SETHURAMAN

In these contexts, it is a natural question to ask about the consistency of modularity clustering with respect to random geometric graphs. That is, one would
like to know how the modularity clusterings converge or stabilize as the number of
sampled data points or vertices grow, and how to characterize geometrically any
limit clusterings. From the point of view of applications, establishing consistency
is relevant to benchmarking performance. We will focus on a class of random geometric graphs, where a length scale is introduced in the connectivity function, so
that distances between adjacent vertices shrink as the number of data points grow,
and spatial scaling limits can be taken.
In this article, we study two questions: The first asks about the large limit
behavior of the modularity functional on these random geometric graphs, evaluated
on a fixed partition of the underlying geometric domain. The second question asks
whether the optimal modularity clusterings for the discrete graphs converge, and if
so to what geometric limit clustering.
With respect to the first question, when the fixed partition of the domain involves
at most K ≥ 1 sets, we show that the limit of the modularity functional, known
to be a priori bounded between −1 and 1, as the sample size grows, is of the form
1 − 1/K plus a term involving the partition, which vanishes when the partition
is ‘balanced’, that is when each set in the partition has the same volume with
respect to an underlying measure (Theorem 2.1). As a corollary, we obtain, for
these random geometric graphs, that the maximum of the modularity functional
taken over all partitions, as the sample size grows, tends to 1 (Corollary 2.2). These
limits prove, in the context of random geometric graphs, some heuristics given in
the literature (cf. Subsection 2.4).
With respect to the second question, we show that, given a fixed upper bound
K on the number of clusters, the optimal modularity clusterings of the discrete
random graphs converge in a distributional sense to an optimal clustering, satisying
a certain shape optimization problem (Theorem 2.3). This geometric continuum
optimization problem, of interest in itself, is a form of Kelvin’s problem: Informally,
find a partition of the domain, where each set has the same volume, but where
the perimeters between sets is minimized. Noting the first result above, it seems
natural that a constraint specifying equal volumes would emerge in the limiting
shape problem. Nonetheless, it seems intriguing that a form of Kelvin’s shape
optimization problem (cf. Subsection 2.2) would appear.
Previously, in the literature, a type of statistical consistency of modularity clustering for stochastic block models has been considered. In the stochastic block
model, each data point is assigned a group from K groups according to a probability π. Then, if the two points belong to groups a and b respectively, one puts an
edge between them with probability Fa,b . Modularity clustering now gives an empirical group assignment to each data point. One of the main results shown is that
the proportion of misclassification of empirical group assignments, with respect to
the a priori assignment, vanishes in probability, Bickel and Chen [12] for the model
above, Zhao, Levina and Zhu [81] for degree-corrected models, Rohe, Chatterjee
and Yu [69] for high-dimensional models, and Le, Levina and Vershynin [52] via
low rank approximation.
In this context, the main focus of the article is to understand the geometry of
optimal partitions, and other asymptotics with respect to the modularity functional. Our results represent limit results on a ‘geometric’ form of consistency of

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS

3

the discrete modularity clusterings, which seem not to have been considered before.
Moreover, as a corollary of this type of consistency, we show that the proportion
of misclassification of the data points into sets given by the modularity functional,
with respect to the limit optimization problem, vanishes a.s. (Corollary 2.4).
We use the recent framework of optimal transport introduced by Garcı́a Trillos
and Slepčev in [37], in the context of continuum limits of graph variational problems,
to help relate point cloud empirical measures to absolutely continuous ones. We
rewrite, after some manipulation, the modularity functional in terms of a ‘graph
total variation’ term and a ‘balance’ term (Section 4). The proofs, with respect
to the first question on asymptotics of the modularity functional of a particular
clustering, make use of concentration estimates for these terms through U-statistics
bounds.
On the other hand, with respect to the second question, we observe that maximizers of the modularity functional are the same as minimizers of an energy functional
built as the sum of the ‘graph total variation’ and ‘balance’ terms (cf. Subsection
6.1). In this energy functional, the coefficient in front of the ‘balance’ term diverges
as the reciprocal of the length scale when the number of data points grows. In the
limit, the soft penalty ‘balance’ term becomes a hard constraint. We show convergence of a subsequence of minimizers to an optimizer of the limit problem by use a
modified notion of Gamma convergence that we formulate (cf. Subsection 3.2), together with a compactness principle. For the ‘liminf’ part of Gamma convergence,
although we have to treat the balance constraint, the analysis of the graph total
variation term follows from work in [37], which handles a similar expression.
However, dealing with the ‘balance’ constraint represents a serious difficulty with
respect to the ‘limsup’ or ‘recovery sequence’ part of the Gamma convergence setup.
Without the constraint, one can form the recovery sequence by approximating
with piecewise smooth partitions. However, such approximations become more
complicated when also enforcing the ‘balance’ constraint. But, the probabilistic
result for the first question (Theorem 2.1), given for general measurable clusterings,
already can be seen to yield a recovery sequence, with respect to the modified notion
of Gamma convergence for random functionals. Interestingly, this notion of Gamma
convergence has the same strength, in terms of yielding subsequential convergence,
as the more usual stringent formulation (cf. Remark 3.10). Perhaps of use in
other problems, we observe that this more probabilistic approach offers a diferent
perspective.
With respect to previous work on statistical clustering methods, consistency of
K-means methods have been considered by Pollard in [63], and more recently, via
Gamma convergence, by Thorpe, Theil, Johansen, and Cade in [74]. On single
linkage hierarchical clustering, consistency has been shown by Hartigan in [48]. On
Fuzzy C-Means clustering, consistency has been considered by Sabin in [70]. With
respect to spectral clustering, consistency has been considered by Belkin and Niyogi
in [10], Von Luxburg, Belkin and Bousquet in [79], and Garcı́a Trillos and Slepčev
in [38], the last article, employing the framework of [37], as in this paper. We
also mention, using Gamma convergence (or ‘epi-convergence’) techniques, consistency of maximum likelihood and other estimators was studied by Wets in [80] and
references therein.
Also, related, Arias-Castro and Pelletier [7] considered the consistency of the
dimension reduction algorithm ‘maximum variance unfolding’, and Arias-Castro,

4

ERIK DAVIS AND SUNDER SETHURAMAN

Pelletier and Pudlo [8] and Garcı́a Trillos, Slepčev, von Brecht, Laurent and Bresson
[39] studied the consistency of Cheeger and ratio cuts. Pointwise estimates between
graph Laplacians and their continuum counterparts were considered by Belkin and
Niyogi [9], Coifman and Lafon [21], Giné and Koltchinskii [40], Hein, Audibert
and Von Luxburg [49], and Singer [72]. In addition, spectral convergence in more
general contexts was considered by Ting, Huang and Jordan [75] and Singer and
Wu [73].
In addition, we mention there is a large literature on Gamma convergence of
discrete lattice based variational expressions to continuum optimization problems
(cf. Braides [15], Braides and Gelli [16] and references therein). More recently,
see van Gennip and Bertozzi [42] which studies Gamma convergence of GinzburgLandau graph based functionals to continuum limits.
The plan of the paper is the following. In Section 2, we define the random
geometric graph model and state and discuss the two main results (Theorems 2.1
and 2.3) on modularity clustering. In Section 3, we discuss preliminaries with
respect to optimal transport distances and Gamma convergence–we remark that
the proof of Theorem 2.3 relies on this section, but the proof of Theorem 2.1 does
not. In Section 4, we develop the modularity functional into a convenient form
amenable to later analysis. In Section 5 and 6, the proofs of the two main theorems
are given respectively. Finally, in Section 7, some technical calculations and proofs,
referenced in previous sections, are collected.
2. Model and Results
We first introduce in Subsection 2.1 the modularity functional on graphs with
weighted edges. In Subsection 2.2, we discuss a form of Kelvin’s continuum shape
optimization problem. In Subsection 2.3, we state our main theorems, and make
some remarks in Subsection 2.4.
2.1. Graph Partitioning by Modularity Maximization. Let G = (X, W ) be a
weighted graph with vertex set X := {x1 , x2 , . . . , xn } and weight matrix W , where
the entry Wij ≥ 0 denotes the weight ofPthe (undirected) edge between vertex xi
and xj . The degree of vertex xi is di := j Wij , and the total weight of the graph
P
P
is m := 21 i di = 12 i,j Wij . When convenient, we will refer to the vertex xi
simply as ’vertex i’.
Let U = {Uk }K
k=1 be a partition of the vertex set X. We shall sometimes refer
to the nontrivial sets Uk of U as ‘clusters’, and we denote by |U| the number of
clusters. We may have |U|< K, if one of the sets Uk is empty. The partition U is
therefore equivalent to an assignment {ci }ni=1 of labels ci ∈ {1, . . . , K} to vertices,
where Uk = {xi : ci = k} for 1 ≤ k ≤ K.
Modularity was originally introduced as a quantitative measure of the bias towards of vertices in a given cluster to be connected to other vertices in the same
cluster [60]. Informally, the idea is to measure the proportion of edge weight that
runs between vertices in the same cluster, and compare it to the expected proportion if the edge weight was redistributed at random, according to a ‘null’ or ‘ground
truth’ model.
The total proportion of edge weight between vertices in the same cluster is
1 X
Wij δ(ci , cj ),
2m i,j

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS

5

where δ(ci , cj ) is the indicator that ci = cj , and the factor of 1/2 arises because
distinct vertex pairs appear twice in the sum.
Let Eij denote the expected edge weight between vertex i and vertex j under a
random redistribution model, which we specify below in different forms. Then, the
expected proportion of edge weight between vertices in the same cluster is
1 X
Eij δ(ci , cj ).
2m i,j
Then the modularity Q is defined to be

1 X
Q(U) =
Wij − Eij δ(ci , cj ),
2m i,j
and one has −1 ≤ Q ≤ 1. The guiding thought is that a partition U with large
modularity Q(U) would represent a good clustering of the graph.
The most popular choice of null model, and the one originally introduced in [60],
di dj
specifies Eij = 2m
. For unweighted graphs, where W is the adjacency matrix, this
choice corresponds to the configuration model. Namely, with respect to the vertex
degrees d1 , . . . , dn , consider the following distribution over graphs with n vertices
and m edges. At each vertex i place di half-edges. Then, successively choose a pair
of half-edges at random without replacement and connect them to form an edge
with unit weight. Then, to dominant order, the expected number of edges between
di dj
vertex i and vertex j behaves as 2m
.
Another natural choice corresponds to the Erdős-Rényi model, when Eij = 2m
n2 .
Namely, for unweighted graphs, when W again is the adjacency matrix, if the
endpoints of each edge is chosen uniformly from the vertex set, with m edges total,
the expected number of edges between vertex i and vertex j is Eij = 2m
n2 to dominant
order.
More generally, we may define Eij which interpolates in and among these two
α
Pn
dα
i dj
possibilities. For α ∈ R, let S = i=1 dα
i , and Eij = 2m S 2 . Define the ‘α’modularity Q to be
α
dα
1 X
i dj
Q(U) :=
Wij − 2m 2 δ(ci , cj ).
(2.1)
2m i,j
S
When α = 0 or 1, this reduces to the modularity corresponding to the Erdős-Rényi
model or the configuration model respectively.
The modularity maximization problem is the following: Given a graph G, find
the partition for which the modularity Q is maximized. In other words one solves
the following optimization problem,
maximize
U

Q(U),

(2.2)

where the maximization occurs over all partitions U of the vertex set. One is
particularly interested in optimal partitions U ∗ ∈ arg maxU Q(U), representing a
division of the graph into natural communities.
We also consider the following variant of problem (2.2), in which we restrict the
partitions to have at most K classes:
maximize
U

Q(U),

subject to |U|≤ K.

(2.3)

6

ERIK DAVIS AND SUNDER SETHURAMAN

We remark that finding a global maximum of the modularity is known to be
NP-hard ([18]). Nonetheless, there are various algorithms to compute approximate
maximizers, among them greedy algorithms (cf. [20], [13]), and relaxation methods
(cf. [58], [59], [50]). There is also a Potts model interpretation of modularity which
offers another computational perspective (cf. [68], [45]).
2.2. Geometric Partitioning. We now discuss a continuum partitioning problem, which will emerge as a scaled limit of the discrete graph partitioning optimization. Consider a domain D ⊂ Rd , and a partition U = {Uk }K
k=1 of D. For what
follows, we take K ≥ 1 to be fixed.
Suppose that we have a probability measure µ on D. We say that a partition U
is balanced with respect to the measure µ if each Uk has equal µ-measure, that is
1
k = 1, . . . , K.
µ(Uk ) =
K
Because U is a partition, any two distinct sets Uk and Ul are disjoint. However, if
they are adjacent their boundaries will intersect nontrivially as a d − 1 dimensional
surface. When the boundaries of {Uk }K
k=1 are piecewise-smooth, we may measure
the size of the interface between Uk and Ul , with respect to a density φ on D, by
Z
φ(x)dH(d−1) (x),
∂Uk ∩∂Ul ∩D
(d−1)

where dH
denotes the Euclidean (d − 1)-dimensional surface measure. The
measure of the total interface or perimeter between the sets of U is therefore
Z
1 X
φ(x)dH(d−1) (x),
(2.4)
2
∂Uk ∩∂Ul ∩D
1≤k6=l≤K

noting the factor 1/2 accounts for the fact that each distinct pair k, l contributes
twice to the sum.
Because ∂Uk ∩ D = ∪l6=k ∂Uk ∩ ∂Ul ∩ D, the quantity (2.4) is equal to
Z
1 X
φ(x)dH(d−1) (x).
(2.5)
2
∂Uk ∩D
1≤k≤K

More generally, for partitions U consisting of measurable sets {Uk }K
k=1 , we may
define the weighted perimeter of Uk as follows:
Per(Uk ; φ) := T V (1Uk ; φ),
where T V (1Uk ; φ), defined below, is the weighted total variation of the indicator
function 1Uk . For sufficiently regular sets, this definition agrees with the informal
notion of perimeter (2.5).
Let L∞ (D, θ) and Lp (D, θ) be Rthe usual spaces of functions u where inf{C :
|u(x)|≤ C for θ − a.e. x} < ∞ and D |u(x)|p dθ(x) < ∞ for 1 ≤ p < ∞ respectively.
When θ is Lebesgue measure on D and the underlying domain D is understood, we
will abbreviate Lp := Lp (D, θ). The weighted total variation of a function u ∈ L1
is given by
Z
T V (u; φ) :=

sup
Φ∈Cc1 (D;Rd )
|Φ(x)|≤φ(x)

u(x)div Φ(x) dx,
D

where Cc1 (D; Rd ) is the space of continuously differentiable, compactly supported
Pd
i
vector fields on D, and div Φ(x) = i=1 ∂Φ
∂xi . In our later applications, the density

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS

7

φ will be bounded above and below on D by positive constants. In this case, the
weighted total variation has many of the same properties as the total variation with
respect to the uniform density 1D , discussed in detail in Chapter 3 of [5].
Consider now the following geometric partitioning problem. Among all balanced
K-partitions of D, choose that which minimizes the total perimeter of its sets:
K

minimize
U

1X
Per(Uk ; φ)
2

(2.6)

k=1

1
subject to µ(Uk ) = ,
K

k = 1, . . . , K.

See Figure 1 for the behavior when D is a square.

(a) K = 4

(b) K = 9.

(c) K = 100.

Figure 1. Local minimizers of Problem 2.6 on D = (0, 1)2 , with
φ = 1, dµ = dx, produced using [17].

It is clear, by dividing D in terms of a moving hyperplane, that balanced Kpartitions with finite perimeter exist. Also, depending on D, the problem may or
may not have a unique solution (modulo relabeling of sets): Suppose φ = 1 and
dµ = dx. When D is a long, thin rectangle in R2 , there is only one perimeter
minimizing division into two sets of equal area. However, when D is a disc in R2 ,
there are infinitely many such divisions, given by cuts of the disc along a diameter.
The general problem (2.6) can be seen as a type of ‘soap bubble’ problem. It
can also be seen as a bounded domain form of Kelvin’s problem: Find a tiling
of Rd where each tile has unit µ-volume so that the φ-perimeter between tiles is
minimized. We note in passing, when φ = 1 and dµ = dx, in d = 2, this problem
has been solved in terms of hexagonal tiles, and is the subject of much research in
d ≥ 3. See Morgan [56], which discusses these and other related optimizations.
We remark, when φ = 1 and dµ = dx, the problem (2.6) has been considered
in the literature. Cañete and Ritore [19] have studied minimal partitions of the
disc into three regions, and in this context proved that the regions are bounded
by circular arcs making perpendicular contact with the boundary of the disc and
meeting at a 120 degree triple point within. Some conjectures about minimizers
for larger values of K and other domains are presented in Cox and Flikkema [22].
Oudet [61] derives a numerical algorithm, via Gamma convergence, for computing
approximate solutions.

8

ERIK DAVIS AND SUNDER SETHURAMAN

2.3. Results. Before stating the two main theorems, we first define the random
geometric graphs under consideration. We make the following standing assumptions
throughout on the domain D ⊂ Rd , ground measure ν on D, and underlying edge
weight structure.
(D) D is a bounded, open, connected subset of Rd with Lipschitz boundary.
(M) In d ≥ 1, ν is a probability measure on D with distribution function Fν
and density ρ such that ρ is Lipschitz and bounded above and below by
positive constants.
Further, in d = 1, ρ satisfies additional conditions: (a) ρ is differentiable
on D := (c, d) and (b) ρ is increasing in some interval with left endpoint c
and decreasing in some interval with right endpoint d.
Let {Xi }i∈N be a collection of i.i.d. samples from ν, and define Xn = {Xi }ni=1 .
We will denote by P and E the probability and expectation with respect to the
underlying probability space.
The random geometric graph is constructed from the points Xn through a kernel
function η : Rd → R, where η satisfies:
R
(K1) Rd η(x) dx = 1.
(K2) η is radial and non-increasing, i.e. η(z) ≤ η(z0 ) if kzk≥ kz0 k.
(K3) η(0) > 0 and η is continuous at 0.
(K4) η is compactly supported.
There is a large class of kernels admitted under assumptions (K1)−(K4), including
the kernel associated with the well-known random geometric graph, where η is the
indicator function of a ball.
Between vertex Xi and Xj , in terms of a parameter n , we attach an edge with
weight


(
Xi −Xj
1
η
=: ηn (Xi − Xj ) if i 6= j,
d
n
(2.7)
Wij = n
0
otherwise.
The parameter n serves as a length scale. For example, if the support of η is
contained in a ball of radius one, then two vertices Xi and Xj are connected by an
edge only if they are separated by a distance no more than n (cf. Figure 2). Since
the modularity functional Q is the same under weights W and cW , for c > 0, the
normalization factor −d
n in (2.7) was chosen so that the expected value of Wij is
of order 1.
Under all circumstances, we have n → 0, although the specific rate at which n
vanishes will depend on the dimension d, as well as the parameter α. There are in
fact two different sets of assumptions, (I1) being more restrictive than (I2), corresponding to the two main results given below. We first mention typical examples,
satisfying the assumptions.
Taking n = n−β , condition (I1) will hold if

2/(d + 1) if α = 0, 1
β<
1/(d + 1) if α 6= 0, 1.
However, condition (I2) would be satisfied if
(
min(1/d, 1/2), if α = 0, 1
β<
1/d + 1,
if α 6= 0, 1.
More precisely, (I1) and (I2) are the following:

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS

9

Figure 2. Random geometric graph, constructed from n = 200
uniformly distributed points on the strip D = (0, 4) × (0, 1) with
connectivity function η = 1|x|<1 and  = n−0.3 .
(I1) The sequence {n }n∈N is such that n > 0 and n → 0. When α = 0 or
α = 1, we also suppose that
∞
X

exp(−n(d+1)/2
) < ∞.
n

n=1

However, when α 6= 0, 1, we suppose that
∞
X

n exp(−nd+1
n ) < ∞.

n=1

(I2) The sequence {n }n∈N is such that n > 0 and n → 0. When α = 0 or
α = 1, we also suppose that
√
2 log log n 1
√
lim
= 0,
if d = 1
n→∞
n
n
(log n)3/4 1
=0
n→∞
n1/2 n
(log n)1/d 1
=0
lim
n→∞
n1/d n
lim

if d = 2
if d ≥ 3.

However, when α 6= 0, 1, we suppose that
∞
X

n exp(−nd+1
n ) < ∞.

n=1

In Subsection 2.4 we discuss the motivation behind these assumptions in more
detail.
Now, given the set Xn and a sequence {n }n∈N , denote by Wn the weight matrix with entries given by (2.7), and denote by Gn = (Xn , Wn ) the corresponding
weighted random geometric graph. We let
Qn denote the modularity functional (2.1) corresponding to Gn .

10

ERIK DAVIS AND SUNDER SETHURAMAN

Consider a partition U = {Uk }K
k=1 of the domain D. For any n ≥ 1, this induces
a partition Un = {Un,k }K
of
the
sample Xn , where
k=1
Un,k = Uk ∩ Xn ,
for 1 ≤ k ≤ K.
Theorem 2.1 (Asymptotics). Suppose {n }n∈N satisfies condition (I1). Fix K ≥
1 and let U = {Uk }K
k=1 be a partition of D where each Uk is a subset of finite
perimeter, Per(Uk ; ρ2 ) < ∞. Let Un be the induced partition of Xn for n ≥ 1.
Then, the modularity Qn (Un ) satisfies
K 
2
X
a.s.
1 − 1/K − Qn (Un ) −−→
µ(Uk ) − 1/K ,
(2.8)
k=1
1+α
(x) dx
Rρ
.
ρ1+α (x) dx
D
2

as n → ∞, where dµ(x) =
PK
Further, if k=1 (µ(Uk ) − 1/K) = 0, we have
K

X
1 − 1/K − Qn (Un ) a.s.
−−→ Cη,ρ
Per(Uk ; ρ2 ),
n

(2.9)

k=1

as n → ∞, where
R

η(x)|x1 | dx
,
2 D ρ2 (x) dx
and x1 denotes the first coordinate of x.
Cη,ρ =

Rn
R

One way to interpret these law of large numbers limits is that the nonnegative
quantity, a ‘balance’ term,
K 
X
1 2
µ(Uk ) −
,
K
k=1

is a measure of how balanced the partition U is with respect to the measure µ. In
our model, the limiting modularity of a partition is predominantly determined by
the number of clusters and the extent to which they are balanced.
We state a corollary of Theorem 2.1, which follows by considering balanced
partitions where K is not restricted.
Corollary 2.2. Suppose the assumptions of Theorem 2.1 are satisfied. Let Q∗n =
maxUn Qn (Un ) denote the maximum modularity associated to Gn , where the maximum is over all partitions Un of Xn . Then, we have
a.s.

Q∗n −−→ 1,
as n → ∞.
Our second main result is a characterization of the behavior of optimal clusterings
Un∗ ∈ arg max|Un |≤K Qn (Un ), as n → ∞. To this end, we introduce a suitable notion
of convergence.
To a sequence of sets P
{Un }n∈N with Un ⊂ Xn , we associate the ‘graph measures’
n
{γn }n∈N , where γn = n1 i=1 υ(Xi ,1Un (Xi )) , and υ· denotes a point mass. In words,
the measure γn is the distribution of the graph of 1Un under the empirical measure
νn on Xn . Let also U ⊂ D and define γ as the distribution of the graph of 1U under
ν. We will write, with respect to a realization of {Xi }i∈N , that
w

w

Un converges weakly (denoted −
→) to U if γn −
→ γ.

(2.10)

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 11

Correspondingly, consider a sequence of partitions Un = {Un,k }K
k=1 of Xn , and
a partition U = {Uk }K
of
D.
Since
the
sets
in
the
collections
Un and U are
k=1
unordered, we say that
w

Un converges weakly (denoted −
→) to U
if there exists a sequence {πn }n∈N of permutations πn : {1, . . . , K} → {1, . . . , K}
such that
w
γn,πn k −
→ γk ,
for k = 1, . . . , K.
(2.11)
Theorem 2.3 (Optimal Clusterings). Suppose {n }n∈N satisfies condition (I2).
Let Un∗ ∈ arg max|Un |≤K Qn (Un ) be an optimal partition of Xn , for n ≥ 1. Let also,
R
with respect to problem (2.6), φ = ρ2 and dµ = ρ1+α dx/ D ρ1+α (x)dx.
If U ∗ is the unique solution (modulo reordering of its constituent sets) of problem
(2.6), then a.s. Un∗ converges weakly to U ∗ , in the sense of (2.11).
If there is more than one solution to the problem (2.6), then a.s. Un∗ converges
weakly along a subsequence, in the sense of (2.11), to a solution U ∗ of (2.6).
Figure 3 illustrates this result. We remark that, in the proof of Theorem 2.3,
we will in fact show a stronger form of convergence, in terms of Wasserstein,
Kantorovich-Rubenstein type (T L1 )K distances, via a Gamma convergence statement (Theorem 6.1) for certain energy functionals.

Figure 3. Binary partitions produced by modularity clustering of
random geometric graphs with various values of n on the domain
D = (0, 1) × (0, 4), using the algorithm of [58]. Here α = 1, the
density ρ is uniform, η = 1|x|<1 , and n = n−0.3 . The red lines indicate the optimal cut associated with the continuum partitioning
problem for K = 2.

12

ERIK DAVIS AND SUNDER SETHURAMAN

We also note that the parameter α, which parametrizes a family of null models
in the modularity functional (2.1), appears in the balancing measure µ with respect
to the continuum problem. As α increases, the measure µ puts more mass near the
modes of the density ρ, of course altering the optimal clusterings, as illustrated in
Figure 4.

(a) Level sets of ρ

(b) α = −1

(c) α = 0

(d) α = 1

Figure 4. Behavior of Problem (2.6) for K = 2 and various α
on D = (0, 1) × (0, 3), computed using a modified Rversion of the
algorithm in [61]. Here φ = ρ2 , dµ = ρ1+α (x) dx/ D ρ1+α (x) dx,
for ρ(x) ∝ min(2 exp(−4||x − z||2 ), 1/2), with z = (1/2, 2).
We also observe that Theorem 2.3 implies that the proportion of misclassified
points vanishes almost surely.
Corollary 2.4. Consider the setting of Theorem 2.3. Let {Un∗m }m∈N be a subsequence of optimal Qnm -modularity partitions of the sample space which a.s. converges weakly, in the sense of (2.11), to a solution U ∗ of (2.6). Then, the proportion
of correctly classified points converges to 1. That is, a.s. as m → ∞,
pnm := max

1≤k≤K

|{x ∈ Xnm : x ∈ Uk∗ ∩ Un∗m ,πn
|{x ∈ Xnm : x ∈

m (k)

Uk∗ }|

}|

→ 1.

Proof. It is enough to show, with respect to a sequence of sets Vm ⊂ Xnm and a set
w
V ⊂ D where a.s. Vm −
→ V , in the sense of (2.10), that
|{x ∈ Xnm : x ∈ V ∩ Vm }|
→1
|{x ∈ Xnm : x ∈ V }|

a.s.

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 13

as m → ∞. Then, the statement in the corollary would follow by application of
this limit with Vm = Un∗m ,πn (k) and V = Uk∗ for 1 ≤ k ≤ K.
m
In terms of the measures γm and γ, which govern the graphs of 1Vm and 1V
under νn and ν respectively, we can write
R
1V (x)y dγm (x, y)
|{x ∈ Xnm : x ∈ V ∩ Vm }|
= RD×R
.
|{x ∈ Xnm : x ∈ V }|
1 (x) dγm (x, y)
D×R V
w

Since a.s. γm −
→ γ as m → ∞, by approximating (x, y) 7→ 1V (x)y and (x, y) 7→
1V (x) by bounded, continuous functions, we have
R
R
1 (x)y dγm (x, y) a.s. D×R 1V (x)y dγ(x, y)
D×R V
R
−−→ R
= 1,
1 (x) dγm (x, y)
1 (x) dγ(x, y)
D×R V
D×R V
as m → ∞, concluding the argument.



2.4. Discussion.
1. As alluded to in the introduction, the phenomena shown in Corollary 2.2
for random geometric graphs has been considered before in other models. Indeed,
in [45] the authors provide heuristic arguments for the limiting behavior Q∗n → 1
under two regimes: i) when the graphs are regular lattices, and ii) when the graphs
are Erdős-Rényi graphs with edge probability p = 2/n. In [43], the authors derive
the limiting behavior Q∗n → 1 under a sparse graph model, in which modules of
some characteristic size are adjoined to the graph. Further, these asymptotics are
consistent with the empirical results associated with large real-world graphs [13].
2. It has been observed in the literature that modularity optimization may fail
to identify clusters smaller than a certain level, depending on the total size and
interconnectedness of the graph. In other words, modularity possesses a ‘resolution
limit’ in terms of its clustering (cf. [32], [43]). An extreme example is when the
graph contains a pair of cliques (complete subgraphs) connected by a single edge,
but modularity would lump them into a common cluster (cf. Figure 3 of [32]).
In [68], the authors consider a variant of the modularity given by
di dj 
1 X
Qλ =
Wij − λ
δ(ci , cj )
(2.12)
2m i,j
2m
where λ is a parameter. In [51], the parameter λ is related to the resolution limit
phenomena: Namely, higher values of λ allow for smaller cluster sizes.
The methods used to prove Theorem 2.3 give the following asymptotic behavior
of optimal Qλ modularity clusterings: When λ = λn := κβn is scaled with n,
for β ≥ 0 and n satisfying (I2), three distinct possibilities arise for the limiting
problem. When 0 ≤ β < 1, the continuum partitioning problem remains as it is
in (2.6). When β = 1, the hard constraints µ(Uk ) = 1/K for 1 ≤ k ≤ K of the
limiting problem get replaced by a soft balancing condition, resulting in
minimize
U

K

K

k=1

k=1

X
1X
Per(Uk ; φ) + κ
(µ(Uk ) − 1/K)2 .
2

(2.13)

When β > 1, the continuum problem degenerates to a perimeter minimization
problem with no balancing condition, which has as its solution a single global
cluster D (and the other K − 1 sets being empty).

14

ERIK DAVIS AND SUNDER SETHURAMAN

3. One can ask about the reasons behind the assumptions (I1) and (I2). With
respect to Theorem 2.1, a lower bound for n should be informed by the fluctuations
of the functional. In fact, the variance of Qn (Un ) can be seen to be of order
−1
(n2 d+1
when α = 0, 1 (by a computation with formula (4.7)), so that condition
n )
(I1) makes sense. However, when α 6= 0, 1, a worse bound is useful to control the
nonlinearity of the functional.
On the other hand, assumption (I2) in Theorem 2.3 is informed by the connectivity radius of the random geometric graphs. For instance, if n were to vanish too
quickly, the underlying graphs would contain O(n) disconnected components (cf.
Theorem 13.25 in [62]). Then, presumably, one would be able to find a Un∗ such
a.s.
that (1/2 − Qn (Un∗ ))/n −−→ 0 and consequently obtain a continuum cluster point
∗
U . This would be a contradiction, as the resulting partition U ∗ would have zero
perimeter – in other words, one of the sets in U ∗ would be D itself – and so could
not satisfy the balance conditions. This is a version of the argument in Remark 1.6
of [37].
The threshhold that n should be larger than for the graphs to be connected is
known: In d ≥ 1, it is of order (log(n))1/d /n1/d (cf. [62]). Viewed from this lens,
when α = 0, 1, condition (I2) is more optimal than when α 6= 0, 1, again due to the
nonlinearity of the functional in this case.
4. We briefly discuss the assumptions on ρ, D, and η. The proof of Theorem
2.3 makes use of certain ‘transport maps’ (cf. Proposition 3.2). For d ≥ 2, we use
the optimal transport results of [36], which require that ρ be bounded above and
below by positive constants. Likewise, the assumptions on D are made there so
that comparisons to results on cubes may be made. On the other hand, for d = 1, it
is not necessary that ρ be bounded below to define a suitable transport map–here,
the technical condition required is (7.6). However, in all dimensions, we require
a lower bound on ρ, as this enables us to handle the general α 6= 0, 1 case via a
Lipschitz inequality for the map x 7→ xα (cf. Lemma 5.6). The boundedness of D
is also used in several intermediate technical results. The Lipschitz continuity of
ρ is used for handling the ‘balance’ term in the proof of Theorem 2.3 (principally
in Lemma 5.3, by way of Lemma 7.1). We remark that this condition could be
weakened to Hölder continuity, with exponent greater than 1/2.
With respect to η, the radial and monotone assumptions are convenient in relating certain graph functionals to their nonlocal analogues (cf. Lemma 6.3). The
continuity at zero is used in the proof of the compactness property, Lemma 6.11.
Finally, we remark that the compact support of η allows to analyze behavior near
the boundary of D, although this assumption could be weakened to a suitable
condition on the decay of η at infinity.
3. Preliminaries
Before entering into the main derivations, we first discuss in Subsection 3.1 the
T L1 topology and framework, introduced by Garcı́a Trillos and Slepčev in [37], and
connections to weak convergence of graph measures. Then, in Subsection 3.2, we
define a variant of Gamma convergence for random energy functionals that we will
use to prove Theorem 2.3.
3.1. T L1 topology and framework. Given a measurable space S ⊂ Rd , we let
B(S) denote the Borel σ-algebra on S, and similarly let P(S) denote the set of Borel

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 15

probability measures on S. Also, given two spaces, S1 and S2 , a measurable map
T : S1 → S2 , and a measure µ ∈ P(S1 ), we define the push-foward T] µ ∈ P(S2 ) by
T] µ(A) = µ(T −1 (A)),

for A ∈ B(S2 ).

In particular, T] µ is the distribution of T X where X has distribution µ.
Given measures µ, θ ∈ P(S), recall that a coupling between µ and θ is a probability measure π on S × S such that the marginal with respect to the first variable
is µ, and the marginal with respect to the second variable is θ. Consider the set of
couplings
Γ(µ, θ) := {π ∈ P(S × S) : (∀U ∈ B(S) π(U × S) = µ(U ) and π(S × U ) = θ(U )}.
Define the distance on P(S) by
Z
d1,S (µ, θ) :=

|x − y| dπ(x, y).

inf
π∈Γ(µ,θ)

S

This is a metric on the subset of probability measures in P(S) with finite first
moment.
When S is complete, a case of a more general result (see Theorem 6.9 [78]) is
the following: Let {µn }n∈N and µ be measures in P(S). Then, as n → ∞,
w

µn −
→ µ if d1,S (µn , µ) → 0.

(3.1)

Now, as in [37], to understand weak convergence of ‘graph measures’, define the
space T L1 (S) by
T L1 (S) := {(µ, f ) : µ ∈ P(S), kf kL1 (S,µ) < ∞},
and, for (µ, f ) and (θ, g) in T L1 (S), define the distance
Z Z
dT L1 ,S ((µ, f ), (θ, g)) := inf
|x − y|+|f (x) − g(y)| dπ(x, y).
π∈Γ(µ,θ)

S×S

One may identify an element (µ, f ) ∈ T L1 (S) with a graph measure (Id×f )] µ ∈
P(S ×R), whose support is contained in the graph of f . Consider now, with respect
to (µ, f ), (θ, g) ∈ T L1 (S), the graph measures γ = (Id × f )] µ, γ
e = (Id × g)] θ ∈
P(S × R). It may be seen (cf. Proposition 3.3 of [37]) that
d1,S×R (γ, γ
e) = dT L1 ,S ((µ, f ), (θ, g)).

(3.2)

We now restrict S to be the bounded domain D ⊂ Rd introduced in Subsection
1
2.3. We will abbreviate T L1 := T L1 (D). Then, for (µ,
R f ) ∈ T L , the graph
measure γ = (Id × f )] µ has a finite first moment in that D |x|+|f (x)|dµ(x) < ∞.
Hence, by (3.2), T L1 can be viewed as a metric space with metric dT L1 ,D .
With respect to graph measures γ 0 and γ 00 on D × R, consider their extensions
0
γ̄ and γ̄ 00 to D × R by setting γ̄ 0 (∂D × R) = γ̄ 00 (∂D × R) = 0. Then, the distance
d1,D×R (γ̄ 0 , γ̄ 00 ) ≤ d1,D×R (γ 0 , γ 00 ).

(3.3)

1

TL

Suppose now (µn , fn ) −−→ (θ, g), and γn and γ are the associated graph measures
for n ≥ 1. Then, by (3.2) and (3.3), d1,D×R (γ̄n , γ̄) ≤ d1,D×R (γn , γ) → 0 as n → ∞.
w

w

In particular, as D × R is complete, by (3.1), γ̄n −
→ γ̄ in P(D × R), and so γn −
→γ
in P(D × R), as n → ∞.
We now make a remark on definition (2.11) in connection with the product space
(T L1 )K . Fix a realization {Xi }i∈N . Recall the empirical measures νn and probability measure ν on D from the beginning of Subsection 2.3. Let Un = {Un,k }K
k=1 be

16

ERIK DAVIS AND SUNDER SETHURAMAN

a partition of Xn for n ≥ 1, and U = {Uk }K
k=1 be a partition of D. We say the seK
K
quence (νn , Un ) := ((νn , 1Un,k ))k=1 converges in (T L1 )K to (ν, U) := ((ν, 1Uk ))k=1
T L1

if (νn , 1Un,k ) −−→ (ν, 1Uk ) for 1 ≤ k ≤ K. Hence, by the comment below (3.3), as
convergence in the metric dT L1 ,D implies weak convergence in P(D × R), we obtain
(T L1 )K

w

Un −
→ U if (νn , Un ) −−−−−→ (ν, U),

(3.4)

in the sense of definition (2.11), by choosing the identity permutations
We now discuss when this convergence may be formulated in terms of transportation maps. We say that a measurable function T : D → D is a transportation
map between the measures µ ∈ P(D) and θ ∈ P(D) if θ = T] µ. In this context, for
f ∈ L1 (θ), the change of variables formula holds
Z
Z
f (y) dθ(y) =
f (T (x)) dµ(x).
D

D

A transportation map T yields a coupling πT ∈ Γ(µ, θ) defined by πT :=
(Id × T )] µ where (Id × T )(x) = (x, T (x)). It is well known, when θ is absolutely
continuous with respect to Lebesgue measure on D, that the infimum d1,D (µ, θ) can
be achieved by a coupling πT induced by a transportation map T between µ and θ.
Indeed, we note briefly that this is only one result among many others which relate
various ‘Monge’ and ‘Kantorovich’ distances via optimal transport theory. See [78]
and references therein; see also [4], [77].
We will say that a sequence {Tn }n∈N of transportation maps, with Tn] θ = θn ,
with respect to a sequence of measures {θn }n∈N ⊂ P(D), is stagnating if
Z
lim
|x − Tn (x)| dθ(x) = 0.
n→∞

D

The following is Proposition 3.12 in [37].
Lemma 3.1. Consider a measure θ ∈ P(D) which is absolutely continuous with
respect to the Lebesgue measure. Let (θ, f ) ∈ T L1 (D) and let {(θn , fn )}n∈N be a
sequence in T L1 (D). The following statements are equivalent:
T L1

(i) (θn , fn ) −−→ (θ, f ).
w
(ii) θn −
→ θ and there exists a stagnating sequence of transportation maps
Tn] θ = θn such that
Z
lim
|f (x) − fn (Tn (x))| dθ(x) = 0.
(3.5)
n→∞

D

w

(iii) θn −
→ θ and for any stagnating sequence of transportation maps Tn] θ = θn ,
the convergence (3.5) holds.
In order to make use of the above result on T L1 convergence, we will need to
find a suitable stagnating sequence {Tn }n∈N of transportation maps.
Proposition 3.2. Recall, from the beginning of Subsection 2.3, the assumptions
on the probability measure ν on D, and that νn denotes the empirical measure
corresponding to i.i.d. samples drawn from ν.
Then, there is a constant C > 0 such that, with respect to realizations of {Xi }i∈N
in a probability 1 set Ω0 , a sequence of transportation maps {Tn }n∈N exists where

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 17

Tn] ν = νn and
lim sup
n→∞

lim sup
n→∞

lim sup
n→∞

n1/2 kId − Tn kL∞
≤C
(2 log log n)1/2

if d = 1,

n1/d kId − Tn kL∞
≤C
(log n)3/4

if d = 2,

n1/d kId − Tn kL∞
≤C
(log n)1/d

if d ≥ 3.

Proof. We prove the d = 1 case in the appendix (Proposition 7.6), as a consequence
of quantile transform results for the empirical measure, making use of the technical
conditions assumed on ρ. In Garcı́a Trillos and Slepčev [36], the d = 2 and d ≥ 3
cases are first discussed, in the context of concentration estimates in the literature
when D is a cube and ν is the uniform measure, and then proved for general D and
nonuniform ν.

Although a result of Varadarajan (cf. Theorem 11.4.1 in [28]) implies that a.s.
w
νn −
→ ν, Proposition 3.2 gives a way to specify the probability 1 set on which the
weak convergence holds.
Corollary 3.3. On the probability 1 set Ω0 of Proposition 3.2, the empirical measures νn converge weakly to ν as n → ∞.
Proof. Let f : D → R be a bounded, Lipschitz continuous function. Since
Z
n
1X
f (Xi ) =
f (Tn x) dν(x),
n i=1
D
we may write
n

1X
f (Xi ) −
n i=1

Z

Z
f (x) dν(x) ≤

D

|f (Tn x) − f (x)| dν(x)
D

Z
≤C

|x − Tn x| dν(x)
D

≤ C||Id − Tn ||L∞ ,
where C is a Lipschitz constant
Pn for f . By RProposition 3.2, for each realization
of {Xi }i∈N in Ω0 , we have n1 i=1 f (Xi ) → D f (x) dν(x) as n → ∞. Hence, by
the Portmanteau theorem (Theorem 3.9.1 in [29]), we have the weak convergence
w
νn −
→ ν as n → ∞.

3.2. On Gamma convergence of random functionals. Here, we introduce
a type of Γ-convergence, with respect to random functionals, which will be an
important tool in the proof of Theorem 2.3 in Section 6, and may be of interest in
its own right. For what follows, let X denote a metric space with metric d and let
Fn : X → [0, ∞] be functionals on this space.
We first state the definition with respect to deterministic functionals.
Definition 3.4. The sequence {Fn }n∈N Γ-converges with respect to the topology on
X if the following conditions hold:

18

ERIK DAVIS AND SUNDER SETHURAMAN

(1) Liminf inequality: For every x ∈ X and every sequence {xn }n∈N converging to x,
F (x) ≤ lim inf Fn (xn ),
n→∞

(2) Limsup inequality: For every x ∈ X, there exists a sequence {xn }n∈N
converging to x satisfying
lim sup Fn (xn ) ≤ F (x).
n→∞
Γ

The function F is called the Γ-limit of {Fn }n∈N , and we write Fn −
→ F.
When we wish to make the dependence on the metric d explicit, we say that
{Fn }n∈N Γ(d)-converges to F , or F is the Γ(d)-limit of {Fn }n∈N , etc.
Remark 3.5. If the liminf inequality holds, the limsup inequality is equivalent to
the following condition: For every x ∈ X, there exists a sequence {xn }n∈N with
xn → x and limn→∞ Fn (xn ) = F (x). The sequence {xn }n∈N is referred to as a
recovery sequence for x.
A basic consequence of Definition 3.4 is the following (cf. [15], Theorem 1.21).
Theorem 3.6. Let Fn : X → [0, ∞] be a sequence of functionals Γ-converging to
F . Suppose {xn }n∈N is a relatively compact sequence in X with


lim Fn (xn ) − inf Fn (x) = 0.
(3.6)
n→∞

x∈X

Then,
(1) F attains its minimum value and
min F (x) = lim inf Fn (x).

x∈X

n→∞ x∈X

(2) The sequence {xn }n∈N has a cluster point, and every cluster point of the
sequence is a minimizer of F .
For this theorem to be applicable, it is standard to put some condition on
{Fn }n∈N so that (3.6) implies that the sequence {xn }n∈N is relatively compact
in X.
Definition 3.7. We say that the sequence of nonnegative functionals {Fn }n∈N has
the compactness property if for any sequence {xn }n∈N , the following two conditions,
(i) {xn }n∈N is bounded in X
(ii) The energies {Fn (xn )}n∈N are bounded,
imply that {xn }n∈N is relatively compact in X.
We now extend the above notions to the random setting. Here, we have a
probability space (Ω, F, P) and a sequence of functionals Fn : X × Ω → [0, ∞].
Definition 3.8. We say the (random) sequence {Fn }n∈N Γ-converges to the deterministic functional F : X → [0, ∞] if
(1) Liminf inequality With probability 1, the following statement holds: For
any x ∈ X and any sequence {xn }n∈N with xn → x,
F (x) ≤ lim inf Fn (xn ).
n→∞

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 19

(2) Recovery sequence For any x ∈ X, there exists a (random) sequence
a.s.
a.s
{xn }n∈N with xn −−→ x and Fn (xn ) −−→ F (x).
Definition 3.9. We say the (random) sequence {Fn }n∈N has the compactness property if with probability 1, the sequence {Fn (·, ω)}n∈N has the compactness property
in Definition 3.7.
Remark 3.10. The definition for Γ-convergence of random functionals, Definition 3.8, is weaker than the one in [37], which prescribes that Definition 3.4 holds
with probability 1. However, in our Definition 3.8, with respect to the recovery sequence, the probability 1 set may depend on the sequence, and therefore is an easier
condition to verify, say with probabilistic arguments. Interestingly, this weaker definition has the same strength in terms of its application in the following Gamma
convergence statement, Theorem 3.11, a main vehicle in the proof of Theorem 2.3.
In passing, we also note that the compactness criterion of random functionals,
Definition 3.9, can also be weakened, in that the probability 1 set may depend on
the particular bounded sequence in Definition 3.7, without altering the statement
of the Gamma convergence Theorem 3.11, and with virtually the same proof.
Theorem 3.11. Let Fn : X × Ω → [0, ∞] be a sequence of random functionals
Γ-converging to a limit F : X → [0, ∞], in the sense of Definition 3.8, which is
not identically equal to ∞. Suppose that {Fn }n∈N has the compactness property,
in the sense of Definition 3.9, and also the following condition holds: For ω in a
probability 1 set, there exists a bounded sequence, xn = xn (ω), whose bound may
depend on ω, such that


lim Fn (xn ) − inf Fn (x) = 0.
n→∞

x∈X

Then, with probability 1,
(1) F attains its minimum value and
min F (x) = lim inf Fn (x).
n→∞ x∈X

x∈X

(2) The sequence {xn }n∈N has a cluster point, and every cluster point of the
sequence is a minimizer of F .
Proof. Pick x̃ ∈ X, along with a recovery sequence {x̃n }k∈N , so that on a probability
1 set Ω1 we have limn→∞ x̃n = x̃ and limn→∞ Fn (x̃n ) = F (x̃). Let Ω2 be a probability 1 set on which xn = xn (ω) is a bounded sequence where limn→∞ (Fn (xn ) −
inf x∈X Fn (x)) = 0. Hence, on the probability 1 set Ω1 ∩ Ω2 , we obtain
lim sup Fn (xn ) ≤ F (x̃).

(3.7)

n→∞

Applying the argument for (3.7) with respect to a countable collection {x̃(m) }m∈N
with limm→∞ F (x̃(m) ) = inf x∈X F (x), we obtain on a probability 1 set Ω3 ⊂ Ω2
that
lim sup Fn (xn ) ≤ inf F (x).
(3.8)
n→∞

x∈X

Now, because F is not identically equal to ∞, the right hand side of the above
inequality is finite. Then, on the probability 1 set Ω3 , the sequences {xn }n∈N
and {Fn (xn )}n∈N are bounded. Let Ω4 be the probability 1 set on which the
compactness property for {Fn }n∈N holds. In particular, on Ω5 = Ω3 ∩ Ω4 , the
bounded sequence {xn }n∈N is relatively compact. With respect to the set Ω5 , let

20

ERIK DAVIS AND SUNDER SETHURAMAN

{xnk }k∈N be a subsequence converging to a cluster point x∗ , that is limk→∞ xnk =
x∗ .
Let Ω6 be a probability 1 set on which the liminf inequality holds. Then, on
Ω7 = Ω5 ∩ Ω6 , we have
inf F (x) ≤ F (x∗ ) ≤ lim inf Fnk (xnk ).

x∈X

(3.9)

k→∞

Combining (3.8) and (3.9) shows, since Ω7 ⊂ Ω3 , that on the set Ω7 we have
lim sup Fnk (xnk ) ≤ lim sup Fn (xn ) ≤ inf F (x) ≤ F (x∗ ) ≤ lim inf Fnk (xnk ).
x∈X

n→∞

k→∞

k→∞

(3.10)
Hence, we conclude that F attains its minimum value, F (x∗ ) = inf x∈X F (x) and
x∗ is a minimizer of F , proving part of the first statement. In fact, the second
statement also follows: With respect to the probability 1 set Ω7 , every cluster
point of {xn }n∈N is a minimizer of F .
We now show the remaining part of the first statement. With respect to the set
Ω7 , let {xmk }k∈N be a subsequence of {xn }n∈N where, for some cluster point x∗∗ ,
lim xmk = x∗∗ .

lim Fmk (xmk ) = lim inf Fn (xn ) and
n→∞

k→∞

k→∞

Then, by (3.10), we conclude on Ω7 that limn→∞ Fn (xn ) = inf x∈X F (x). Since
Ω7 ⊂ Ω2 , we have on Ω7 that limn→∞ (Fn (xn ) − inf x∈X Fn (x)) = 0. Hence, we
conclude on Ω7 that limn→∞ inf x∈X Fn (xn ) = inf x∈X F (x).


4. Reformulation of the modularity functional
In this section, we write the modularity functional as a sum of a ‘graph total
variation’ term and a ‘balance’ or ‘quadratic’ term, which will aid in its subsequent
analysis. A similar, but different decomposition was used in [50].
Recall the modularity functional in Subsection 2.3 acting on a partition Un =
{Un,k }K
k=1 of the data points Xn into K ≥ 1 sets:
Qn (Un ) =

α
dα
1 X
i dj
Wij − 2m 2 δ(ci , cj ).
2m i,j
S

(4.1)

P
P
P P
Here, di = j Wij , 2m = ij Wij , and S = i ( j Wij )α and the weights Wij =
ηn (Xi − Xj ) if i 6= j and equal 0 otherwise. The label ci = k is assigned to the
point Xi if Xi ∈ Un,k for 1 ≤ k ≤ K.
Define In (D) as the collection of indicator functions of subsets of Xn . Natural
members of In (D), in the above context, are un,k = 1Un,k for 1 ≤ k ≤ K. Note
PK
that the collection {un,k }K
k=1 satisfies
k=1 un,k = 1Xn .
Observe now that δ(ci , cj ), signifying that Xi and Xj have the same label, can
be expressed in two ways:
δ(ci , cj ) = 1 −

K

K

k=1

k=1

X
1X
|un,k (Xi ) − un,k (Xj )|=
un,k (Xi )un,k (Xj ).
2

(4.2)

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 21

Applying the first identity in (4.2) to the first term in (4.1) gives
K

1 X
1 X
1 1 XX
Wij δ(ci , cj ) =
Wij −
Wij |un,k (Xi ) − un,k (Xj )|
2m i,j
2m i,j
2 2m
i,j
k=1

K
1 1 XX
Wij |un,k (Xi ) − un,k (Xj )|.
=1−
2 2m
i,j
k=1

Define the graph total variation GT Vn (u), acting on u : Xn → R, to be
GT Vn (u) :=

1
1
n n(n − 1)

X

ηn (Xi − Xj )|u(Xi ) − u(Xj )|.

(4.3)

1≤i6=j≤n

Then, we may write
K

n(n − 1) X
1 X
Wij δ(ci , cj ) = 1 − n
GT Vn (un,k ).
2m i,j
4m

(4.4)

k=1

Similarly, the second relation in (4.2) gives
α
X dα
i dj
i,j

S2

δ(ci , cj ) =

K
1 XX α α
di dj un,k (Xi )un,k (Xj )
S2
i,j
k=1

=

K
2
1 XX α
di un,k (Xi )
2
S
i
k=1

=

K
α
2
1 XX X
η
(X
−
X
)
u
(X
)
.
n
i
j
n,k
i
S2
1≤j≤n
i
k=1

j6=i

Define GΛn (u), for u : D → R, by
GΛn (u) :=

n
α
X
1 X 1
ηn (Xi − Xj ) u(Xi ).
n i=1 n − 1 1≤j≤n
j6=i

Then,
α
X dα
i dj

S2

i,j

K
n2 (n − 1)2α X
2
δ(ci , cj ) =
(GΛn (un,k )) .
S2
k=1

α

Note that GΛn (1) = S/(n(n − 1) ). With a bit of algebra, we obtain
K 
X

2
GΛn (un,k )

k=1

=

K h
X

(GΛn (un,k − 1/K))2

k=1

i
+2GΛn (un,k − 1/K)GΛn (1/K) + (GΛn (1/K))2 ,

(4.5)

22

ERIK DAVIS AND SUNDER SETHURAMAN

which further equals
K
X

(GΛn (un,k − 1/K))2

k=1

+2GΛn

K
X


1
(un,k − 1/K) GΛn (1/K) + GΛn (1)2
K

k=1

=

K
X

(GΛn (un,k − 1/K))2 +

k=1

We have used the relation
Hence,
α
X dα
i dj
i,j

S2

PK

k=1

1
GΛn (1)2 .
K

un,k = 1Xn in the last equality.
K

δ(ci , cj ) =

i
n2 (n − 1)2α h X
2
(GΛ
(u
−
1/K))
+ 1/K.
n n,k
S2

(4.6)

k=1

Combining (4.4) and (4.6) gives
K

1 − 1/K − Qn (Un )

=

i
n2 (n − 1)2α h X
2
(GΛ
(u
−
1/K))
n
n,k
S2

(4.7)

k=1

K

n(n − 1) X
+n
GT Vn (un,k ).
4m
k=1

5. Proof of Theorem 2.1: Asymptotic Formula
We analyze the ‘graph total variation’ and ‘quadratic’ terms, identified in the
decomposition of the modularity functional in Section 4, in the first two subsections.
Then, in Subsection 5.3, we collect estimates and prove Theorem 2.1.
In this section, in accordance with the assumptions of Theorem 2.1, we suppose
that the partition Un = {Un,k }K
k=1 of the data points Xn is induced by a ‘continuum’
partition U = {Uk }K
of
D
into
K ≥ 1 sets with finite perimeter Per(Uk ; ρ2 ) < ∞,
k=1
where Un,k = {Xi ∈ Xn |Xi ∈ Uk }, for 1 ≤ k ≤ K.
Define I(D) as the collection of measurable indicator functions of subsets U ⊂ D.
Let uk = 1Uk , and note that uk ∈ I(D) is an extension of the indicator un,k =
1Un,k , defined on Xn , for 1 ≤ k ≤ K. Of course, the family {uk }K
k=1 satisfies
PK
k=1 uk = 1D .
5.1. Convergence of graph total variation. To show a.s. convergence of the
graph total variations, we first state that its expectations converge, and then use
concentration ideas to elicit convergence of the random quantitites.
Let u ∈ L1 (D). We define the nonlocal total variation of u to be
Z Z
1
:=
T V (u; ρ)
η (x − y)|u(x) − u(y)|ρ(x)ρ(y) dx dy.
 D D
Note that, if X and Y are independent random variables with density ρ, we have
h1
i
E η (X − Y )|u(X) − u(Y )| = T V (u; ρ).


CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 23

Recalling the definition (4.3) of the graph total variation, we therefore have
h
i
E GT Vn (u) = T Vn (u; ρ).
Let also

Z
η(x)|x1 |dx.

ση :=
D

Lemma 5.1. Let u ∈ L1 (D) such that T V (u; ρ2 ) < ∞. Then, we have
lim T V (u; ρ) = ση T V (u; ρ2 ).

→0

(5.1)

Proof. For general ρ, continuous on D and bounded above and below by positive
constants, and d ≥ 2, the result follows from part of the proof of [37], Theorem
4.1 (see Remark 4.3 in [37]), which is a much more involved result. This proof also
holds in d = 1.
For the convenience of the reader, we make a few remarks (see also remarks in
[37]), addressing the case ρ = 1D . Integrals of the form
Z
|u(x) − u(y)|
dx dy
(5.2)
η (x − y)
|x − y|
D×D
are considered in [14], where the limiting behavior as  → 0 is established for u ∈
W 1,1 (D). In [23] and [64], this is extended to general u such that T V (u; 1D ) < ∞,
with the result being
Z
|u(x) − u(y)|
dx dy = K1,d T V (u; 1),
(5.3)
lim
η (x − y)
→0 D×D
|x − y|
R
1
|e · σ| dHd−1 is the average of the e1 component of
where K1,d = Hd−1 (S
d−1 )
S d−1 1
the unit normal vector field on the unit sphere S d−1 (see [64], Corollary 1.3).
The limit (5.3) implies (5.1). Indeed,
Z
1
T V (u; 1D ) =
η (x − y)|u(x) − u(y)| dx dy
 D×D
Z
(5.4)
|u(x) − u(y)|
=
η̃ (x − y)
dx dy,
|x − y|
D×D
R
d
with η̃(z) = η(z)|z| and η̃ (z) = η̃(z/)/ . Letting c = Rd η(z)|z| dz, it follows
from (5.3) that
Z
|u(x) − u(y)|
lim T V (u; 1D ) = lim
η̃ (x − y)
dx dy
→0
→0 D×D
|x − y|
(5.5)
= cK1,d T V (u; 1D ).
R
Finally, one may verify that cK1,d = Rd η(z)|z1 | dz = ση , as desired.

We now proceed to the almost sure convergence of the graph total variation to
its continuum limit.
Lemma 5.2. Fix u ∈ I(D) where T V (u; ρ2 ) < ∞, and let {n }n∈N be a sequence
converging to zero such that
∞
X
n=1

exp(−n(d+1)/2
) < +∞.
n

(5.6)

24

ERIK DAVIS AND SUNDER SETHURAMAN

Then,
a.s.

GT Vn (u) −−→ ση T V (u; ρ2 )
as n → ∞.
1
η (x − y)|u(x) − u(y)|, so that we have
n n
X
1
GT Vn (u) =
fn (Xi , Xj ).
n(n − 1)

Proof. Let fn (x, y) =

1≤i6=j≤n

We let Efn denote E[fn (Xi , Xj )] = T Vn (u; ρ), so that

X 
1
fn (Xi , Xj ) − Efn + Efn .
GT Vn (u) =
n(n − 1)
1≤i6=j≤n

By Lemma 5.1, we have limn→∞ Efn = ση T V (u; ρ2 ). Therefore, it remains to argue

X 
1
that lim
fn (Xi , Xj ) − Efn = 0 almost surely.
n→∞ n(n − 1)
1≤i6=j≤n

We introduce a bit of notation. Let
Z
ln (Xi ) =
fn (Xi , y)ρ(y) dy
D
Z
mn (Xj ) =
fn (x, Xj )ρ(x) dx
D

hn (Xi , Xj ) = fn (Xi , Xj ) − ln (Xi ) − mn (Xj ) + Efn ,
so that we have
fn (Xi , Xj ) − Efn = hn (Xi , Xj ) + (ln (Xi ) − Efn ) + (mn (Xj ) − Efn ).
Summing this gives
X
1
n(n − 1)




fn (Xi , Xj ) − Efn =

1≤i6=j≤n

+

1
n(n − 1)

X

1 X
1 X
(ln (Xi ) − Efn ) +
(mn (Xj ) − Efn ).
n
n
1≤i≤n

hn (Xi , Xj )

1≤i6=j≤n

(5.7)

1≤j≤n

We handle the three terms on the right hand side of the above equation separately.
First, note that Eln = Efn . An application of Bernstein’s inequality ([76],
Lemma 19.32) in this setting yields, for s > 0,
 1X

 1

ns2
ln (Xi ) − Efn > s ≤ 2exp −
P
.
2
n i
4 Eln + skln kL∞
In Lemma 7.2 of the Appendix, we prove the upper bounds Eln2 ≤ C/n and
kln kL∞ ≤ C/n where C is a constant independent of n. Hence, we have
 1X

  n s2 
n
ln (Xi ) − Efn > s ≤ 2exp −
P
.
n i
C s+1
By our assumption (5.6), this implies
∞
 1X

X
P
ln (Xi ) − Efn > s < ∞,
n i
n=1

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 25

and so, as n → ∞,
n

1X
a.s.
ln (Xi ) − Efn −−→ 0.
n i=1
Similarly, we have, as n → ∞,
n
1X
n

(5.8)

a.s.

mn (Xj ) − Efn −−→ 0.

(5.9)

j=1

What remains is the double sum

1
n(n − 1)

X

hn (Xi , Xj ). Let Y1 , . . . , Yn be

1≤i6=j≤n

independent copies of X1 , . . . , Xn . By the decoupling inequality of de la Peña and
Montgomery-Smith [24], there is a constant C independent of n and h such that


X
1
(5.10)
hn (Xi , Xj ) > s
P
n(n − 1)
1≤i6=j≤n


X
1
≤CP C
hn (Xi , Yj ) > s .
n(n − 1)
1≤i6=j≤n
P
The sum 1≤i6=j≤n hn (Xi , Yj ) is canonical, that is, EX [hn (Xi , Yj )] = 0 a.s. and
EY [hn (Xi , Yj )] = 0 a.s., where EX and EY denote expectation with respect to the
first and second variables respectively. A general concentration inequality for Ustatistics given by Giné, Latala and Zinn in Theorem 3.3 of [41], states, for canonical
kernels {hi,j }1≤i,j≤n , that

h 1
 X
s2 s s2/3 s1/2 i
hi,j (Xi , Yj ) > s ≤ L exp − min ( 2 , , 2/3 , 1/2 ) ,
P
L
R Z B
A
1≤i,j≤n
for all s > 0, where L is a constant not depending on {hi,j }1≤i,j≤n or n, and
X
A = maxkhi,j kL∞ ,
R2 =
Eh2i,j ,
i,j

i,j

h X
i
X
B = max k
EX h2i,j (Xi , y)kL∞ , k
EY h2i,j (x, Yj )kL∞ ,
2

i,j

Z = sup{E

i

X

j

hi,j (Xi , Yj )fi (Xi )gj (Yj ) : E

i,j

X
i

fi2 (Xi ) ≤ 1, E

X

gj2 (Yj ) ≤ 1}.

j

In our context, we take hi,j = hn for i 6= j, and hi,j = 0 otherwise, which gives
the constants A = khn kL∞ , B 2 = (n−1) max(kEX h2n k, kEY h2n k), R2 = n(n−1)Eh2n
and, after a manipulation, Z ≤ nkhn kL2 →L2 , where
khn kL2 →L2 := sup{Eh(X, Y )f (X)g(Y ) : Ef 2 (X) ≤ 1, Eg 2 (Y ) ≤ 1}.
It follows that

1
P
n(n − 1)

X


hn (Xi , Yj ) > s

(5.11)

1≤i6=j≤n

h
 n2 s2
ns
1
,
,
≤ Lexp − 0 min
L
Eh2n khn kL2 →L2
n2/3 s2/3
ns1/2 i
,
,
[max(kEX h2n kL∞ , kEY h2n kL∞ )]1/3 khn k1/2
∞
L

26

ERIK DAVIS AND SUNDER SETHURAMAN

for some constant L0 independent of n and h.
In Corollary 7.3 of the Appendix, we prove the upper bounds
Eh2n ≤ C/d+1
n ,

kEY h2n kL∞ ≤ C/d+2
n ,

khn kL∞ ≤ C/d+1
n ,

kEX h2n kL∞ ≤ C/d+2
n ,

khn kL2 →L2 ≤ C/n .

Hence, the minimum in the right hand side of (5.11) simplifies to
2
(d+2)/3 2/3
C min(n2 d+1
s , n(d+1)/2
s1/2 ).
n s , nn s, nn
n
(d+1)/2

We claim, for sufficiently large n, this minimum will be attained by nn
s1/2 :
(d+1)/2
(d+1)/2
Indeed, by (5.6), nn
→ ∞, and so nn
is smaller than n2 d+1
n . Also,
(d+1)/2
(d+2)/3
nn is larger than nn
since n → 0 and d ≥ 1. In addition, nn
is larger
(d+1)/2
than nn
as d ≥ 1.
Hence, we have




X
1
1/2
hn (Xi , Yj ) > s ≤ L exp − Cn(d+1)/2
s
,
(5.12)
P
n
n(n − 1)
1≤i6=j≤n

where C is a constant independent of n. Combining (5.11) and (5.12), gives
∞


X
X
1
hn (Xi , Xj ) > s < ∞,
P
n(n − 1)
n=1
1≤i6=j≤n

for all s. Therefore,
1
n(n − 1)

a.s.

X

hn (Xi , Xj ) −−→ 0,

(5.13)

1≤i6=j≤n

as n → ∞. Applying (5.8), (5.9), and (5.13) to (5.7) completes the proof.



5.2. Quadratic Term. We first consider convergence of certain ‘mean-values’, and
then treat the random expressions, for various values of α, in the subsequent subsubsections.
For u ∈ L1 (D) and  > 0, define Λ (u) by
Z Z
α
Λ (u) :=
η (x − y)ρ(y) dy u(x)ρ(x) dx.
D

D

Let
Z
η (x − y)ρ(y) dy,

(5.14)

u(x)(ρ (x))α ρ(x) dx.

(5.15)

ρ (x) :=
D

and write, with this notation,
Z
Λ (u) =
D

Define also
Z
Λ(u) :=

u(x)ρ1+α (x)dx.

(5.16)

D

Lemma 5.3. Let g be a bounded, measurable function on the domain D. Then,
there exists a constant C, independent of g, such that
|Λ (g) − Λ(g)|≤ CkgkL∞ (D) ,

(5.17)

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 27
L1

for all sufficiently small . Further, suppose there is a sequence {g }>0 with g −→
g as  → 0. Then, we have
lim Λ (g ) = Λ(g).

(5.18)

→0

Proof. We first prove inequality (5.17). By Lemma 7.1 in the Appendix, there exist
positive constants A, B such that, for sufficiently small , both ρ and ρ take values
in the interval [A, B]. Then we have
Z
Z
α
|Λ (g) − Λ(g)| =
g(x)(ρ (x)) ρ(x) dx −
g(x)(ρ(x))α ρ(x) dx
D
D
Z
∞
≤ BkgkL
|(ρ (x))α − (ρ(x))α | dx
ZD
≤ CkgkL∞ |ρ (x) − ρ(x)| dx,
D

where the last inequality follows from the observation
that x 7→ xα is Lipschitz on
R
the interval [A, B]. By Lemma 7.1 again, where D |ρ (x)−ρ(x)| dx ≤ C 0  is proved,
we obtain
|Λ (g) − Λ(g)|≤ C 00 kgkL∞ .
L1

We now prove (5.18). Suppose we have a family {g }>0 with g −→ g as  → 0.
Then,
Z
lim |Λ (g ) − Λ(g)| ≤ lim
|g (x)(ρ (x))α − g(x)(ρ(x))α |ρ(x) dx.
→0

→0

D

Since ρ is bounded, it is sufficient to prove that
Z
lim
|g (x)(ρ (x))α − g(x)(ρ(x))α | dx = 0.
→0

D

Writing
α
α
α
α
α
g ρα
 − gρ = g ρ − gρ + gρ − gρ ,

one may obtain
Z
D

α
|g (x)ρα
 (x) − g(x)ρ (x)| dx
Z
Z
α
α
≤
|g (x) − g(x)|ρ (x) dx + kgkL∞ |ρα
 (x) − ρ (x)| dx.
D

D

Now, since g → g in L1 , and ρ is bounded above and below by Lemma 7.1, we
have that the first term on the right hand side vanishes in the limit. Likewise, by
Lemma 7.1, we have also ρ → ρ a.e. as  → 0. By dominated convergence, then,
the second term on the right hand side vanishes, completing the proof.

In the following Subsubsection 5.2.1, the cases α = 0, 1 are considered. Then, in
Subsubsection 5.2.2, the general α 6= 0, 1 case is treated, where different techniques
are used as the the functional is nonlinear.

28

ERIK DAVIS AND SUNDER SETHURAMAN

5.2.1. Quadratic Term: α = 0 or α = 1. The expression (4.5) for GΛn simplifies
to give
( Pn
1
u(Xi ),
when α = 0,
GΛn (u) = n 1 i=1P
η
(X
−
X
)u(X
),
when α = 1.
i
j
i
1≤i6=j≤n n
n(n−1)
Lemma 5.4. Fix α = 0. Let u be a bounded, measurable function on the domain
D, and let {n }n∈N be a sequence converging to zero such that
lim

n→∞

log log n
= 0.
nn

Then,

1 
a.s.
GΛn (u) − Λ(u) −−→ 0.
√
n
as n → ∞.
Proof. By the law of the iterated logarithm, and the boundedness of u, we have
n
GΛn (u) − Λ(u) ≤ C,
a.s.
lim sup √
2n log log n
n→∞
We may write
 √2n log log n


n
1 
√
GΛn (u) − Λ(u) =
GΛn (u) − Λ(u) ,
√
√
n
n n
2n log log n


√
a.s.
√ log n = 0. Hence, √1
where by assumption, limn→∞ nnlog
n
n GΛn (u) − Λ(u) −−→ 0
as n → ∞.

Lemma 5.5. Fix α = 1. Let u be a bounded, measurable function on the domain
D, and let {n }n∈N be a sequence converging to zero such that
∞
X

exp(−n(d+1)/2
) < +∞.
n

(5.19)

n=1

Then,

1 
a.s.
GΛn (u) − Λ(u) −−→ 0,
√
n
as n → ∞.
Proof. We first rewrite



1 
1 
1 
GΛn (u) − Λ(u) = √
GΛn (u) − Λn (u) + √
Λn (u) − Λ(u) .
√
n
n
n
R R
Here, as α = 1, Λn (u) = D D ηn (x − y)u(x)ρ(x)ρ(y) dx dy.
By an application of inequality (5.17), the second
term on the right

 vanishes as
n → ∞. Hence, we must show that limn→∞ √1n GΛn (u) − Λn (u) = 0 a.s.
1
Let fn (x, y) = √ ηn (x − y)u(x). Note, for i 6= j, that Efn = Efn (Xi , Xj ) =
n
√1 Λ (u). Then,
n
n

X
1 
1
GΛn (u) − Λn (u) =
fn (Xi , Xj ) − Efn .
√
n
n(n − 1)
1≤i6=j≤n

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 29

Let
Z
ln (Xi ) =

fn (Xi , y)ρ(y) dy
D

Z
mn (Xj ) =

fn (x, Xj )ρ(x) dx
D

hn (Xi , Xj ) = fn (Xi , Xj ) − ln (Xi ) − mn (Xj ) + Efn ,
so that we have
fn (Xi , Xj ) − Efn = hn (Xi , Xj ) + (ln (Xi ) − Efn ) + (mn (Xj ) − Efn ).
Summing this gives
1
n(n − 1)
=

fn (Xi , Xj ) − Efn



(5.20)

1≤i6=j≤n

1
n(n − 1)
+



X

X

hn (Xi , Xj )

1≤i6=j≤n

1X
1X
(ln (Xi ) − Efn ) +
(mn (Xj ) − Efn ).
n i
n j

We handle the three terms on the right hand side of the above equation separately.
Note that Eln = Efn . An application of Bernstein’s inequality ([76], Lemma
19.32) yields, for s > 0, that
 1X

 1

ns2
P
ln (Xi ) − Efn > s ≤ 2exp −
.
n i
4 Eln2 + skln kL∞
In Lemma 7.4 of the Appendix, we prove the upper bounds Eln2 ≤ C/n and
1/2
kln kL∞ ≤ C/n , where C is a constant independent of n. Hence, we have
 1X


Cn ns2 
P
ln (Xi ) − Efn > s ≤ 2 exp −
,
1/2
n i
1 + n s
where C is another constant independent of n. By the assumption (5.19), this
implies
∞
 1X

X
P
ln (Xi ) − Efn > s < ∞,
n i
n=1
and so
n

1X
a.s.
ln (Xi ) − Efn −−→ 0
n i=1

(5.21)

as n → ∞. The same argument also implies that
n

1X
a.s.
mn (Xj ) − Efn −−→ 0,
n j=1
as n → ∞.
What remains is the double sum

1
n(n − 1)

X

(5.22)

hn (Xi , Xj ). Let Y1 , . . . , Yn be

1≤i6=j≤n

independent copies of X1 , . . . , Xn . By the decoupling inequality of de la Peña and

30

ERIK DAVIS AND SUNDER SETHURAMAN

Montgomery-Smith ([24]), there exists a constant C independent of n and h such
that


X
1
P
(5.23)
hn (Xi , Xj ) > s
n(n − 1)
1≤i6=j≤n


X
1
≤CP C
hn (Xi , Yj ) > s .
n(n − 1)
1≤i6=j≤n

As in the proof of the GTV case (Lemma 5.2), the hn here are canonical. Recalling the U-statistics inequality of Giné, Latala and Zinn, Theorem 3.3 of [41],
with the same application as in the proof of Lemma 5.2, we have


X
1
(5.24)
P
hn (Xi , Yj ) > s
n(n − 1)
1≤i6=j≤n

h

≤ Lexp −

 n2 s2
1
ns
,
min
,
0
2
L
Ehn khn kL2 →L2
n2/3 s2/3
ns1/2 i
,
.
[max(kEX h2n kL∞ , kEY h2n kL∞ )]1/3 khn k1/2
∞
L

In Corollary 7.5 of the Appendix, we prove the upper bounds
kEY h2 kL∞ ≤ C/d+1
n ,

Eh2n ≤ C/d+1
n ,

d+1/2

khn kL∞ ≤ C/n

kEX h2 kL∞ ≤ C/d+1
n ,
1/2

khn kL2 →L2 ≤ C/n .

,

Hence, the minimum in the right hand side of (5.24) is bounded below by
2
1/2
(d+1)/3 2/3
C min(n2 d+1
s , n(d+1/2)/2
s1/2 ).
n s , nn s, nn
n
(d+1)/2

Note that n vanishes, and our assumption (5.19) implies that nn
n → ∞. Therefore, we conclude, for sufficiently large n, that

→ ∞ as

2
1/2
(d+1)/3 2/3
C min(n2 d+1
s , n(d+1/2)/2
s1/2 ) ≥ Cn(d+1)/2
min(s2 , s1/2 ).
n s , nn s, nn
n
n

Hence. we have

X
1
P
n(n − 1)




hn (Xi , Yj ) > s ≤ L exp − Cn(d+1)/2
min(s1/2 , s2 ) ,
n

1≤i6=j≤n

(5.25)
where C is a constant independent of n. Combining (5.24) and (5.25), and summing
over n, gives
∞


X
X
1
P
hn (Xi , Xj ) > s < ∞,
n(n − 1)
n=1
1≤i6=j≤n

for all s > 0. Therefore,
1
n(n − 1)

X

a.s.

hn (Xi , Xj ) −−→ 0,

(5.26)

1≤i6=j≤n

as n → ∞.
Applying (5.21), (5.22), and (5.26) to (5.21) completes the proof.



CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 31

5.2.2. Quadratic Term: General α. Recall, from (4.5) and (5.16), the forms of
GΛn (u) and Λ(u).
Lemma 5.6. Fix a bounded, measurable function u on the domain D, and let
{n }n∈N be a sequence converging to zero such that
∞
X

n exp(−nd+1
n ) < +∞.

(5.27)

n=1

Then,

1 
a.s.
GΛn (u) − Λ(u) −−→ 0,
√
n
as n → ∞.
Proof. Recall the forms of ρ and Λ in (5.14) and (5.15) respectively. We now
introduce the intermediate term
1 X
GΛn (u) :=
ρn (Xi )α u(Xi ).
(5.28)
n
1≤i≤n

Then,
GΛn (u) − Λ(u) = GΛn (u) − GΛn (u) + GΛn (u) − Λn (u) + Λn (u) − Λ(u).
The proof proceeds in three steps:
Step 1. We first attend to GΛn (u) − GΛn (u). We claim that
1
a.s.
√ (GΛn (u) − GΛn (u)) −−→ 0,
n
as n → ∞. Define
Zi =

(5.29)

X
1
η (Xi − Xj ),
n − 1 1≤j≤n n
j6=i

so that GΛn (u) =

1
n

Pn

α
i=1 Zi u(Xi ). Then we have

E[Zi |Xi ] = ρn (Xi ),
and further, an application of Bernstein’s inequality (Lemma 19.32 of [76]) gives


 1 t2 (n − 1) 
P |Zi − ρn (Xi )|> t Xi ≤ 2 exp −
,
(5.30)
4 a + tb
where a = E[ηn (Xi −Xj )2 |Xi ] and b = supx∈D |ηn (Xi −x)|. Recalling the definition
η (z) = η(z/)/d and the assumptions (K1), (K4), we have a ≤ C/dn and b ≤ C/dn .
Therefore, inequality (5.30) implies



t2 (n − 1)dn 
P |Zi − ρn (Xi )|> t Xi ≤ 2 exp − C
(t + 1)
in terms of a constant C not depending on n. Applying a union bound gives




P sup |Zi − ρn (Xi )|> t ≤ nP |Zi − ρn (Xi )|> t
1≤i≤n


t2 (n − 1)dn 
.
≤ Cn exp − C
(t + 1)

(5.31)

By Lemma 7.1, there exist positive constants A, B such that, for sufficiently
small , both ρ and ρ take values in the interval [A, B]. Let Jn denote the event

32

ERIK DAVIS AND SUNDER SETHURAMAN

that sup1≤i≤n |Zi − ρn (Xi )|< A/2. Then, if Jn holds, the inequality A/2 < Zi <
B + A/2 is satisfied for all i. Since the function x 7→ xα is Lipschitz on the interval
[A/2, B + A/2], we obtain
|Ziα − ρn (Xi )α |≤ C|Zi − ρn (Xi )|.

(5.32)

Hence, when Jn occurs, inequality (5.32) and kukL∞ < ∞ imply, with respect to
another constant C independent of n, that
1 X
|Ziα − ρn (Xi )α ||u(Xi )|
|GΛn (u) − GΛn (u)|≤
n
1≤i≤n

1 X
≤C
|Zi − ρn (Xi )|≤ C sup |Zi − ρn (Xi )|,
n
1≤i≤n
1≤i≤n

and moreover,
1
1
sup |Zi − ρn (Xi )|.
√ |GΛn (u) − GΛn (u)|≤ C √
n
n 1≤i≤n
It follows, by (5.31), that
o
n 1

P √ |GΛn (u) − GΛn (u)|> t ∩ Jn
n


1
≤ P C√
sup |Zi − ρn (Xi )|> t
n 1≤i≤n


t2 (n − 1)d+1
n
≤ Cn exp − C
.
t+1
On the other hand, by (5.31) again, we have

A2 (n − 1)dn 
P(Jnc ) ≤ Cn exp − C
.
A+1
Combining (5.34) and (5.34) gives

 1
P √ |GΛn (u) − GΛn (u)|> t
n
n 1
o

≤ P √ |GΛn (u) − GΛn (u)|> t ∩ Jn + P(Jnc )
n


≤ Cn exp − C(n − 1)d+1
,
n

(5.33)

(5.34)

for some constant C not depending on n.
From our assumption (5.27) on n , it follows that
∞

 1
X
P √ |GΛn (u) − GΛn (u)|> t < ∞,
n
n=1
and so

1
a.s.
√ (GΛn (u) − GΛn (u)) −−→ 0.
n

Step 2. Now, we argue that

1 
a.s.
GΛn (u) − Λn (u) −−→ 0,
√
n
as n → ∞.

(5.35)

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 33

Noting (5.15), since
E[ρn (Xi )α u(Xi )] = Λn (u),
by Bernstein’s inequality (Lemma 19.32 of [76]), we have
 1 1 X

 1 t2  n 
n
P √
,
ρn (Xi )α u(Xi ) − Λn (u) > t ≤ 2 exp −
√
n n
4 a + t n b
1≤i≤n

where a = E[(ρ(Xi )α u(Xi ))2 ] and b = supx∈D |ρn (x)α u(x)|. Both of these are
bounded by a constant C, and so by the assumption (5.27) on n , we obtain
∞

 1
X
P √ |GΛn (u) − Λn (u)|> t < ∞,
n
n=1
and therefore (5.35).
Step 3. By Lemma 5.3, we have
|Λn (u) − Λ(u)|≤ CkukL∞ n .
It follows that

1 
Λn (u) − Λ(u) → 0,
√
n

(5.36)

as n → ∞. Combining (5.29), (5.35), and (5.36) gives

1 
a.s.
GΛn (u) − Λ(u) −−→ 0,
√
n
as n → ∞, finishing the proof of the lemma.



5.3. Proof of Theorem 2.1. Recall equation (4.7) which decomposes the modularity Qn (Un ) with respect to partitions Un of Xn induced from a partition U =
2
{Uk }K
k=1 of D, where each of the sets URk have finite perimeter, Per(Uk ; ρ ) < ∞.
α
1+α
Since S/(n(n − 1) ) = GΛn (1) and D ρ
(x) dx = Λ(1), by Lemmas 5.4, 5.5,
and 5.6, which cover the cases α = 0, α = 1, and α 6= 0, 1, we have
Z
S
a.s.
−−→
ρ1+α (x) dx
(5.37)
n(n − 1)α
D
as n → ∞. In particular, when α = 1, we have, as n → ∞,
Z
X
1
2m
a.s
=
ηn (Xi − Xj ) −−→
ρ2 (x) dx.
n(n − 1)
n(n − 1)
D

(5.38)

1≤i,j≤n
i6=j

Further, these same lemmas, applied to the indicators {uk = 1Uk }K
k=1 , imply that
K
X

a.s.

(GΛn (uk − 1/K))2 −−→

k=1

K
X

(Λ(uk − 1/K))2

k=1

as n → ∞. Hence, combining these limits,
K

K

k=1

k=1

i
2
X
n2 (n − 1)2α h X
a.s.
2
(GΛ
(u
−
1/K))
−
−
→
µ(U
)
−
1/K
,
n
k
k
S2
as n → ∞, with dµ(x) =

1+α
(x)
R ρ
1+α (x) dx .
ρ
D

(5.39)

34

ERIK DAVIS AND SUNDER SETHURAMAN

By Lemma 5.2, we have, as n → ∞,
K
X

a.s.

GT Vn (uk ) −−→ ση

k=1

where ση =

R
Rd

K
X

T V (uk ; ρ2 ),

k=1

η(x)|x1 | dx. Therefore,
K

K

k=1

k=1

X
ση
n(n − 1) X
a.s.
GT Vn (uk ) −−→ R 2
T V (uk ; ρ2 ),
4m
2 D ρ (x)dx

(5.40)

as n → ∞.
Since limn→∞ n = 0, and T V (uk ; ρ2 ) < ∞ for 1 ≤ k ≤ K as the sets in U have
PK
finite perimeter, noting (5.38) and (5.40), we have that n n(n−1)
k=1 GT Vn (uk )
4m
vanishes a.s., as n → ∞. Hence, from the limit (5.39), we obtain the first statement
(2.8) in Theorem 2.1.
To prove the second statement (2.9), we write, dividing (4.7) by n , that
1 − 1/K − Qn (U)
n
K
K
i n(n − 1) X
2
n (n − 1)2α h X 1
2
(
GT Vn (uk ).
=
GΛ
(u
−
1/K))
+
√
n
k
S2
n
4m
k=1
k=1
PK
By assumption, the partition U is balanced with respect to dµ, and so k=1 (µ(Uk )−
1/K)2 = 0. Equivalently, recalling the definition (5.16) of Λ, we have Λ(uk −1/K) =
0 for 1 ≤ k ≤ K.
Hence, writing gk = uk − 1/K, it follows that
K 
K 
2 X
2
X
1 
1
a.s.
GΛn gk − Λgk
−−→ 0,
√ GΛn (uk − 1/K) =
√
n
n

k=1

(5.41)

k=1

as n → ∞, by Lemmas 5.4, 5.5, and 5.6 for the various cases of α. Combining
(5.40) and (5.41) gives
K

X
1 − 1/K − Qn (U) a.s.
ση
T V (uk ; ρ2 ),
−−→ R 2
n
2 D ρ (x) dx
k=1

as n → ∞. This finishes the proof of Theorem 2.1.



6. Proof of Theorem 2.3: Optimal clusterings
The general approach to proving Theorem 2.3 is to formulate both the modularity clustering problem (2.3) and the continuum partitioning problem (2.6) as
optimization problems on the common metric space (T L1 (D))K , say equipped with
the product metric. Although we wish to maximize the modularity, it will be convenient later in Subsection 6.1 to pose an equivalent problem of minimizing a related
energy En .
Thus, the maximum modularity clusterings of the graph Gn = (Xn , Wn ) will be
related to the solution of
minimize
En (V),
V∈(T L1 (D))K

and likewise, the optimal partitions of Problem (2.6) will be related to the solution
of
minimize
E(V).
V∈(T L1 (D))K

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 35

We then argue in Subsection 6.2 that the random functionals En Γ((T L1 )K )converge to E, in the sense of Definition 3.8, which when taken with an additional
compactness property given in Subsection 6.3 will be sufficient to imply that the
minimizers of En converge subsequentially in (T L1 )K to a minimizer of E, and
thereby prove Theorem 2.3 at the end of the section.
6.1. Reformulation as a mimimization problem. Recall the identity (4.7),
1 − 1/K − Qn (Un )
K
K
i
n2 (n − 1)2α h X
n(n − 1) X
2
=
(GΛ
(u
−
1/K))
+

GT Vn (un,k ),
n n,k
n
S2
4m
k=1

k=1

{Un,k }K
k=1

where Un =
is a partition of the data points Xn and un,k = 1Un,k ∈ In (D)
for 1 ≤ k ≤ K. As is our convention, we note that some of the {Un,k }K
k=1 may be
empty sets, and so generally we have |U|≤ K.
We define
K
i
1 n2 (n − 1)2α h X
2
Fn (Un ) :=
(GΛn (un,k − 1/K))
(6.1)
2
n
S
k=1

and
K

T Vn (Un ) :=

n(n − 1) X
GT Vn (un,k ),
4m

(6.2)

k=1

so that the problem of maximizing Qn (Un ) over clusterings Un of Xn with |Un |≤ K
is equivalent to that of minimizing Fn (Un ) + T Vn (Un ).
We now place the modularity optimization problem on the space (T L1 (D))K .
Recalling that νn denotes the empirical measure, we define Mn (D) ⊂ (T L1 (D))K
by
K
n
o
X
K
Mn (D) := ((νn , un,k ))k=1 : un,k ∈ In (D),
un,k = 1Xn .
k=1

As a notational convenience, we often denote elements of Mn (D) by
(νn , Un ) := {(νn , un,k )}K
k=1 ,
where un,k = 1Un,k and Un = {Un,k }K
k=1 .
1
K
Define En : (T L (D)) × Ω → [0, ∞] by
(
Fn (Un ) + T Vn (Un ), if Vn = (νn , Un ) ∈ Mn (D),
En (Vn ) =
∞,
otherwise.

(6.3)

The energy minimization problem
minimize

Vn ∈(T L1 (D))K

En (Vn ),

(6.4)

is equivalent to the K-class modularity clustering problem (2.3), in the sense that
Un is a solution to (2.3) iff Vn = (νn , Un ) is a solution to (6.4).
Similarly, we define continuum functionals on partitions U = {Uk }K
k=1 of D, via
their indicators {uk }K
⊂
I(D),
by
k=1
(
PK
(k)
0, if
) − 1/K)2 = 0,
k=1 (µ(U
F (U) =
(6.5)
∞, otherwise,

36

ERIK DAVIS AND SUNDER SETHURAMAN

and
T V (U) = Cη,ρ

K
X

T V (uk ; ρ2 ),

(6.6)

k=1

R
where dµ = ρ1+α dx/ D ρ1+α (x) dx and
Cη,ρ

R
η(x)|x1 |dx
ση
=
= DR 2
.
2 D ρ2 (x) dx
2 D ρ (x) dx
R

Define M (D) ⊂ (T L1 (D))K by
K
K
n
o
X
X
M (D) := ((ν, uk ))K
:
u
∈
I(D),
u
=
1
,
T V (uk , ρ2 ) < ∞ .
k
k
D
k=1
k=1

k=1

As before, we denote elements of M (D) by
(ν, U) := {(ν, uk )}K
k=1 ,
where U = {Uk }K
k=1 and uk = 1Uk for 1 ≤ k ≤ K.
Define the energy E : (T L1 (D))K → [0, ∞] as
(
F (U) + T V (U), if V = (ν, U) ∈ M (D),
E(V) :=
∞,
otherwise.

(6.7)

Then, with µ as above and φ = ρ2 , the continuum partitioning problem (2.6),
which does not include the prefactor Cη,ρ , is equivalent to
minimize

V∈(T L1 (D))K

E(V),

(6.8)

in the sense that U is a solution to (2.6) iff V = (ν, U) is a solution to (6.8).
As noted in Subsection 2.2, since there is a solution to (2.6), the problem (6.8)
also possesses a solution. In particular, the energy E is not identically infinite.
6.2. Gamma convergence. We now state the Gamma convergence used later in
the proof of Theorem 2.3.
Theorem 6.1. Under the assumptions of Theorem 2.3, the random functionals En : (T L1 (D))K × Ω → [0, ∞], given in (6.3), Γ-converge in (T L1 )K to
E : (T L1 (D))K → [0, ∞], given in (6.7):
Γ((T L1 ))K

En −−−−−−−→ E,
as n → ∞, in the sense of Definition 3.8.
Proof. The proof of Theorem 6.1 is in two steps. In Subsection 6.2.1, via Lemma
6.7, we give the ‘liminf’ estimate. In Subsection 6.2.2, through Lemma 6.9, we
prove the ‘recovery sequence’ property.

6.2.1. Liminf Inequality. We now argue the liminf inequality for the Γ-convergence
in Theorem 6.1, according to Definition 3.8. Recall that Ω0 denotes the probability
1 set of realizations {Xi }i∈N , under which Proposition 3.2 holds.
We first show a closure property of Mn (D) and M (D).
Lemma 6.2. On the probability 1 set Ω0 , the following statement holds: If {Vn }n∈N
(T L1 )K

is a sequence in Mn (D) and Vn −−−−−→ V, then V ∈ M (D).

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 37

Proof. Fix a realization in the probability 1 set Ω0 . Let Vn = ((νn , un,k ))K
k=1 and
1
V = ((µk , uk ))K
.
By
the
characterization
of
T
L
convergence,
Lemma
3.1, for
k=1
w
each 1 ≤ k ≤ K we have νn −
→ µk , and so by Corollary 3.3 it follows that µk = ν.
Further, we have
Z
|uk (x) − un,k (Tn x)|ρ(x)dx = 0,

lim

n→∞

D

where {Tn }n∈N is the sequence of transportation maps given in Proposition 3.2.
Hence, as ρ is bounded above and below on D, it follows that uk is the L1 limit
of a sequence of indicator functions ũn,k (x) := un,k (Tn x) ∈ I(D). It follows, by
subsequential Lebesgue a.e. convergence, that uk ∈ I(D). Similarly, the relation
PK
K
k=1 uk = 1D follows from the corresponding relations for {un,k }k=1 . Thus, V =
K
((ν, uk ))k=1 ∈ M (D).

We now establish the following technical lemma, which adapts a technique from
the proof of Theorem 1.1 in [37] to relate graph functionals with their continuum
nonlocal analogues.
Lemma 6.3. On the probability 1 set Ω0 , the following statement holds: Given any
sequence of uniformly bounded, nonnegative functions {gn }n∈N , and a function g,
T L1

if (νn , gn ) −−→ (ν, g), then
lim GΛn (gn ) = Λ(g).

n→∞

Proof. Fix a realization in the probability 1 set Ω0 . Recall, from (4.5) and (5.16),
that
n
α
X
1 X 1
GΛn (gn ) =
ηn (Xi − Xj ) gn (Xi )
n i=1 n − 1 1≤j≤n
j6=i
n
n
1 X1 X
ηn (0) α
n
η
(X
−
X
)
−
gn (Xi ),

i
j
n
(n − 1)α n i=1 n j=1
n
α

=

R
and Λ(g) = D ρ1+α (x)g(x)dx. Let {Tn }n∈N be the transport maps in Proposition
3.2. Since Tn] ν = νn , by a change of variables, we have
Z Z
nα
ηn (0) α
GΛn (gn ) =
η
(T
x
−
T
y)ρ(y)
dy
−
gn (Tn x)ρ(x) dx.

n
n
n
(n − 1)α D
n
D
R
For what follows,
let Rn (x) := D ηn (Tn x − Tn y)ρ(y) dy. Recall also, from (5.14),
R
that ρ (x) = D η (x − y)ρ(y)dy.
Step 1. First, suppose that η is of the form η(x) = a for |x|< b and η(x) = 0 for
|x|> b. Define
kId − Tn kL∞
n := n + 2
,
(6.9)
b
and note that, for Lebesgue a.e. (x, y) ∈ D × D,
|x − y| > bn implies |Tn x − Tn y| > bn .
By the form of η, we have the bound
T x − T y
x − y
n
n
η
≤η
.
n
n

38

ERIK DAVIS AND SUNDER SETHURAMAN

Integrating with respect to ρ(y) dy, and scaling appropriately, we obtain
Rn (x) ≤ (n /n )d ρn (x),
for Lebesgue a.e. x ∈ D.
By the assumption (I2) on n , together with the estimates in Proposition 3.2 on
{Tn }n∈N , it follows that n vanishes slower than kId − Tn kL∞ , and so for large n
we have
kId − Tn kL∞
> 0.
˜n := n − 2
b
In particular, for Lebesgue a.e. (x, y) ∈ D × D,
|Tn x − Tn y| > bn implies |x − y| > b˜
n
and so

T x − T y
n
n
.
(6.10)
˜n
n
Again, integrating with respect to ρ(y) dy and scaling appropriately, we obtain a
lower bound of Rn (x), and can write, for Lebesgue a.e. x,
η

x − y

≤η

(˜
n /n )d ρ˜n (x) ≤ Rn (x) ≤ (n /n )d ρn (x).

(6.11)

By the assumption (I2) on the rate n , we observe that
lim

˜n

n→∞ n

= lim 1 + 2
n→∞

kId − Tn kL∞
= 1.
n

Similarly, we have limn→∞ nn = 1.
In light of (6.11), and Lemma 7.1 in the Appendix, which shows lim→0 ρ = ρ
and bounds ρ from above and below, we make two observations:
i) For Lebesgue a.e. x, we have Rn (x) → ρ(x) as n → ∞.
ii) There exist constants A0 , B 0 > 0 such that, for all large n, A0 ≤ Rn (x) ≤ B 0
for Lebesgue a.e. x.
Step 2. Now let η be a simple function satisfying assumptions (K1)−(K4), which
PL
implies that we may write η as a convex combination η = l=1 λl η l for functions
R
(l)
(l)
η (l) satisfying the assumptions of Step 1. We let Rn (x) := D ηn (Tn x−Tn y)ρ(y) dy
P(l)
(l)
so that Rn (x) = l=1 λl Rn (x).
Hence,
(l)

i) For Lebesgue a.e. x, each Rn (x) → ρ(x) as n → ∞. The same holds for
the convex combination Rn .
(l)
ii) There exist constants A0 , B 0 > 0 such that, for all large n, A0 ≤ Rn (x) ≤ B 0
for Lebesgue a.e. x. Therefore, the same holds for Rn .
Note also, since limn→∞ ndn = ∞ by the assumption (I2), we have ηn (0)/n ≤
kηkL∞ (ndn )−1 vanishes as n → ∞. We have then, by bounded convergence, that
Z
Z
lim GΛn (gn ) − Λ(g) = lim
Rn (x)α gn (Tn x)ρ(x) dx −
g(x)ρ(x)1+α dx
n→∞
n→∞
D
Z D
α
α
≤ lim
Rn (x) gn (Tn x) − ρ(x) g(x) ρ(x) dx.
n→∞

D

Since ρ is bounded, we now argue that
Z
lim
Rn (x)α gn (Tn x) − ρ(x)α g(x) dx = 0.
n→∞

D

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 39

By adding and subtracting ρ(x)α gn (Tn x), we obtain
Z
Rn (x)α gn (Tn x) − ρ(x)α g(x) dx
D
Z
Z
α
α
gn (Tn x) − g(x) ρα (x) dx.
≤
Rn (x) − ρ(x) gn (Tn x) dx +
D

D

With respect to the first term on the right side, by assumption, gn (Tn x) is uniformly bounded. Also, the sequence Rn is bounded above and below, and converges
Lebesgue a.e. to ρ, so by dominated convergence the integral vanishes in the limit.
T L1

With respect to the second term on the right side, suppose (νn , gn ) −−→ (ν, g) as
n → ∞. Since ρ is bounded above and below, we have ρα is bounded, and the
corresponding integral, by the characterization of T L1 convergence in Lemma 3.1,
also vanishes in the limit.
Hence, when the kernel η is a simple function, we have that
lim GΛn (gn ) = Λ(g).

n→∞

(6.12)

Step 3. Now, we consider general η satisfying properties (K1) − (K4).
We first approximate η by simple functions η (k) , satisfying
(K2) − (K4), with
Pn  1 Pn
(k)
(k)
1
(k)
(k)
η
≤ η and η
→ η pointwise. Let GΛn (gn ) = n i=1 n−1 j=1 ηn (Xi −
α
R
Xj ) gn (Xi ), and λk = D η (k) (x)dx. Then, by (6.12), we have
lim

n→∞

1
GΛ(k)
n (gn ) = Λ(g).
λα
k

Because η (k) ≤ η, and the sequence {gn }n∈N is assumed nonnegative, we have that
lim inf
n→∞

1
GΛn (gn ) ≥ Λ(g),
λα
k

and taking the limit λk → 1 as k → ∞ gives
lim inf GΛn (gn ) ≥ Λ(g).
n→∞

(6.13)

Likewise, consider approximating η by simple functions η (k) satisfying (K2) −
(K4), with η (k) ≥ η and η (k) → η pointwise. Then, similarly, we obtain that
lim sup GΛn (gn ) ≤ Λ(g).

(6.14)

n→∞

Combining inequalities (6.13) and (6.14) gives that
lim GΛn (gn ) = Λ(g),

n→∞

completing the proof.



Lemma 6.4. On the probability 1 set Ω0 , the following statement holds: Given
(T L1 )K

any sequence {Vn }n∈N such that Vn −−−−−→ V, where Vn = (νn , Un ) ∈ Mn (D) and
V = (ν, U) ∈ M (D), then
F (U) ≤ lim inf Fn (Un ).
n→∞

(6.15)

40

ERIK DAVIS AND SUNDER SETHURAMAN

Proof. Fix a realization in the probability 1 set Ω0 . If F (U) = 0, the above inequality holds trivially. We now consider the other case when F (U) = ∞. Recalling the
definitions (6.5) and (5.16) of F and Λ, this means that there is a 1 ≤ k ≤ K such
that uk = 1Uk satisfies Λ(uk − 1/K) 6= 0. Let δ = Λ(uk − 1/K)2 > 0.
T L1

w

Now, by Corollary 3.3, νn −
→ ν, and so (νn , 1/K) −−→ (ν, 1/K) by Lemma 3.1,
as n → ∞. Therefore, by Lemma 6.3, as n → ∞ we have
Z
1
1
S
1
→
GΛn (1/K) =
Λ(1)
=
ρ1+α (x)dx.
K n(n − 1)α
K
K D
By decomposing GΛn (un,k − 1/K) = GΛn (un,k ) − GΛn (1/K) and noting Lemma
(T L1 )K

6.3 again, it follows that, if Vn −−−−−→ V, then
lim

n→∞

K
X

2

(GΛn (un,k − 1/K)) =

k=1

K
X

2

(Λ(uk − 1/K)) .

k=1

In particular, there is an N > 0, depending on the realization, such that, for n > N ,
we have
K
X
2
(GΛn (uk − 1/K)) ≥ δ/2.
k=1

Since
Fn (Un ) =

K
1 n2 (n − 1)2α X
2
(GΛn (un,k − 1/K)) ,
n
S2
k=1

and

n2 (n−1)2α
S2

R
−
→ ( D ρ1+α (x) dx)−2 , it follows that
lim inf Fn (Un ) ≥ lim inf
n→∞

n→∞

K
C X
2
(GΛn (uk − 1/K))
n
k=1

Cδ
≥ lim inf
= ∞.
n→∞ 2n
Hence, in this case also, inequality (6.15) holds.



Lemma 6.5. On the probability 1 set Ω0 , the following statement holds: Given any
T L1

sequence {un }n∈N such that (νn , un ) −−→ (ν, u), then
ση T V (u; ρ2 ) ≤ lim inf GT Vn (un ),
n→∞

where ση =

R
Rd

η(x)|x1 | dx.

Proof. The desired statement follows the same argument given for the liminf inequality for the Gamma convergence stated in Theorem 1.1 in [37]–see Step 3 of
Section 5.1 of [37]. There, the probability 1 set is Ω0 . We note this proof, although
stated for d ≥ 2, also holds in d = 1 with the same notation.
For a sense of what is involved, note that in [37], Section 4.1, it is proved, for
{u }>0 with u → u in L1 (D), that the following liminf inequality holds:
ση T V (u; ρ2 ) ≤ lim inf T V (u ; ρ).
→0

(6.16)

To apply (6.16) to the graph total variation, one may proceed in three steps,
analogous to the proof of Lemma 6.3, by first considering η that are normalized

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 41

indicator functions, then simple functions, and finally the general kernels satisfying
assumptions (K1) − (K4), to show
lim inf GT Vn (un ) ≥ lim inf T Vn (un ; ρ).
n→∞

(6.17)

n→∞

Combining (6.16) and (6.17) would then give the proof.



Lemma 6.6. On the probability 1 set Ω0 , the following statement holds: Given
(T L1 )K

any sequence {Vn }n∈N such that Vn −−−−−→ V, where Vn = (νn , Un ) ∈ Mn (D) and
V = (ν, U) ∈ M (D), then
T V (U) ≤ lim inf T Vn (Un ).
n→∞

w

Proof. Fix a realization in the probability 1 set Ω0 . Note that νn −
→ ν by Corollary
1

TL

3.3, and so (ν, 1) −−→ (ν, 1) by Lemma 3.1, as n → ∞. Hence, by Lemma
R 6.3, applied with α = 1 and gn ≡ 1, we have that GΛn (1) = 2m/(n(n − 1)) −
→ D ρ2 (x) dx,
as n → ∞.
PK
(T L1 )K
Recall now that T Vn (Un ) = (n(n − 1)/4m) k=1 GT Vn (un,k ). If Vn −−−−−→ V,
by Lemma 6.5, we have
ση T V (uk ; ρ) ≤ lim inf GT Vn (un,k )
n→∞

for 1 ≤ k ≤ K. It follows that
T V (U) = Cη,ρ

K
X

K

T V (uk ; ρ2 ) ≤ lim inf
n→∞

k=1

where Cη,ρ = ση /(2

n(n − 1) X
GT Vn (un,k ),
4m
k=1

2

R
D

ρ (x)dx).



Lemma 6.7. On the probability 1 set Ω0 , the following statement holds: Given
(T L1 )K

any sequence {Vn }n∈N in (T L1 (D))K and V ∈ (T L1 )K such that Vn −−−−−→ V as
n → ∞, then
E(V) ≤ lim inf En (Vn ).
n→∞

Proof. Fix a realization in the probability 1 set Ω0 . Without loss of generality,
we may assume that Vn = (νn , Un ) ∈ Mn (D), as En (Vn ) diverges otherwise. If
(T L1 )K

Vn −−−−−→ V, by Lemma 6.2, it follows that V = (ν, U) ∈ M (D). Also, by Lemmas
6.4 and 6.6, we have
T V (U) ≤ lim inf T Vn (Un ) and F (U) ≤ lim inf Fn (Un ).
n→∞

n→∞

Adding these two liminf inequalities gives E(V) ≤ lim inf En (Vn ).
n→∞



6.2.2. Existence of Recovery Sequence. The a.s. recovery sequence for (ν, U) in
M (D) will be {(νn , Un )}n∈N ⊂ Mn (D), where Un is the partition of Xn induced
by U. However, before proving this in Lemma 6.9, we first establish a preliminary
result.
Lemma 6.8. Fix u ∈ L1 (D), and let {Tn }n∈N be the transport maps given in
Proposition 3.2. Then, a.s.,
L1

u ◦ Tn −→ u as n → ∞.

42

ERIK DAVIS AND SUNDER SETHURAMAN

R
Proof. Let u be a Lipschitz function such that D |u(x) − u (x)| dx < . Let A > 0
be a lower bound for ρ on D. It follows that
Z
Z
A |u(Tn x) − u(x)| dx ≤
|u(Tn x) − u (Tn x)|ρ(x) dx
D
D
Z
Z
+ |u (Tn x) − u (x)|ρ(x) dx +
|u (x) − u(x)|ρ(x) dx. (6.18)
D

D

We rewrite the first term in the right side of (6.18) in terms of the data set Xn :
Z
n
1X
|u(Xi ) − u (Xi )|.
|u(Tn x) − u (Tn x)|ρ(x) dx =
n i=1
D
Pn
By the strong
law of large numbers, we have a.s. that limn→∞ n1 i=1 |u(Xi ) −
R
u (Xi )|= D |u(x) − u (x)|ρ(x) dx < .
For the second term in (6.18), let C be the Lipschitz constant for u . Then a.s.,
by Proposition 3.2,
Z
lim sup |u (Tn x) − u (x)|ρ(x) dx ≤ lim sup CkρkL∞ kTn − IdkL∞ = 0.
n→∞

n→∞

D

Taking limits in (6.18) therefore gives a.s. that
Z
lim sup |u(Tn x) − u(x)| dx ≤ 2A−1 .
n→∞

D

Letting  go to zero along a countable sequence establishes the lemma.



Lemma 6.9. Let V ∈ (T L1 (D))K . If V = (ν, U) ∈ M (D), let Vn = (νn , Un ) ∈
Mn (D), where Un,k = Uk ∩ Xn for 1 ≤ k ≤ K and n ≥ 1. On the other hand, if
V∈
/ M (D), let Vn = V for n ≥ 1.
Then, a.s., as n → ∞,
(T L1 )K

Vn −−−−−→ V and En (Vn ) → E(V).
Proof. In the case that V ∈
/ M (D), since the sequence {νn }n∈N is composed of
distinct elements, for all large n, V 6∈ Mn (D) and hence En (V) = E(V) = ∞.
Suppose now that V = (ν, U) ∈ M (D). In the following, we will use the fact
that un,k (x) = 1Un,k (x) = 1Uk (x) = uk (x) when x ∈ Xn . To show a.s. that
(T L1 )K

w

Vn −−−−−→ V as n → ∞, by Lemma 3.1, it is enough to show a.s. that νn −
→ν
and, for 1 ≤ k ≤ K, that
Z
Z
|un,k (Tn x) − uk (x)|dν(x) =
|uk (Tn x) − uk (x)|ρ(x)dx → 0,
(6.19)
D

D

as n → ∞, since Tn x ∈ Xn implies un,k (Tn x) = uk (Tn x).
w
The a.s. convergence νn −
→ ν follows, for instance, by Corollary 3.3. On the
other hand, the limit (6.19) follows by Lemma 6.8.
To show that a.s. En (Vn ) → E(V), we need to show that
a.s.

T Vn (Un ) −−→ T V (U)

a.s.

and Fn (Un ) −−→ F (U),

(6.20)

as n → ∞. Since condition (I2) on {n }n∈N implies condition (I1), we shall see that
these limits in fact follow from the proof of Theorem 2.1.

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 43

In particular, recall the definitions (6.2) and (6.6) of T Vn and T V respectively.
a.s.
Then, since un,k = uk on Xn , the limit T Vn (Un ) −−→ T V (U), as n → ∞, follows
from (5.40).
With regards to the Fn convergence, we consider two possibilities. First, suppose
that U is balanced. Then, recalling the definition (6.1), and again noting that
a.s.
un,k = uk on Xn , it follows from (5.41) that Fn (Un ) −−→ F (U) = 0 as n → ∞.
2
PK 
Suppose now that U is not balanced, so that k=1 µ(Uk ) − 1/K 6= 0. Then
a.s.

(5.39) implies, as n → ∞, that Fn (Un ) −−→ F (U) = ∞. Having considered all
cases, (6.20) is established.

6.3. Compactness and Proof of Theorem 2.3. After a few preliminary estimates, we supply the needed compactness property for the graph energies {En }n∈N
in Theorem 6.12. Then, we prove Theorem 2.3 at the end of the section.
Lemma 6.10. Let {un }n∈N be a sequence of indicator functions on D, un ∈ I(D),
and {n }n∈N be a sequence of positive numbers with limn→∞ n = 0. If
sup T Vn (un ; 1D ) < ∞,
n∈N

then {un }n∈N is relatively compact with respect to the L1 topology.
Proof. This result is a special case of Proposition 4.6 of [37] and Theorem 3.1
of [3], which treat more involved settings. However, for the convenience of the
reader, we present a streamlined argument in our situation, which makes use of the
assumptions that the functions {un }n∈N are {0, 1}-valued, and that the kernel η is
compactly supported.
For what follows, we extend un to all of Rd by setting un (x) = 0 for x ∈ Rn \D.
Note that
Z
ηn (x0 − x)|un (x0 ) − un (x)| dx dx0
d
d
R ×R
Z
=
ηn (x0 − x)|un (x0 ) − un (x)| dx dx0
D×D
Z
+2
ηn (x0 − x)|un (x0 ) − un (x)| dx dx0 ,
D×(Rd \D)

since |un (x0 )−un (x)| vanishes on (Rd \D)×(Rd \D). Now, as supn∈N T Vn (un ; 1D ) <
∞, it follows that there is a constant C such that
Z
ηn (x0 − x)|un (x0 ) − un (x)| dx dx0 ≤ Cn .
(6.21)
D×D

Let R be such that η(z) = 0 when |z|≥ R, and let ∂n D = {x ∈ Rd |d(x, ∂D) <
Rn } be the Rn -neighborhood of ∂D. Note that the volume of ∂n D is bounded by
Cn for some constant C. Then, by boundedness of {un }n∈N and property (K1) of
the kernel η, we have
Z
Z
ηn (x0 − x)|un (x0 ) − un (x)| dx dx0 ≤
ηn (x0 − x) dx dx0
d
d
D×(R \D)
D×(R \D)
Z
Z
0
0
0
≤
ηn (x − x) dx dx ≤
dx ≤ Cn .
(6.22)
D×∂n D

∂n D

44

ERIK DAVIS AND SUNDER SETHURAMAN

Combining (6.21) and (6.22) thus gives, in terms of another constant C, that
Z
Cn ≥
ηn (x0 − x)|un (x0 ) − un (x)| dx dx0
d
d
ZR ×R
=
ηn (y)|un (x + y) − un (x)| dx dy.
Rd ×Rd

Now, let φ : Rd → R be a non-negative, smooth, compactly supported radial
function, with φ(0) > 0, φ ≤ η, and |∇φ|≤ η. Indeed, by property
(K3), since
R
η(0) > 0 and η is continuous at zero, such a φ exists. Let c = Rd φ(x) dx ≤ 1 and
φn (x) = (cdn )−1 φ(x/n ). Define the sequence {wn }n∈N by
Z
wn (x) =
φn (y)un (x + y) dy.
Rd

We make the following observations.
(1) The sequence {wn }n∈Rd is bounded in L1 (D),
Z
Z
Z
|wn (x)| dx ≤
|wn (x)| dx ≤
|un (x)| dx ≤ vol(D),
D

Rn

Rd

as un is an indicator
R function on D, and extended by zero outside of D.
(2) We have the limit Rd |wn (x) − un (x)| dx → 0 as n → ∞. Indeed, one may
verify the inequality
Z
Z
Z
φn (y)un (x + y) dy − un (x) dx
|wn (x) − un (x)| dx =
Rd
Rd
Rd
Z
≤
φn (y)|un (x + y) − un (x)| dx dy
Rd ×Rd
Z
1
η (y)|un (x + y) − un (x)| dx dy ≤ Cn ,
≤
c Rd ×Rd n
since φn ≤ c−1 ηn and (6.21) holds.
(3) The gradient |∇wn (x)| is uniformly bounded in L1 (D). To see this, note
that
Z
Z
Z
|∇wn (x)| dx =
∇φn (y)un (x + y) dy dx
d
d
Rd
ZR ZR
=
∇φn (y)(un (x + y) − un (x)) dy dx
Rd
Rd
Z
≤
|∇φn (y)kun (x + y) − un (x)| dy dx
Rd ×Rd
Z
1
η (y)|un (x + y) − un (x)| dy dx
≤
cn Rd ×Rd n
1
≤ T Vn (un ; 1D ).
c
R
Here, the second equality follows as Rd ∇φn (y) dy = 0 because φ is compactly supported,. The third inequality follows as |∇φn |≤ (cn )−1 ηn .
R
R
Now, because supn D |wn (x)| dx < ∞ and supn D |∇wn (x)| dx < ∞, it fol1
Rlows by Theorem 3.23 of [5] that {wn }n∈N is relatively compact in L (D). Since
|wn (x) − un (x)| dx → 0, as n → ∞, it follows that the sequence {un }n∈N is also
D
relatively compact in L1 (D), with the same cluster points as {wn }n∈N .


CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 45

Recall that Ω0 denotes the probability 1 set of realizations of {Xi }i∈mathbbN
under which Proposition 3.2 holds.
Lemma 6.11. Suppose {n }n∈N satifies condition (I2). On the probability 1 set
Ω0 , the following holds: Given any sequence {un }n∈N of indicator functions on the
data points, un ∈ In (D), if
sup GT Vn (un ) < ∞,
n∈N

then {(νn , un )}n∈N is relatively compact with respect to the T L1 topology.
Proof. We begin as in the proof of Lemma 6.3. Fix a realization in the probability
1 set Ω0 . Suppose that η is of the form η(x) = a for |x|< b and η(x) = 0 for |x|> b.
∞
Let ˜n := n − 2 kId−Tbn kL , with respect to the transport maps {Tn }n∈N . Then, for
all large n, ˜n > 0, and we have the inequality (6.10),
x − y
T x − T y
n
n
η
≤η
Lebesgue a.e. (x, y) ∈ D × D
˜n
n
Let A > 0 be a lower bound for ρ on D. Then,
Z 
x − y
|un (Tn x) − un (Tn y)| dx dy
A2
η
˜n
D
Z 
x − y
≤
η
|un (Tn x) − un (Tn y)|ρ(x)ρ(y) dx dy
˜
ZD  n
Tn x − Tn y 
|un (Tn x) − un (Tn y)|ρ(x)ρ(y) dx dy
≤
η
n
D
= d+1
n GT Vn (un ).
The above inequality is equivalent to
(˜
n /n )d+1 T V˜n (un ◦ Tn ; 1D ) ≤ GT Vn (un ).
Since limn→∞ ˜n /n = 1, the bound supn GT Vn (un ) < ∞ implies that
sup T V˜n (un ◦ Tn ; 1D ) < ∞.
n

It follows, by Lemma 6.10, that the family {un ◦ Tn }n∈N is relatively compact with
w
respect to the L1 topology. Since, by Corollary 3.3, νn −
→ ν, we conclude by Lemma
3.1 that {(νn , un )}n∈N is relatively compact in T L1 .
Suppose now η is an arbitrary kernel satisfying assumptions (K1)-(K4). Since η
is continuous at zero, and η(0) > 0, there is some radius R such that η̃ = η(0)
2 1|x|<R
R
]
satisfies η̃ ≤ η. Let c = Rd η̃(x) dx. Then, if GT V n denotes the graph total
variation associated to the kernel η̃/c (instead of η), we have
]
GT Vn (un ) ≥ c GT
V n (un ).
]
Since supn GT Vn (un ) < ∞ implies supn GT
V n (un ) < ∞, it follows from our previous discussion that the sequence {(νn , un )}n∈N is relatively compact in T L1 (D). 
Theorem 6.12. Suppose {n }n∈N satisfies condition (I2). On the probability 1 set
Ω0 , the following holds: Given any sequence {Vn }n∈N ⊂ (T L1 )K , if
sup En (Vn ) < ∞,
n∈N

then {Vn }n∈N is relatively compact with respect to the (T L1 )K topology.

46

ERIK DAVIS AND SUNDER SETHURAMAN

Proof. Fix a realization in the probability 1 set Ω0 . Suppose supn En (Vn ) < ∞. By
definition of En , it follows that Vn = (νn , Un ) ∈ Mn (D) where Un = {Un,k }K
k=1 for
T L1

w

n ∈ N. By Corollary 3.3, we have νn −
→ ν. Since (νn , 1D ) −−→ R(ν, 1D ) by Lemma
3.1, we have, by Lemma 6.3, that GΛn (1) = 2m/(n(n − 1)) → D ρ2 (x)dx. Recall
now that En (Vn ) = T Vn (Un ) + Fn (Un ) and
K

T Vn (Un ) =

n(n − 1) X
GT Vn (un,k ),
4m
k=1

where un,k = 1Un,k for 1 ≤ k ≤ K. Hence, given that supn∈N En (Vn ) < ∞, we
have
sup GT Vn (un,k ) < ∞,
n∈N

for 1 ≤ k ≤ K. Thus, by Lemma 6.11, the collection {(νn , un,k )}n∈N is relatively
compact in T L1 for 1 ≤ k ≤ K. Thus, {Vn = ((νn , un,k ))K
k=1 = (νn , Un )}n∈N is
relatively compact in (T L1 )K .

Proof of Theorem 2.3. We have seen in Theorem 6.1 that
Γ((T L1 )K )

En −−−−−−−→ E,
in the sense of Definition 3.8. By Theorem 6.12, the graph energies En have the
compactness property according to Definition 3.9. Also, as noted in Subsection 6.1,
the energy E is not identically infinite.
For each realization {Xi }i∈N , consider a partition Un∗ ∈ arg max|Un |≤K Qn (Un ).
Then, by the discussion in Subsection 6.1, Un∗ is a minimizer of Fn + T Vn , and
so Vn = (νn , Un∗ ) ∈ Mn (D) is a minimizer
R of En . The sequence {Vn }n∈N is also
bounded in (T L1 )K : Indeed, we have D |x|dνn (x) ≤ supx∈D |x| and, for u∗n,k =
∗
∗
∗ , ku
1Un,k
n,k kL1 ≤ vol(D)kun,k kL∞ ≤ vol(D).
Hence, on the full set of realizations {Xi }i∈N , denoted as Ω, the sequence
xn = Vn , on the metric space (T L1 )K , satisfies the hypotheses of Theorem 3.11.
Therefore, with respect to realizations {Xi }i∈N on a probability 1 set Ω∗ , Vn converges in (T L1 )K , perhaps along a subsequence, to a limit V, which is a minimizer
of E, and is therefore of the form V = (ν, U ∗ ). Since the ‘liminf’ inequality, Lemma
w
6.7, holds on Ω0 , we note that Ω∗ ⊂ Ω0 . Moreover, by Corollary 3.3, νn −
→ ν on
Ω∗ . Therefore, by (3.4), on Ω∗ , Un∗ converges weakly, perhaps along a subsequence,
to the limit U ∗ , which isR an optimal partition of the continuum problem (2.6) with
φ = ρ2 and dµ = ρ1+α / D ρ1+α (x)dx.
In fact, we may conclude that, on Ω∗ , the distances βn := inf{d(T L1 )K (Vn , V) :
V ∈ arg min E}, where d(T L1 )K is the product metric for (T L1 )K convergence,
satisfy βn → 0 as n → ∞. For if not, there is a subsequence {nm }m∈N with
βnm → β > 0. However, by the above discussion one may find a further subsequence
{n0m }m∈N with βn0m → 0, a contradiction.
Moreover, if problem (2.6) has a unique solution U ∗ = {Uk∗ }K
k=1 , modulo permutations, then arg min E = {((ν, u∗π(k) ))K
:
π
∈
Sym(K)},
where
Sym(K) denotes
k=1
the permutations of {1, . . . , K} and u∗k = 1Uk∗ for 1 ≤ k ≤ K. Thus, on the
probability 1 set Ω∗ , since βn → 0, one may construct a sequence {πn }n∈N of
1 K
permutations such that, as n → ∞, ((νn , u∗n,πn (k) ))K
to
k=1 converges in (T L )
∗
∗ K
∗
∗
(ν, U ) = ((ν, uk ))k=1 . Hence, by (3.4), Un converges to U weakly, in the sense of
(2.11).


CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 47

7. Appendix
7.1. Approximation Lemma. Recall that we have defined ρ (x) =
y)ρ(y)dy.

R
D

η (x −

Lemma 7.1. Under the standing assumptions on ρ, D and η in Subsection 2.3,
we have the following:
(i) ρ converges pointwise to ρ as  ↓ 0.
(ii) There exists a constant C such that, for sufficiently small ,
Z
|ρ (x) − ρ(x)| dx ≤ C.

(7.1)

D

(iii) There exist constants a, b such that, for sufficiently small ,
0 < a ≤ ρ (x) ≤ b

for all x ∈ D.

Proof. The pointwise convergence in item (i) follows from continuity of ρ.
We now focus attention on item (ii), inequality (7.1). For the moment, fix x ∈ D.
Since η is compactly supported, we take
R R such that η(z) = 0 for |z|> R. Then for
0 <  < dist(x, ∂D)/R, we have, since R η(x)dx = 1, that
Z
ρ(x) =
η (z)ρ(x) dz,
x+z∈D

and so,
Z
ρ (x) − ρ(x) =

η (z)(ρ(x + z) − ρ(x)) dz.
x+z∈D

Let L be a Lipschitz constant for ρ. Then,
Z
|ρ (x) − ρ(x)| ≤ L
η (z)|z| dz
Zx+z∈D
≤L
η (z)|z| dz
|z|≤diam(D)
Z
= L
η(z)|z| dz
|z|≤diam(D)/
Z
≤ L
η(z)|z| dz.
Rd

Because

R
R

η(x)dx = 1 and η(z) = 0 for |z|> R, the above implies
|ρ (x) − ρ(x)|≤ LR.

(7.2)

Let DR = {x ∈ D | dist(x, ∂D) < R} and ∂R D = D \ DR . We split the
integral,
Z
Z
Z
|ρ (x) − ρ(x)| dx =
|ρ (x) − ρ(x)| dx +
|ρ (x) − ρ(x)| dx,
D

DR

∂R D

and consider the two terms separately.
On DR , applying inequality (7.2) yields
Z
|ρ (x) − ρ(x)| dx ≤ vol(D)LR.
DR

(7.3)

48

ERIK DAVIS AND SUNDER SETHURAMAN

For the second integral, note that because the boundary is Lipschitz, there is a
0 > 0 and constant C such that vol(∂DR ) ≤ CR for 0 <  < 0 . It follows that
Z
|ρ (x) − ρ(x)| dx ≤ 2CkρkL∞ R.
(7.4)
∂R D

Combining (7.3) and (7.4) gives, for sufficiently small  > 0,
Z
|ρ (x) − ρ(x)| dx ≤ CR,
D

where C is a constant independent of .
For item (iii) of the lemma, note that because the boundary of D is Lipschitz,
there exists constants r0 , r1 such that, for any x ∈ D and 0 < r < r1 ,
0 < r0 <

vol(D ∩ B(x, r))
,
vol(B(x, r))

where B(x, r) denotes the ball of radius r centered at x (cf. the discussion about
cone conditions in Section 4.11 of [1]).
By assumption, ρ is bounded above and below: 0 < A ≤ ρ(·) ≤ B. Also, by
assumption (K3), η is continuous at zero and η(0) > 0, so we may take r so that
0 < η(0)/2 ≤ η(z) for |z|< r. Letting η̃(x) = η(0)1B(x,r) /2vol(B(x, r)), we thus
have
Z
Z
0 < Ar0 η(0)/2 ≤ A
η̃(x − y) dy ≤
η (x − y)ρ(y) dy = ρ (x).
D

D

R

Since R η (x)dx = 1, the upper bound ρ (x) ≤ B holds. This completes the
lemma.

7.2. Estimates for GTV Limsup. Recall, from the proof
R of Lemma 5.2, that
fn (Xi , Xj ) = 1n ηn (Xi − Xj )|u(Xi ) − u(Xj )|, ln (Xi ) = 1n D ηn (Xi − y)|u(Xi ) −
R
u(y)|ρ(y) dy, and mn (Xj ) = 1n D ηn (x−Xj )|u(x)−u(Xj )|ρ(x) dx. Here, u ∈ I(D)
is such that T V (u; ρ2 ) < ∞.
Lemma 7.2. There exists a constant C such that, for sufficiently large n, we have
the following bounds:
|Efn |≤ C,

kfn kL2 →L2 ≤ C/n ,

Efn2

Eln2 ≤ C/n ,

≤

C/d+1
n ,

kEY fn2 kL∞ ≤ C/d+2
n ,

kln kL∞ ≤ C/n ,

kEX fn2 kL∞ ≤

Em2n ≤ C/n ,

C/d+2
n ,

kfn kL∞ ≤ C/d+1
n ,

kmn kL∞ ≤ C/n .

Proof. Note, by Lemma 5.1, that Efn = T Vn (u; ρ) converges to T V (u; ρ2 ) < ∞ as
n → ∞. Hence |Efn |≤ C.
For Efn2 , we have
Z Z
1
2
Efn =
(ηn (x − y))2 |u(x) − u(y)|2 ρ(x)ρ(y) dx dy.
2

D D n

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 49

Since η is bounded above, we have (ηn (x − y))2 ≤ Cηn (x − y)/dn . Because
u ∈ I(D), we have |u(x) − u(y)|2 = |u(x) − u(y)|. Hence,
Z Z
1 1
Efn2 ≤ C
η (x − y)|u(x) − u(y)|ρ(x)ρ(y) dx dy
2 d n

D D n n
≤ C T Vn (u; ρ)/d+1
≤ C 0 /d+1
n
n
Likewise, one may get the bound
Z
1
2
(ηn (x − y))2 |u(x) − u(y)|2 ρ(y) dy
EY fn =
2

D n
Z
≤C
ηn (x − y)ρ(y) dy/d+2
≤ C 0 /d+2
n
n ,
D

with the last inequality following from our assumption that ρ is bounded. By the
symmetry of fn , this also gives
EX fn2 ≤ C 0 /d+2
n .
Recall that kfn kL2 →L2 is given by
kfn kL2 →L2
Z
= sup{

fn (x, y)h(x)g(y)dν(x)dν(y) : khkL2 (D,ν) ≤ 1, kgkL2 (D,ν) ≤ 1}.

D×D

R
R
It is straightforward to show D |fn (x, y)|ρ(x) dx ≤ C/n and D |fn (x, y)|ρ(y) dy ≤
C/n , forR some constant C independent of n. Thus, with respect to the map
Jg(x) = D fn (x, y)g(y)ρ(y)dy, by Theorem 6.18 of [30], we have
kJgkL2 (D,ν) ≤ CkgkL2 (D,ν) /n ,
which implies kfn kL2 →L2 ≤ C/n .
Now considering ln , we have
Z  Z
2
1
2
ηn (x − y)|u(x) − u(y)|ρ(y) dy ρ(x) dx.
Eln =
D n D
By Jensen’s inequality, it follows that
Z
1
2
Eln ≤ 2
η (x − y)|u(x) − u(y)|2 ρ(y)ρ(x) dy dx
n D×D n
Z
1
= 2
η (x − y)|u(x) − u(y)|ρ(y)ρ(x) dy dx
n D×D n
1
≤ Efn ≤ C/n .
n
Similarly, we have
Z
1
|ln (x)| =
η (x − y)|u(x) − u(y)|ρ(y) dy
n D n
Z
1
≤
η (x − y)ρ(y) dy ≤ C/n ,
n D n
since ρ is bounded.
The same argument applied to mn gives the required inequalities.



Recall, from the proof of Lemma 5.2, that hn (Xi , Xj ) = 1n ηn (Xi − Xj )|u(Xi ) −
R
R
u(Xj )|− D fn (Xi , y)ρ(y) dy − D fn (x, Xj )ρ(x) dx + T Vn (u; ρ).

50

ERIK DAVIS AND SUNDER SETHURAMAN

Corollary 7.3. There exists a constant C, such that, for sufficiently large n, we
have the following bounds:
Eh2n ≤ C/d+1
n ,
kEY h2n kL∞ ≤ C/d+2
n ,
kEX h2n kL∞ ≤ C/d+2
n ,
khn kL∞ ≤ C/d+1
n ,
khn kL2 →L2 ≤ C/n .
Proof. Since hn (Xi , Xj ) = fn (Xi , Xj ) − ln (Xi ) − mn (Xj ) + Efn , we have
p
p
p
p
p
Eh2n ≤ Efn2 + Eln2 + En m2 + (Efn )2 .
q
All terms in the right hand side may be bounded by C/d+1
n , and hence
Eh2n ≤ C/d+1
n .
Similarly, in the bound
p
p
p
p
p
kEX h2n kL∞ ≤ kEX fn2 kL∞ + kEX ln2 kL∞ + kEX m2n kL∞ + (Efn )2 ,
q
all terms in the right hand side are dominated by C/d+2
n , and hence
kEX h2n kL∞ ≤ C/d+2
n .
By symmetry of hn , this gives
kEY h2n kL∞ ≤ C/d+2
n .
Likewise, the same triangle inequality gives
khn kL∞ ≤ C/d+1
n .
For the last bound, we consider
khn kL2 →L2 ≤ kfn kL2 →L2 +kln kL2 →L2 +kmn kL2 →L2 +|Efn |
≤ kfn kL2 →L2 +kln kL∞ +kmn kL∞ +|Efn |,
and each term in the right hand side is bounded by C/dn .

7.3. Estimates for GF Limsup. Recall, from the proof
R of Lemma 5.5, the notation fn (Xi , Xj ) = √1n ηn (Xi −Xj )u(Xj ), ln (Xi ) = √1n D ηn (Xi −y)u(Xi )ρ(y) dy,
R
and mn (Xj ) = √1n D ηn (x − Xj )u(x)ρ(x) dx. Here, u ∈ I(D).
Lemma 7.4. There exists a constant C, such that, for sufficiently large n, we have
the following bounds:
1/2

1/2

|Efn |≤ C/n ,

kfn kL2 →L2 ≤ C/n ,

Efn2 ≤ C/d+1
n ,

Eln2 ≤ C/n ,

kEY fn2 kL∞ ≤ C/d+1
n ,

kln kL∞ ≤ C/n ,

kEX fn2 kL∞ ≤ C/d+1
n ,

Em2n ≤ C/n ,

d+1/2

kfn kL∞ ≤ C/n

,

1/2

1/2

kmn kL∞ ≤ C/n .

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 51

Proof. These inequalities are easier Rthan the ones in Lemma 7.2, and follow from
the boundedness of u and ρn (x) = D ηn (x − y)ρ(y) dy.

Recall that hn (Xi , Xj ) = fn (Xi , Xj ) − ln (Xi ) − mn (Xj ) + Efn . The proof of the
following is similar to that of Corollary 7.3.
Corollary 7.5. There exists a constant C, such that, for sufficiently large n, we
have the following bounds:
Eh2n ≤ C/d+1
n ,
kEY h2n kL∞ ≤ C/d+1
n ,
kEX h2n kL∞ ≤ C/d+1
n ,
d+1/2

khn kL∞ ≤ C/n
khn kL2 →L2 ≤

,

1/2
C/n .

7.4. Transport Distance in d = 1. In this section, we provide the transport maps
{Tn }n∈N in d = 1 and establish a bound on the rate at which kId − Tn kL∞ → 0 as
n → ∞.
Recall that by assumption (M ) of Subsection 2.3, ν is a probability measure on
D = (c, d) with distribution function Fν and density ρ that is differentiable, Lipschitz, and bounded above and below by positive constants. Further, ρ is increasing
in some interval with left endpoint c and decreasing in some interval with right
endpoint d.
Given a sample Xn = {X1 , . . .P
, Xn }, we let Fn denote the distribution function
n
of the empirical measure νn = n1 i=1 υXi . We define Tn by
Tn x = Fn−1 (F x),

(7.5)

Fn−1 (t)

= inf{x ∈ R : t ≤ Fn (x)}. The map Tn is a valid transport map, i.e.
where
Tn] ν = νn .
By the assumptions on ρ, it follows that
sup Fν (x)(1 − Fν (x))|ρ0 (x)|/ρ2 (x) < ∞

(7.6)

c<x<d

It is known – see Theorem 3 on p. 650 of [71] – that when i) ρ > 0 on (c, d),
ii) inequality (7.6) is satisfied, and iii) ρ is increasing in some interval with left
endpoint c and decreasing in some interval with right endpoint d, the standardized
quantile process
√
Qn (t) := g(t) n[Fn−1 (t) − F −1 (t)],
with g(t) = ρ(F −1 (t)), satisfies, almost surely,
p
lim sup sup |Qn (t)/ 2 log log n|≤ 1.

(7.7)

n→∞ 0<t<1

Since ρ is bounded above and below by non-negative constants, so is g, and so
we have constants C, C 0 > 0 such that
√
C|Qn (t)|≤ n|Fn−1 (t) − F −1 (t)|≤ C 0 |Qn (t)|.
Since ρ is positive, F is strictly increasing, and hence we have
√
C sup |Qn (t)|≤ sup n|Fn−1 (F x) − F −1 (F x)|≤ C 0 sup |Qn (t)|.
0<t<1

c<x<d

0<t<1

52

ERIK DAVIS AND SUNDER SETHURAMAN

Recalling our definition of Tn , this may be rewritten as
√
C sup |Qn (t)|≤ nkId − Tn kL∞ ≤ C 0 sup |Qn (t)|.
0<t<1

0<t<1

In light of (7.7) and the above inequality, we obtain the following estimate.
Proposition 7.6. There is a constant C such that, almost surely, the transport
maps Tn , defined by (7.5), satisfy
√
nkId − Tn kL∞
√
≤ C.
lim
n→∞
2 log log n
Acknowledgement. This work was partially supported by ARO W911NF-14-10179.
References
[1] Adams, Robert A and Fournier, John JF (2003). Sobolev Spaces Academic Press
[2] Agarwal, Gaurav and Kempe, David (2008). Modularity-maximizing graph communities
via mathematical programming. European Physical Journal B 66, 409–418.
[3] Alberti, Giovanni and Bellettini, Giovanni (1998). A non-local anisotropic model for
phase transitions: asymptotic behaviour of rescaled energies. European Journal of Applied
Mathematics 9, 261–284.
[4] Ambrosio, Luigi, Gigli, Nicola and Savaré, Giuseppe (2005). Gradient Flows in Metric
Spaces and in the Space of Probability Measures. Birkhäuser Verlag. Basel
[5] Ambrosio, Luigi and Fusco, Nicola and Pallara, Diego (2000). Functions of Bounded
Variation and Free Discontinuity Problems Clarendon Press, Oxford.
[6] Antonioni, Alberto and Eglof, Mattia and Tomassini, Marco (2013). An energy-based
model for spatial social networks In Advances in Artificial Life ECAL 2013 pp. 226–231, MIT
Press
[7] Arias-Castro, E., and Pelletier, B. (2013). On the Convergence of Maximum Variance
Unfolding Journal of Machine Learning Research 14 1747–1770.
[8] Arias-Castro, E., Pelletier, B., Pudlo, P. (2012). The normalized graph cut and Cheeger
constant: from discrete to continuous Adv. in Appl. Probab. 44 907–937.
[9] Belkin, M. and Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and
data representation Neural Comput. 15 1373–1396.
[10] Belkin, M. and Niyogi, P. (2008). Towards a theoretical foundation for Laplacian-based
manifold methods. J. Comput. System Sci. 74 1289–1308.
[11] Bettstetter, Christian (2002). On the minimum node degree and connectivity of a wireless
multihop network. In Proceedings of the 3rd ACM International Symposium on Mobile ad
hoc Networking & Computing pp. 80–91, ACM.
[12] Bickel, P. and Chen, A. (2009). A nonparametric view of network models and NewmanGirvan and other modularities. PNAS 106 21068–21073.
[13] Blondel, Vincent D and Guillaume, Jean-Loup and Lambiotte, Renaud and Lefebvre, Etienne (2008). Fast unfolding of communities in large networks. J. Stat. Mech.: Theory
and Experiment 2008, 10008–10020.
[14] Bourgain, Jean and Brezis, Haim and Mironescu, Petru (2001). Another look at Sobolev
spaces.
[15] Braides, Andrea (2002). Gamma convergence for Beginners Oxford University Press, Oxford.
[16] Braides, A. and Gelli, M.S. (2006). From discrete systems to continuous variational problems: an introduction. In Topics on Concentration Phenomena and Problems with Multiple
Scales, Lecture Notes of the Unione Matematica Italiana 2, 3–77.
[17] Brakke, Kenneth A (1992). The surface evolver. Experimental mathematics 15, 1(2), 519–
527.
[18] Brandes, Ulrik and Delling, Daniel and Gaertler, Marco and Görke, Robert and
Hoefer, Martin and Nikoloski, Zoran and Wagner, Dorothea (2008). On modularity
clustering. IEEE Transactions on Knowledge and Data Engineering 20, 172–188.

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 53

[19] Cañete, A., Ritoré, M. (2003). Least-permiter partitions of the disk into three regions of
given areas. ArXiv preprint ArXiv: 0307207
[20] Clauset, Aaron and Newman, Mark EJ and Moore, Cristopher (2004). Finding community structure in very large networks. Phys. Rev. E 70, 066111
[21] Coiffman, R. and Lafon, S. (2006). Diffusion maps. Appl. Comput. Harmon. Anal. 21,
5–30.
[22] Cox, SJ and Flikkema, E. (2010). The minimal perimeter for N confined deformable bubbles
of equal areas. The Electronic Journal of Combinatorics 17(R45).
[23] Dávila, J (2002). On an open question about functions of bounded variation. Calculus of
Variations and Partial Differential Equations 15, 519–527.
[24] de la Peña, Victor H and Montgomery-Smith, Stephen J (1995). Decoupling inequalities
for the tail probabilities of multivariate U-statistics Annals of Probability 806–816.
[25] Dhara, M. and Shukla, K.K. (2012). Advanced cost based graph clustering algorithm for
random geometric graphs Int. J. Computer Appl. 60, 20–34.
[26] Dıaz, Josep and Penrose, Mathew D and Petit, Jordi and Serna, Marıa (2001). Approximating layout problems on random geometric graphs. J. Algorithms 39, 78–116.
[27] Dı́az, Josep and Petit, Jordi and Serna, Maria (2002). A survey of graph layout problems.
ACM Computing Surveys 34, 313–356.
[28] Dudley, R.M. (2004) Real Analysis and Probability Cambridge University Press, Cambridge.
[29] Durrett, R. (2010) Probability: Theory and Examples 4th Ed. Cambridge University Press,
Cambridge.
[30] Folland, Gerald B (2013). Real analysis: Modern Techniques and Their Applications John
Wiley & Sons
[31] Fortuna, Miguel A and Stouffer, Daniel B and Olesen, Jens M and Jordano, Pedro
and Mouillot, David and Krasnov, Boris R and Poulin, Robert and Bascompte,
Jordi (2010). Nestedness versus modularity in ecological networks: two sides of the same
coin? Journal of Animal Ecology 79, 811–817.
[32] Fortunato, S. and Barthélemy, M. (2006). Resolution limit in community detection.
PNAS 104 36–41.
[33] Fortunato, S. (2010). Community detection in graphs Physics Reports 486 75–174.
[34] Franceschetti, M. and Meester, R. (2007). Random Networks for Communication: From
Statistical Physics to Information Systems. Cambridge University Press, Cambridge.
[35] Gamal, A El and Mammen, James and Prabhakar, Bharat and Shah, Devavrat (2004).
Throughput-delay trade-off in wireless networks. In Twenty-third Annual Joint Conference
Proceedings of the IEEE Computer and Communications Societies
[36] Garcı́a Trillos, Nicolás and Slepčev, Dejan (2015). On the rate of convergence of empirical measures in ∞-transportation distance. Canadian Journal of Mathematics 67 1358–1383
[37] Garcı́a Trillos, Nicolás and Slepčev, Dejan (2016). Continuum limit of total variation
on point clouds. Archive for Rational Mechanics and Analysis 220 193–241.
[38] Garcı́a Trillos, Nicolás and Slepčev, Dejan (2015). A variational approach to the consistency of spectral clustering arXiv preprint arXiv:1508.01928
[39] Garcı́a Trillos, Nicolás and Slepčev, Dejan, and von Brecht, James and Laurent,
Thomas and Bresson, Xavier (2014). Consistency of Cheeger and Ratio Graph Cuts. arXiv
preprint arXiv:1411.6590
[40] Giné, E. and Koltchinski, V. (2006). Empirical graph Laplacian approximation of LaplaceBeltrami operators: large sample results In High dimensional probability 51 238–259. IMS
Lecture Notes Monogr. Ser., Inst. Math. Statist., Beachwood, OH
[41] Giné, Evarist and Latala, Rafal and Zinn, Joel (2000). Exponential and moment inequalities for U-statistics In High Dimensional Probability II pp. 13–38, Springer.
[42] van Gennip, Y. and Bertozzi, A. (2012). Gamma convergence of graph Ginzburg-Landau
functionals Advances in Differential Equations 17 1115–1180.
[43] Good, Benjamin H and de Montjoye, Yves-Alexandre and Clauset, Aaron (2010).
Performance of modularity maximization in practical contexts Phys. Rev. E 81, 046106
[44] Guimera, Roger and Amaral, Luis A Nunes (2005). Functional cartography of complex
metabolic networks Nature 433, 895–900.
[45] Guimera, Roger and Sales-Pardo, Marta and Amaral, Luı́s A Nunes (2004). Modularity from fluctuations in random graphs and complex networks. Phys. Rev. E 70, 025101.

54

ERIK DAVIS AND SUNDER SETHURAMAN

[46] Gupta, Piyush and Kumar, Panganmala R (2000). The capacity of wireless networks.
IEEE Transactions on Information Theory 46, 288–404.
[47] Hagmann, Patric and Cammoun, Leila and Gigandet, Xavier and Meuli, Reto and
Honey, Christopher J and Wedeen, Van J and Sporns, Olaf (2008). Mapping the structural core of human cerebral cortex. PLoS Biol 6, e159
[48] Hartigan, J.A. (1981). Consistency of Single Linkage for High-Density Clusters Journal of
the American Statistical Association 76 388–394.
[49] Hein, M., Audibert, J.-Y., Von Luxburg, U. ( 2005). From graphs to manifolds-weak and
strong pointwise consistency of graph Laplacians In Learning Theory 470–485, Springer
[50] Hu, H., Laurent, T., Porter, M., Bertozzi, A. (2013). A Method Based on Total Variation
for Network Modularity Optimization using the MBO Scheme SIAM J. Appl. Math. 73 2224–
2246.
[51] Lancichinetti, Andrea and Fortunato, Santo (2011). Limits of modularity maximization
in community detection. Phys. Rev. E 84, 066122
[52] Le, C., Levina, E., and Vershynin, R. (2016). Optimization via low-rank approximation
for community detection in networks. Ann. Stat. 44 373–400.
[53] Medus, A and Acuna, G and Dorso, CO (2005). Detection of community structures in
networks via global optimization Physica A: Statistical Mechanics and its Applications 358,
593–604.
[54] Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge University Press,
Cambridge.
[55] Mill, Jonathan and Tang, Thomas and Kaminsky, Zachary and Khare, Tarang and
Yazdanpanah, Simin and Bouchard, Luigi and Jia, Peixin and Assadzadeh, Abbas and
Flanagan, James and Schumacher, Axel and others (2008). Epigenomic profiling reveals
DNA-methylation changes associated with major psychosis The American Journal of Human
Genetics, 82, 696–711.
[56] Morgan, F. (2008). Geometric Measure Theory. A Beginner’s Guide 4th Ed. Academic
Press. New York.
[57] Newman, Mark EJ (2006). Modularity and community structure in networks PNAS 103,
8577–8582.
[58] Newman, Mark EJ (2006). Finding community structure in networks using the eigenvectors
of matrices. Phys. Rev. E 74, 036104
[59] Newman, Mark EJ (2013). Spectral methods for community detection and graph partitioning. Phys. Rev. E 88, 042822
[60] Newman, Mark EJ and Girvan, Michelle (2004). Finding and evaluating community
structure in networks Phys. Rev. E 69, 026113
[61] Oudet, E. (2011). Approximation of partitions of least permiter by Γ-convergence: Around
Kelvin’s conjecture. Experimental Mathematics 20 260–270.
[62] Penrose, Mathew (2003). Random geometric graphs Oxford University Press, Oxford
[63] Pollard, David (1981). Strong consistency of k-means clustering Annals of Statistics 9,
135–140.
[64] Ponce, Augusto (2004). A new approach to Sobolev spaces and connections to-convergence
Calculus of Variations and Partial Differential Equations 19, 229-255.
[65] Porter, Mason A and Mucha, Peter J and Newman, Mark EJ and Warmbrand, Casey
M (2005). A network analysis of committees in the US House of Representatives. PNAS 102,
7057–7062
[66] Porter, M., Onnela, J.P., Mucha, P. (2009). Communities in networks. Notices of the
AMS 56 1082–1097.
[67] Pržulj, Natasa and Corneil, Derek G and Jurisica, Igor (2004). Modeling interactome:
scale-free or geometric? Bioinformatics 20, 3508–3515.
[68] Reichardt, Jörg and Bornholdt, Stefan (2006). Statistical mechanics of community
detection. Phys. Rev. E 74, 016110
[69] Rohe, Karl, Chatterjee, Sourav, and Yu, Bin (2011). Spectral clustering and the highdimensional stochastic blockmodel. Ann. Stat. 39 1878–1915.
[70] Sabin, Michael (1987). Convergence and Consistency of Fuzzy c-means/ISODATA Algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence 9 661–668.
[71] Shorack, Galen R and Wellner, Jon A (2009). Empirical processes with applications to
statistics SIAM, Philadelphia.

CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS 55

[72] Singer, A. (2006). From graph to manifold Laplacian: The convergence rate Appl. Comput.
Harmon. Anal. 21 128–134.
[73] Singer, A. and Wu, H.T. (2015). Spectral Convergence of the connection Laplacian from
random samples arXiv preprint. arXiv:1306.1587
[74] Thorpe, M., Theil, F., Johansen, P., Cade, N. (2015). Convergence of the k-Means minimization problem using Γ-convergence arXiv preprint arXiv: 1501.01320v2
[75] Ting, D., Huang, L., and Jordan, M.I. (2010). An analysis of the convergence of graph
Laplacians In Proceedings of the 27th International Conference on Machine Learning.
[76] Van der Vaart, Aad W (2000). Asymptotic statistics Cambridge University Press, Cambridge.
[77] Villani, Cédric (2004). Topics in Optimal Transportation. American Mathematical Society,
Providence
[78] Villani, Cédric (2009). Optimal Transport Old and New. Springer Verlag, Berlin
[79] Von Luxburg, Ulrike and Belkin, Mikhail and Bousquet, Olivier (2008). Consistency
of spectral clustering Annals of Statistics 555-586.
[80] Wets, Roger (1999). Statistical estimation from an optimization viewpoint. Annals of Operations Research 85 79-102.
[81] Zhao, Y., Levina, E. and Zhu, J. (2012). Consistency of community detection in networks
under degree-corrected stochastic block models. Ann. Statist. 40 2266-2292.
Department of Mathematics, University of Arizona, Tucson, AZ 85721
e-mail: edavis@math.arizona.edu
Department of Mathematics, University of Arizona, Tucson, AZ 85721
e-mail: sethuram@math.arizona.edu

