Mixing Times for Random Walks on Geometric Random Graphs.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, Devavrat Shah · 2005
A geometric random graph, Gd (n, r), is formed as follows: place n nodes uniformly at random onto the surface of the d-dimensional unit torus and connect nodes which are within a distance r of each other. The Gd (n, r) has been of great interest due to its success as a model for ad-hoc wireless networks. It is well known that the connectivity of Gd (n, r) exhibits a threshold property: there exists a constant αd such that for any ɛ> 0, for rd αd(1 + ɛ) log n/n the Gd (n, r) is connected w.h.p.. In this paper, we study mixing properties of random walks on G d (n, r) for r d (n) = ω(log n/n). Specifically, we study the scaling of mixing times of the fastest-mixing reversible random walk, and the natural random walk. We find that the mixing time of both of these random walks have the same scaling laws and scale proportional to r −2 (for all d). These results hold for G d (n, r) when distance is defined using any Lp norm. Though the results of this paper are not so surprising, they are nontrivial and require new methods. To obtain the scaling law for the fastest-mixing reversible random walk, we first explicitly characterize the fastest-mixing reversible random walk on a regular (grid-type) graph in d dimensions. We subsequently use this to bound the mixing time of the fastest-mixing random walk on Gd (n, r). In the course of our analysis, we obtain a tight relation between the mixing time of the fastest-mixing symmetric random walk and the fastest-mixing reversible random walk with a specified equilibrium distribution on an arbitrary graph.