The spectrum of a random geometric graph is concentrated

2004/08/09 by Sanatan Rai, Rai, Sanatan · 1 citation
Mathematics · Physics and Astronomy · #34L20 #60D05 #FOS: Mathematics #FOS: Physical sciences #Probability (math.PR) #Spectral Theory (math.SP) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #math.PR #math.SP #msc:34L20 #msc:60D05

paper · pdf · doi:10.48550/arxiv.math/0408103

arxiv created 2004/09/23 · arxiv updated 2009/12/01

Abstract

Consider n points distributed uniformly in [0,1]^d. Form a graph by connecting two points if their mutual distance is no greater than r(n). This gives a random geometric graph, \gnrn, which is connected for appropriate r(n). We show that the spectral measure of the transition matrix of the simple random walk (\abbrsrw) on \gnrn is concentrated, and in fact converges to that of the graph on the deterministic grid.

Cited by

• On the edge eigenvalues of sparse random geometric graphs

Related

• On the Spectrum of Dense Random Geometric Graphs
• Spectra of high-dimensional sparse random geometric graphs
• Spectral Analysis of the Adjacency Matrix of Random Geometric Graphs
• Which Sampling Densities are Suitable for Spectral Clustering on Unbounded Domains?
• Spectral non-concentration near the top for unimodular random graphs