Consistency of modularity clustering on random geometric graphs

DOI10.1214/17-AAP1313zbMath1402.60016arXiv1604.03993MaRDI QIDQ1617118

Erik Davis, Sunder Sethuraman

Publication date: 7 November 2018

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.03993

zbMATH Keywords

total variationconsistencyscaling limitshape optimizationmodularityperimeteroptimal transportrandom geometric graphcommunity detectiongamma convergenceKelvin's problem

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Geometric probability and stochastic geometry (60D05) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Methods involving semicontinuity and convergence; relaxation (49J45)

Related Items (6)

Large data limit for a phase transition model with the p-Laplacian on point clouds ⋮ Optimal Cheeger cuts and bisections of random geometric graphs ⋮ Consistency of Dirichlet Partitions ⋮ Rates of convergence for Laplacian semi-supervised learning with low labeling rates ⋮ Analysis of $p$-Laplacian Regularization in Semisupervised Learning ⋮ On the rate of convergence of empirical measure in $\infty $-Wasserstein distance for unbounded density function

Uses Software

• Surface Evolver

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Continuum limit of total variation on point clouds
• Spectral clustering and the high-dimensional stochastic blockmodel
• Towards a theoretical foundation for Laplacian-based manifold methods
• The minimal perimeter for \(N\) confined deformable bubbles of equal area
• Asymptotic expansions by \(\Gamma \)-convergence
• Strong consistency of k-means clustering
• Statistical estimation from an optimization viewpoint
• Decoupling inequalities for the tail probabilities of multivariate \(U\)- statistics
• \(\Gamma\)-convergence of graph Ginzburg-Landau functionals
• Consistency of community detection in networks under degree-corrected stochastic block models
• Consistency of spectral clustering
• Diffusion maps
• From graph to manifold Laplacian: the convergence rate
• Approximating Layout Problems on Random Geometric Graphs
• Consistency of Cheeger and Ratio Graph Cuts
• A nonparametric view of network models and Newman–Girvan and other modularities
• Empirical Processes with Applications to Statistics
• Convergence of the $k$-Means Minimization Problem using $\Gamma$-Convergence
• On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
• Optimal Throughput–Delay Scaling in Wireless Networks—Part II: Constant-Size Packets
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Communities in Networks
• Convergence and Consistency of Fuzzy c-means/ISODATA Algorithms
• Consistency of Single Linkage for High-Density Clusters
• Asymptotic Statistics
• A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies
• Random Geometric Graphs
• The capacity of wireless networks
• Spectral convergence of the connection Laplacian from random samples
• Real Analysis and Probability
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Least-perimeter partitions of the disk into three regions of given areas
• Continuum Percolation
• The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous
• Approximation of Partitions of Least Perimeter by Γ-Convergence: Around Kelvin’s Conjecture
• Fast unfolding of communities in large networks
• The Surface Evolver
• A Method Based on Total Variation for Network Modularity Optimization Using the MBO Scheme
• Random Networks for Communication
• Learning Theory
• Probability
• Optimal Transport
• Optimization via low-rank approximation for community detection in networks

This page was built for publication: Consistency of modularity clustering on random geometric graphs