On the Spectrum of Dense Random Geometric Graphs
| Autor: | Adhikari, Kartick, Adler, Robert J., Bobrowski, Omer, Rosenthal, Ron |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In this paper we study the spectrum of the random geometric graph $G(n,r)$, in a regime where the graph is dense and highly connected. In the \erdren $G(n,p)$ random graph it is well known that upon connectivity the spectrum of the normalized graph Laplacian is concentrated around $1$. We show that such concentration does not occur in the $G(n,r)$ case, even when the graph is dense and almost a complete graph. In particular, we show that the limiting spectral gap is strictly smaller than $1$. In the special case where the vertices are distributed uniformly in the unit cube and $r=1$, we show that for every $0\le k \le d$ there are at least $\binom{d}{k}$ eigenvalues near $1-2^{-k}$, and the limiting spectral gap is exactly $1/2$. We also show that the corresponding eigenfunctions in this case are tightly related to the geometric configuration of the points. Comment: 32 pages, 2 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|