The Laplacian Spectra of Random Geometric Graphs

dc.contributor.advisorBassler, Kevin E.
dc.contributor.committeeMemberJosić, Krešimir
dc.contributor.committeeMemberOrdonez, Carlos
dc.contributor.committeeMemberReiter, George F.
dc.creatorNyberg, Amy 1975- 2014 2014
dc.description.abstractIn 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.
dc.description.departmentPhysics, Department of
dc.format.digitalOriginborn digital
dc.rightsThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).
dc.subjectComplex networks
dc.subjectSpatial networks
dc.subjectRandom geometric graphs
dc.subjectGraph Laplacian
dc.subjectEigenvalue spectra
dc.subjectAlgebraic connectivity
dc.subjectEigenvalue separation
dc.titleThe Laplacian Spectra of Random Geometric Graphs
dc.type.genreThesis of Natural Sciences and Mathematics, Department of of Houston of Philosophy


Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
1.86 MB
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
1.81 KB
Plain Text