A1069
Title: Community detection via curvature gaps
Authors: Chang Li - University of Virginia (United States) [presenting]
Zachary Lubberts - University of Virginia (United States)
Melanie Weber - Harvard University (United States)
Yu Tian - Max Planck Institute for Physics of Complex Systems (Germany)
Abstract: The clustering problem is considered in stochastic blockmodel graphs from the perspective of Ollivier's Ricci Curvature, an extension of Ricci Curvature on manifolds to this discrete setting. The gap between the distributions of edge curvatures for within-cluster edges and between-cluster edges allows identifying these two groups of edges by their curvature, guaranteeing effective clustering. This curvature gap is studied under multiple signal strength regimes, identifying its limiting distribution and exploring the limits of curvature-based clustering. These distributional limits for edge curvatures are the first of their kind in the literature, and show that curvature-based clustering can be an effective competitor to traditional clustering methods, even in low signal strength settings.
