Detection and recovery of latent geometry in random graphs (Online)

Abstract

In recent years, random graph models with latent geometric structures have received increasing attention. These models typically involve sampling random points from a metric space, followed by independently adding edges with probabilities that depend on the distances between corresponding point pairs. A central computational challenge is to detect the underlying geometry and recover the latent coordinates of the vertices based solely on the observed graph. Unlike classical random graph models, geometric models exhibit richer structural properties, such as correlations between edges. These features make them more realistic representations of real world networks and data. However, our current understanding of the information-theoretic and computational thresholds for detection in these models remains limited. In this talk, we will survey known algorithmic results and computational hardness findings for several random geometric graph models. We will also highlight open directions for future research.