Effective resistance of Gromov-hyperbolic graphs: Application to asymptotic sensor network problems
EDMOND A. JONCKHEERE, Mingji Lou, João P. Hespanha, Prabir Barooah · 2007
The technique of effective resistance has seen growing popularity in problems ranging from escape probability of random walks on graphs to asymptotic space localization in sensor networks. The results obtained thus far deal with such problems on Euclidean lattices, on which their asymptotic nature already reveals that the crucial issue is the large scale behavior of such lattices. Here we investigate how such results have to be amended on a class of graphs, referred to as Gromov hyperbolic, which behave in the large scale as negatively curved Riemannian manifolds. It is argued that Gromov hyperbolic graphs occur quite naturally in many situations. Among the results developed here, we will mention the nonvanishing probability of escape of a random walk to a Cantor set Gromov boundary and the facts that the space localization error of sensors networked in a Gromov hyperbolic fashion grows linearly with the distance to a sensor whose geographical position is known, but would become uniformly bounded in an idealized situation in which the geographical locations of the nodes at the Gromov boundary are known.