Ecole d'ingénieur et centre de recherche en Sciences du numérique

Spectral bounds of the regularized normalized Laplacian for random geometric graphs

Hamidouche, Mounia; Cottatellucci, Laura; Avrachenkov, Konstantin

GSP 2019, 4th Graph Signal Processing Workshop, June 5-7th, 2019, Minnesota, Minneapolis, USA

In this work, we study the spectrum of the regularized normalized Laplacian for random geometric graphs (RGGs) in both the connectivity and thermodynamic regimes. We prove that the limiting eigenvalue distribution (LED) of the normalized Laplacian matrix for an RGG converges to the Dirac measure in one in the full range of the connectivity regime. In the thermodynamic regime, we propose an approximation for the LED and we provide a bound on the Levy distance between the approximation and the actual distribution. In particular, we show that the LED of the regularized normalized Laplacian matrix for an RGG can be approximated by the LED of the regularized normalized Laplacian for a deterministic geometric graph with nodes in a grid (DGG). Thereby, we obtain an explicit approximation of the eigenvalues in the thermodynamic regime.

Document Arxiv Bibtex

Titre:Spectral bounds of the regularized normalized Laplacian for random geometric graphs
Département:Systèmes de Communication
Eurecom ref:6048
Copyright: © 2019 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+6048, year = {2019}, title = {{S}pectral bounds of the regularized normalized {L}aplacian for random geometric graphs}, author = {{H}amidouche, {M}ounia and {C}ottatellucci, {L}aura and {A}vrachenkov, {K}onstantin}, booktitle = {{GSP} 2019, 4th {G}raph {S}ignal {P}rocessing {W}orkshop, {J}une 5-7th, 2019, {M}innesota, {M}inneapolis, {USA}}, address = {{M}innesota, {\'{E}}{TATS}-{UNIS}}, month = {06}, url = {} }
Voir aussi: