Shortest path distance in random k-nearest neighbor graphs

Morteza Alamgir, Ulrike von Luxburg

Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on R^d. We study the convergence of the s…