On the Normalized Laplacian Spectra of Random Geometric Graphs

Mounia Hamidouche (), Laura Cottatellucci () and Konstantin Avrachenkov ()
Additional contact information
Mounia Hamidouche: EURECOM
Laura Cottatellucci: FAU
Konstantin Avrachenkov: Inria

Journal of Theoretical Probability, 2023, vol. 36, issue 1, 46-77

Abstract: Abstract In this work, we study the spectrum of the normalized Laplacian and its regularized version for random geometric graphs (RGGs) in various scaling regimes. Two scaling regimes are of special interest, the connectivity and the thermodynamic regime. In the connectivity regime, the average vertex degree grows logarithmically in the graph size or faster. In the thermodynamic regime, the average vertex degree is a constant. We introduce a deterministic geometric graph (DGG) with nodes in a grid and provide an upper bound to the probability that the Hilbert–Schmidt norm of the difference between the normalized Laplacian matrices of the RGG and DGG is greater than a certain threshold in both the connectivity and thermodynamic regime. Using this result, we show that the RGG and DGG normalized Laplacian matrices are asymptotically equivalent with high probability (w.h.p.) in the full range of the connectivity regime. The equivalence is even stronger and holds almost surely when the average vertex degree $$a_n$$ a n satisfies the inequality $$a_n > 24 \log (n).$$ a n > 24 log ( n ) . Therefore, we use the regular structure of the DGG to show that the limiting eigenvalue distribution of the RGG normalized Laplacian matrix converges to a distribution with a Dirac atomic measure at zero. In the thermodynamic regime, we approximate the eigenvalues of the regularized normalized Laplacian matrix of the RGG by the eigenvalues of the DGG regularized normalized Laplacian and we provide an error bound which is valid w.h.p. and depends upon the average vertex degree.

Keywords: Random geometric graph; Normalized Laplacian; Limiting eigenvalue distribution; Connectivity regime; Thermodynamic regime; 60B20 random matrices; 05C80 random graphs (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-022-01158-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:36:y:2023:i:1:d:10.1007_s10959-022-01158-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-022-01158-0

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().