Name
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.5555/2627435.2638591 | Journal of Machine Learning Research |
Keywords | Field | DocType |
commute distance,resistance,spectral gap,k-nearest neighbor graph,random graph | Discrete mathematics,Random regular graph,Indifference graph,Combinatorics,Random graph,Chordal graph,Degree distribution,Resistance distance,Hitting time,Pathwidth,Mathematics | Journal |
Volume | Issue | ISSN |
15 | 1 | 1532-4435 |
Citations | PageRank | References |
19 | 0.89 | 27 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| von luxburg | 1 | 3246 | 170.11 |
| Agnes Radl | 2 | 44 | 3.50 |
| Matthias Hein | 3 | 663 | 62.80 |