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. We investigate the spectra of random geometric graphs (RGGs), which are prototypical examples of networks with strong correlations and describe networks whose nodes have a random physical location and are connected to other nodes that are within a threshold distance. 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 find that the number of eigenvalues in each separated peak depends on the dimension and boundary conditions of the embedding space of the RGG. Partly because of the bounds it places on connectivity, the smallest nonzero eigenvalue, or algebraic connectivity, is of particular interest. We find that in the regime of separation, the algebraic connectivity varies as a power of the average degree. This power depends on the dimension of the embedding space.