Eigenvalue Spectra of Random Geometric Graphs

The spectra of the adjacency matrix and the graph Laplacian of networks are important for characterizing both their structural and dynamical properties. We investigate both spectra of random geometric graphs, which describe networks whose nodes have a random physical location and are connected to other nodes that are within a threshold distance. Random geometric graphs model transportation grids, wireless networks, as well as biological processes. Using numerical and analytical methods we investigate the dependence of the spectra on the connectivity threshold. As a function of the number of nodes we consider cases where the average degree is held constant and where the connectivity threshold is kept at a fixed multiple of the critical radius for which the graph is almost surely connected. We find that there exists an eigenvalue separation phenomenon causing the distribution to change form as the graph moves from well connected to sparsely connected. For example, the Laplacian spectra of well connected graphs exhibit a Gaussian envelope of integer values centered about the mean connectivity and superimposed on a real valued distribution. As connectivity decreases, the distribution shifts and includes an accumulation of eigenvalues near zero.