Name
Title | ||
|---|---|---|
Hitting times, commute distances and the spectral gap for large random geometric graphs |
Abstract | ||
|---|---|---|
The commute distance between two vertices in a graph is the expected time it
takes a random walk to travel from the first to the second vertex and back.
According to folklore opinion, it has the property that vertices in the same
cluster of the graph are close to each other while vertices in different
clusters are far from each other. We study the behavior of the commute distance
and hitting times on random geometric graphs ($\epsilon$-graphs, $k$-nearest
neighbor graphs and Gaussian similarity graphs). It turns out that as the size
of the graph increases, the suitably rescaled hitting times and commute
distances can be approximated by extremely simple expressions. However, these
expressions no longer take into account the cluster structure of the graph,
which leads to a completely meaningless distance function. Consequently, the
use of the commute distance for machine learning purposes is discouraged for
large graphs and in high dimensions. Our paper also makes several important
technical contributions such as bounding the spectral gap in random geometric
graphs with general support and distribution. |
Year | Venue | Keywords |
|---|---|---|
2010 | Clinical Orthopaedics and Related Research | distance function,random geometric graph,random walk,hitting time,machine learning,k nearest neighbor |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Random graph,Spectral gap,Heterogeneous random walk in one dimension,Mathematics | Journal | abs/1003.1 |
Citations | PageRank | References |
3 | 1.22 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| von luxburg | 1 | 3246 | 170.11 |
| Agnes Radl | 2 | 44 | 3.50 |
| Matthias Hein | 3 | 663 | 62.80 |