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
and
, the hitting time
is the expected time it takes a random walk to travel
from
to
. The commute distance is its symmetrized version
. In our paper we study the behavior
of hitting times and commute distances when the number
of
vertices in the graph tends to infinity. We focus on random
geometric graphs (
-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
converges to
and
the rescaled commute time to
where
and
denote the degrees of vertices
and
. 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]
