Consistency of modularity clustering on random geometric graphs

Given a graph, the popular “modularity” clustering method specifies a partition of the vertex set as the solution of a certain optimization problem. In this paper, we discuss scaling limits of this method with respect to random geometric graphs constructed from i.i.d. points Xₙ=₁,X₂,…,Xₙ\, distributed according to a probability measure ν supported on a bounded domain Dᵈ. Among other results, we show, via a Gamma convergence framework, a geometric form of consistency: When the number of clusters, or partitioning sets of Xₙ is a priori bounded above, the discrete optimal modularity clusterings converge in a specific sense to a continuum partition of the underlying domain D, characterized as the solution to a “soap bubble” or “Kelvin”-type shape optimization problem.