Optimal construction of k-nearest neighbor graphs for identifying noisy clusters

Markus Maier, Matthias Hein, Ulrike von Luxburg

We study clustering algorithms based on neighborhood graphs on a random sample of data points. The question we ask is how such a graph should be constructed in order to obtain opti…