Eigenvalue Separation in the Laplacian Spectra of Random Geometric Graphs

The graph Laplacian spectra of networks are important for characterizing both their structural and dynamical properties. As a prototypical example of networks with strong correlations, we investigate the spectra of random geometric graphs (RGGs), which describe networks whose nodes have a random physical location and are connected to other nodes within a threshold distance $r$. RGGs model transportation grids, wireless networks, and biological processes. The spectrum consists of two parts, a discrete part consisting of a collection of integer valued delta function peaks centered about the average degree and a continuous part that exhibits the phenomenon of eigenvalue separation. We examine the behavior of eigenvalue separation for large network size $N$ in several scaling regimes based on the parameter $\alpha$ such that $N^{\alpha}r=c$ is constant. We identify a transition at $\alpha=1/3$, above which the separated peaks get closer together as $N$ increases and separation is eventually lost, but below which the peaks get farther apart. Also, an approximation for the expected number of separated peaks is given in terms of $N$ and the average degree and we show that the expected number of peaks scales as $N^{\alpha}$.