Spectral analysis of random geometric graphs

In this thesis we study random geometric graphs (RGGs) using tools from random matrix theory and probability theory to tackle key problems in complex networks. An RGG is constructed by uniformly distributing n nodes on the d-dimensional torus Td  [0; 1]d and connecting two nodes if their `p-distance, with p 2 [1;1] is at most rn. Three relevant scaling regimes for the RGG are of special interest. One of these is the connectivity regime, in which the average vertex degree an grows logarithmically with n or faster, i.e., an =(log(n)). The second scaling regime is the dense regime, in which an  (n). The third scaling regime is the thermodynamic regime, in which the average vertex degree is a constant. First, when d is xed and n ! 1, we study the spectrum of the normalized Laplacian matrix and its regularized version for RGGs in both the connectivity and thermodynamic regime. We propose an approximation for the RGG regularized normalized Laplacian matrix based on the deterministic geometric graph (DGG) with nodes in a grid. Then, we provide an upper bound for the probability that the Hilbert-Schmidt norm of the difference between the RGG and the deterministic geometric graph (DGG) normalized Laplacian matrices is greater than a certain threshold in both the connectivity and thermodynamic regime. In particular, in the connectivity regime, we prove that the normalized Laplacian matrices of the RGG and the DGG are asymptotically equivalent with high probability. Then, when n ! 1, we show that the limiting spectral distributions (LSDs) of the normalized Laplacian matrices of RGGs and DGGs converge in probability to the Dirac distribution at one in the full range of the connectivity regime. In the thermodynamic regime, we show that the LSD of the RGG regularized normalized Laplacian matrix can be approximated by the one in the DGG and we provide an upper bound for the approximation error which is valid with high probability. Therefore, we can use the deterministic structure of the DGG to provide an analytical expression for the eigenvalues of the RGG in both the connectivity and thermodynamic regime. Next, we study the spectrum of the adjacency matrix of an RGG in the connectivity regime. Under some conditions on the average vertex degree an, we show that the Hilbert-Schmidt norm of the difference between two sequences of adjacency matrices of RGGs and DGGs converges in probability to zero as n ! 1. Then, using this result, we show that the Levy distance between the eigenvalue distributions of the DGG and RGG adjacency matrices vanishes with high probability as n ! 1. Then, for n nite, we use the structure of the DGG to approximate the eigenvalues of the adjacency matrix of the RGG. Finally, we tackle the problem of determining the spectral dimension (SD) ds, that characterizes the return time distribution of a random walk (RW) on RGGs. First, we show that the SD depends on the eigenvalue density (ED) of the RGG normalized Laplacian in the neighborhood of the minimum eigenvalues. We show that the smallest non zero eigenvalue converges to zero in the large graph limit. Then, based on the analytical expression of the normalized Laplacian eigenvalues around zero, we show that the ED in a neighborhood of the minimum value follows a power-law tail. Therefore, using these results, we approximate the SD of RGGs by the Euclidean dimension d in the thermodynamic regime.