Geometry of Random Graphs

Abstract

Random graphs are canonical models for network data in various disciplines,including information technology, social studies, artificial intelligence, and biological sciences. These real-world networks are usually associated with some explicit or implicit geometric structure. As a first step towards understanding them, it is crucial to know how the geometry is reflected in the combinatorial structure. To this end, we study random graphs with latent geometry.In particular, we focus on models where the edges are stochastically determined by unobserved random positions. First, we introduce the noisy high-dimensional random geometric graph that is an interpolation between the Erdős–Rényi model and the random geometric graph with a parameter controlling the signal strength of geometry in the edges, and therefore the level of noise. We show that there exists a phase transition driven by the dimension of the latent space and the noise parameter in this model: The geometry is lost in a certain regime, while it can be detected in some other. The proof for losing geometry utilizes information-theoretic inequalities with several improved estimates over previous results. Detecting geometry is proved by analyzing a computationally efficient signed triangle statistic. Second, we consider soft random dot product graphs equipped with general smooth connection functions, and provide an alternative view of the softness as noise in the geometric graph. A natural parameter under this setting is the variance of the noise distribution. Similarly, we show a phase transition phenomenon in this family of random graphs. The proof is based on a second moment method and makes use of tools including Stein's lemma and Gaussian hypercontractivity. In both cases, a trade-off between dimensionality and noise in the phase transition emerges: The dimension threshold for losing geometry can be much lower with the presence of noise. Last, for expository purposes, we study the dimension estimation problem for special cases of both setups. It is shown that the dimension of the latent space can be estimated precisely in certain regimes of the dimension and the noise parameter.