The Laplacian Spectra of Random Geometric Graphs

In this dissertation we study a problem in mathematical physics concerning the eigenvalues of random matrices. A network may be represented by any of several matrices whose set of eigenvalues is the network's spectrum, and can act as a tool in understanding a network's topological and dynamical characteristics. We focus on the spectrum of the graph Laplacian, which is the discretization of the continuous Laplace operator and naturally arises in diffusion and synchronization problems on networks. As a prototypical simple example of spatial networks, we study the ensemble-averaged spectra of random geometric graphs (RGGs) and find that the spectra consist of both a discrete and continuous part. The discrete part, a collection of Dirac delta peaks at integer eigenvalues, does not appear in the spectra of non-spatial graphs and is a direct result of the topology specific to an RGG. We identify two types of mesoscopic symmetric structures that produce integer eigenvalues whose corresponding eigenvectors are exactly localized on the motif and analytically calculate the expected contribution of these motifs to the spectrum of 1d RGGs. Symmetric motifs are of particular interest because the localized eigenvectors imply that mesoscale structures can exist whose dynamics are mostly independent of the embedding network. The continuous part of the spectrum contains groups of eigenvalues that separate from the bulk. We show that the number that separate off together can be deduced by approximating the graph Laplacian with the continuous Laplace operator. Contained within the first separated peak is the smallest nonzero eigenvalue, or algebraic connectivity, whose value is directly related to a network's attack tolerance. We show that the algebraic connectivity varies as a dimensionally dependent power of the average degree. Additionally, we examine the behavior of eigenvalue separation for large N in several scaling regimes and identify a transition, above which separation is lost, but below which separation remains. The elimination of gaps in the spectrum is significant because it implies a smoother path towards synchronization or consensus formation on a network. Also, an approximation for the expected number of separated peaks is given.Physics, Department o