Latent Distance Estimation for Random Geometric Graphs

2019/09/15 by Ernesto Araya, Yohann de Castro, Araya, Ernesto +1 · 2 citations
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Point processes and geometric inequalities #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1909.06841

Abstract

Random geometric graphs are a popular choice for a latent points generative model for networks. Their definition is based on a sample of n points X₁,X₂,⋯,X_n on the Euclidean sphere~\mathbbS^d-1 which represents the latent positions of nodes of the network. The connection probabilities between the nodes are determined by an unknown function (referred to as the "link" function) evaluated at the distance between the latent points. We introduce a spectral estimator of the pairwise distance between latent points and we prove that its rate of convergence is the same as the nonparametric estimation of a function on \mathbbS^d-1, up to a logarithmic factor. In addition, we provide an efficient spectral algorithm to compute this estimator without any knowledge on the nonparametric link function. As a byproduct, our method can also consistently estimate the dimension d of the latent space.

Cited by

• Recovery of latent inner products from an anisotropic Gaussian random geometric graph
• Entropic Optimal Transport in Random Graphs

Related

• On the Estimation of Latent Distances Using Graph Distances
• Random Geometric Graphs on Euclidean Balls
• Reconstructing the Geometry of Random Geometric Graphs
• Typical distances in a geometric model for complex networks
• Minimax rates for latent position estimation in the generalized random dot product graph