Hitting and commute times in large random neighborhood graphs
Lists
Only you see this
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 Huv is the expected time it takes a random walk to travel from u to v. The commute distance is its symmetrized version Cuv = Huv +Hvu. 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 (ε-graphs, kNN graphs and Gaussian similarity graphs), but our results also extend to graphs with a given expected degree distribution or Erdos-Rényi graphs with planted partitions. We prove that in these graph families, the suitably rescaled hitting time Huv converges to 1/dv and the rescaled commute time to 1/du+1=dv where du and dv 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.
BibTeX
@article{luxburg2014hitting,
author = {Ulrike von Luxburg and Agnes Radl and Matthias Hein},
title = {{Hitting and commute times in large random neighborhood graphs}},
journal = {J. Mach. Learn. Res.},
year = {2014},
url = {https://openreview.net/forum?id=CyQPB2jiJ0_},
}Loading related content...