Spectral Analysis of the Adjacency Matrix of Random Geometric Graphs

Abstract : In this article, we analyze the limiting eigen-value distribution (LED) of random geometric graphs (RGGs). The RGG is constructed by uniformly distributing n nodes on the d-dimensional torus T and connecting two nodes if their p-distance, p in [1, ∞] is at most r. In particular, we study the LED of the adjacency matrix of RGGs in the connectivity regime, in which the average vertex degree scales as log(n) or faster, i.e., Ω (log(n)). In the connectivity regime and under some conditions on the radius 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 (DGG) with nodes in a grid as n goes to infinity. Then, for n finite, we use the structure of the DGG to approximate the eigenvalues of the adjacency matrix of the RGG and provide an upper bound for the approximation error.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-02416590
Contributor : Konstantin Avrachenkov <>
Submitted on : Tuesday, December 17, 2019 - 5:20:05 PM
Last modification on : Wednesday, December 18, 2019 - 1:33:15 AM

File

Spectra-Adjacency matrix.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Mounia Hamidouche, Laura Cottatellucci, Konstantin Avrachenkov. Spectral Analysis of the Adjacency Matrix of Random Geometric Graphs. Allerton 2019 - 57th Annual Allerton Conference on Communication, Control, and Computing, Sep 2019, Monticello, United States. pp.208-214, ⟨10.1109/ALLERTON.2019.8919798⟩. ⟨hal-02416590⟩

Share

Metrics

Record views

24

Files downloads

24