查看文章

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.