ALLERTON 2019, 57th Annual Allerton Conference on Communication, Control, and Computing, 25-27 September 2019, Urbana-Champaign, USA
We analyze the limiting eigenvalue distribution (LED) of random geometric graphs (RGGs) in two different regimes. The RGG is constructed by uniformly distributing n nodes on the d-dimensional torus mathbb^d equiv [0, 1]^d, and connecting two nodes if their ell_-distance, p in [1, infty] is at most r_. We study the LED of the adjacency matrix for RGGs in a large class of the connectivity regime in which the average vertex degree scales as logleft( nright) or faster, i.e., Omega left(log(n) right). Additionally, we analyze the LED of normalized adjacency matrices in the thermodynamic regime in which the average vertex degree tends to a constant. In the connectivity regime, under some conditions on r_, we show that the LED of the adjacency matrix of RGGs converges to the LED of the adjacency matrix of a deterministic geometric graph with nodes in a grid (DGG) as n goes to infinity. In the thermodynamic regime, we propose an approximation for the LED of the adjacency matrix normalized by the squared average degree. Then, we upper bound the Levy distance between this approximation and the actual distribution. Based on the structure of the DGG, we provide an explicit expression for the eigenvalues in both the connectivity and the thermodynamic regimes.
Type:
Conference
City:
Urbana-Champaign
Date:
2019-09-25
Department:
Communication systems
Eurecom Ref:
6049
Copyright:
Allerton
See also:
