## Hitting and Commute Times in Large Random Neighborhood Graphs

*Ulrike von Luxburg, Agnes Radl, Matthias Hein*; 15(May):1751−1798, 2014.

### Abstract

In machine learning, a popular tool to analyze the structure of
graphs is the hitting time and the commute distance (resistance
distance). For two vertices $u$ and $v$, the hitting time
$H_{uv}$ is the expected time it takes a random walk to travel
from $u$ to $v$. The commute distance is its symmetrized version
$C_{uv} = H_{uv} + H_{vu}$. In our paper we study the behavior
of hitting times and commute distances when the number $n$ of
vertices in the graph tends to infinity. We focus on random
geometric graphs ($\epsilon$-graphs, kNN graphs and Gaussian
similarity graphs), but our results also extend to graphs with a
given expected degree distribution or Erdos-Renyi graphs with
planted partitions. We prove that in these graph families, the
suitably rescaled hitting time $H_{uv}$ converges to $1/d_v$ and
the rescaled commute time to $1/d_u + 1/d_v$ where $d_u$ and
$d_v$ denote the degrees of vertices $u$ and $v$. In these
cases, hitting and commute times do not provide information
about the structure of the graph, and their use is discouraged
in many machine learning applications.

[abs][pdf][bib]