by Ulrike von Luxburg, Agnes Radl, Matthias Hein
Abstract:
Next to the shortest path distance, the second most popular distance function between vertices in a graph is the commute distance (resistance distance). For two vertices u and v, the hitting time H\_\uv\ is the expected time it takes a random walk to travel from u to v. The commute time is its symmetrized version C\_\uv\ = H\_\uv\ + H\_\vu\. In our paper we study the behavior of hitting times and commute distances when the number n of vertices in the graph is very large. We prove that as n converges to infinty, hitting times and commute distances converge to expressions that do not take into account the global structure of the graph at all. Namely, the hitting time H\_\uv\ converges to 1/d\_v and the commute time to 1/d\_u + 1/d\_v where d\_u and d\_v denote the degrees of vertices u and v. In these cases, the hitting and commute times are misleading in the sense that they do not provide information about the structure of the graph. We focus on two major classes of random graphs: random geometric graphs (k-nearest neighbor graphs, epsilon-graphs, Gaussian similarity graphs) and random graphs with given expected degrees (in particular, Erdos-Renyi graphs with and without planted partitions)
Reference:
Hitting and commute times in large graphs are often misleading (Ulrike von Luxburg, Agnes Radl, Matthias Hein), In ArXiv, volume 1003.1266, 2011.
Bibtex Entry:
@article{VonLuxburg2010,
abstract = {Next to the shortest path distance, the second most popular distance function between vertices in a graph is the commute distance (resistance distance). For two vertices u and v, the hitting time H\_\{uv\} is the expected time it takes a random walk to travel from u to v. The commute time is its symmetrized version C\_\{uv\} = H\_\{uv\} + H\_\{vu\}. In our paper we study the behavior of hitting times and commute distances when the number n of vertices in the graph is very large. We prove that as n converges to infinty, hitting times and commute distances converge to expressions that do not take into account the global structure of the graph at all. Namely, the hitting time H\_\{uv\} converges to 1/d\_v and the commute time to 1/d\_u + 1/d\_v where d\_u and d\_v denote the degrees of vertices u and v. In these cases, the hitting and commute times are misleading in the sense that they do not provide information about the structure of the graph. We focus on two major classes of random graphs: random geometric graphs (k-nearest neighbor graphs, epsilon-graphs, Gaussian similarity graphs) and random graphs with given expected degrees (in particular, Erdos-Renyi graphs with and without planted partitions)},
archivePrefix = {arXiv},
arxivId = {1003.1266},
author = {von Luxburg, Ulrike and Radl, Agnes and Hein, Matthias},
eprint = {1003.1266},
journal = {ArXiv},
keywords = {SML-LIB-BIBLIO,lang:ENG},
mendeley-tags = {SML-LIB-BIBLIO,lang:ENG},
month = mar,
title = {{Hitting and commute times in large graphs are often misleading}},
url = {http://arxiv.org/abs/1003.1266},
volume = {1003.1266},
year = {2011}
}