Consistency of modularity clustering on random geometric graphs
| Autor: | Erik Davis, Sunder Sethuraman |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Statistics and Probability
Vertex (graph theory) 05C82 68R10 Modularity Mathematics - Statistics Theory 60D05 62G20 05C82 49J55 49J45 68R10 Statistics Theory (math.ST) random geometric graph 01 natural sciences Combinatorics 010104 statistics & probability Kelvin’s problem Gamma convergence FOS: Mathematics community detection Partition (number theory) 49J45 Continuum (set theory) scaling limit 0101 mathematics 60D05 Random geometric graph Mathematics - Optimization and Control 62G20 Mathematics Probability measure Modularity (networks) consistency Probability (math.PR) 010102 general mathematics perimeter Scaling limit total variation optimal transport Optimization and Control (math.OC) Bounded function shape optimization 49J55 Statistics Probability and Uncertainty Mathematics - Probability |
| Zdroj: | Ann. Appl. Probab. 28, no. 4 (2018), 2003-2062 |
| Popis: | We consider a large class of random geometric graphs constructed from samples $\mathcal{X}_n = \{X_1,X_2,\ldots,X_n\}$ of independent, identically distributed observations of an underlying probability measure $\nu$ on a bounded domain $D\subset \mathbb{R}^d$. The popular `modularity' clustering method specifies a partition $\mathcal{U}_n$ of the set $\mathcal{X}_n$ as the solution of an optimization problem. In this paper, under conditions on $\nu$ 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 $\mathcal{U}_n$ converge in a certain sense to a continuum partition $\mathcal{U}$ of the underlying domain $D$, characterized as the solution of a type of Kelvin's shape optimization problem. Comment: 4 figures, 55 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|