Graduate School and Research Center in Digital Sciences

Spectral analysis of the adjacency Matrix of random geometric graphs

Hamidouche, Mounia; Cottatellucci, Laura; Avrachenkov, Konstantin

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.

Document Doi Arxiv Hal Bibtex

Title:Spectral analysis of the adjacency Matrix of random geometric graphs
Keywords:Random geometric graphs, adjacency matrix, limiting eigenvalue distribution, Levy distance
Type:Conference
Language:English
City:Urbana-Champaign
Country:UNITED STATES
Date:
Department:Communication systems
Eurecom ref:6049
Copyright: Allerton
Bibtex: @inproceedings{EURECOM+6049, doi = {http://dx.doi.org/10.1109/ALLERTON.2019.8919798}, year = {2019}, title = {{S}pectral analysis of the adjacency {M}atrix of random geometric graphs}, author = {{H}amidouche, {M}ounia and {C}ottatellucci, {L}aura and {A}vrachenkov, {K}onstantin}, booktitle = {{ALLERTON} 2019, 57th {A}nnual {A}llerton {C}onference on {C}ommunication, {C}ontrol, and {C}omputing, 25-27 {S}eptember 2019, {U}rbana-{C}hampaign, {USA}}, address = {{U}rbana-{C}hampaign, {UNITED} {STATES}}, month = {09}, url = {http://www.eurecom.fr/publication/6049} }
See also: