Hamidouche M, Cottatellucci L, Avrachenkov K (2022)
Publication Type: Journal article
Publication year: 2022
DOI: 10.1007/s10959-022-01158-0
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
APA:
Hamidouche, M., Cottatellucci, L., & Avrachenkov, K. (2022). On the Normalized Laplacian Spectra of Random Geometric Graphs. Journal of Theoretical Probability. https://doi.org/10.1007/s10959-022-01158-0
MLA:
Hamidouche, Mounia, Laura Cottatellucci, and Konstantin Avrachenkov. "On the Normalized Laplacian Spectra of Random Geometric Graphs." Journal of Theoretical Probability (2022).
BibTeX: Download