## Abstract

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_{n} = {X_{1},X_{2},...,X_{n}}, distributed according to a probability measure ν supported on a bounded domain D ⊂ R^{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_{n} 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.

Original language | English (US) |
---|---|

Pages (from-to) | 2003-2062 |

Number of pages | 60 |

Journal | Annals of Applied Probability |

Volume | 28 |

Issue number | 4 |

DOIs | |

State | Published - Aug 2018 |

## Keywords

- Community detection
- Consistency
- Gamma convergence
- Kelvin’s problem
- Modularity
- Optimal transport
- Perimeter
- Random geometric graph
- Scaling limit
- Shape optimization
- Total variation

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty