On the Normalized Laplacian Spectra of Random Geometric Graphs

[PDF]

Abstract

In this work, we study the spectrum of the normalized Laplacian and its regularized version for random geometric graphs (RGGs) in different scaling regimes. We consider $n$ nodes distributed uniformly and independently on the $d-$dimensional torus $\mathbf{T} \sim [0, 1]^d$ and form an RGG by connecting two nodes when their $p-$distance, $1 \leq p \leq \infty$, does not exceed a certain threshold $r_n$. Two scaling regimes for are of special interest. One of these is the connectivity regime, in which the average vertex degree grows logarithmically in $n$. The second scaling regime is the thermodynamic regime, in which the average vertex degree is a constant. When $d$ is fixed and , we prove that the limiting eigenvalue distribution (LED) of the normalized Laplacian matrix of RGGs converges to the Dirac distribution at one in the full range of the connectivity regime. In the thermodynamic regime, we propose an approximation for the LED and we provide a bound on the Levy distance between this approximation and the actual distribution. In particular, we show that the LED of the regularized normalized Laplacian matrix of an RGG can be approximated by the LED of the regularized normalized Laplacian of a deterministic geometric graph with nodes in a grid (DGG).