Hitting and Commute Times in Large Random Neighborhood Graphs
Ulrike von Luxburg, Agnes Radl, Matthias Hein.
Year: 2014, Volume: 15, Issue: 52, Pages: 1751−1798
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.