Abstract:

In recent years random-walk-based algorithms have been proposed for a 
variety of networking tasks. These proposals include searching, 
routing, self-stabilization, and query processing in wireless 
networks, peer-to-peer networks and other distributed systems. This 
approach is gaining popularity since random walks present locality, 
simplicity, low-overhead and inherent robustness to structural 
changes.

Two properties of the random walk on graphs are essential to 
determine the efficiency of this approach: cover time (expected time 
to visit all nodes) and mixing time (time to sample a node 
uniformly). Recently, with the advent of ad-hoc and sensor networks, 
an interesting class of random graphs, namely random geometric 
graphs, has gained new relevance and its properties have been the 
subject of much study.  A random geometric graph G(n, r) is obtained 
by placing n points uniformly at random on the unit square and 
connecting two points iff their Euclidean distance is at most r.  
The phase transition behavior with respect to the radius r of such 
graphs has been of special interest. We show that there exists a 
critical radius r_opt such that for any r >= r_opt G(n, r) has 
optimal cover time of \Theta(n \log n) with high probability, and, 
importantly, r_opt = Theta(r_con) where r_con denotes the critical 
radius guaranteeing asymptotic connectivity. Moreover, since a 
disconnected graph has infinite cover time, there is a phase 
transition and the corresponding threshold width is O(r_con). On the 
other hand, the radius required for rapid mixing r_rapid = 
\omega(r_con), and, in particular, r_rapid = \Theta(1/poly(log n)). 
We are able to draw our results by giving a tight bound on the 
electrical resistance and conductance of G(n, r) via certain 
constructed flows.