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

DOI10.1016/j.tcs.2009.01.009zbMath1167.68045arXiv0912.3408OpenAlexW2122218279MaRDI QIDQ1017654

Matthias Hein, Ulrike von Luxburg, Markus Maier

Publication date: 12 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.3408

zbMATH Keywords

clusteringneighborhood graphrandom geometric graphconnected component

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs, Estimation of level set trees using adaptive partitions, Fully adaptive density-based clustering, On the normalized Laplacian spectra of random geometric graphs, SELP: semi-supervised evidential label propagation algorithm for graph data clustering, Unconstrained and curvature-constrained shortest-path distances and their approximation, A Review on Modal Clustering, Cluster Identification in Nearest-Neighbor Graphs, Spectral clustering based on local linear approximations, On clustering procedures and nonparametric mixture estimation, Statistical analysis of a hierarchical clustering algorithm with outliers

Cites Work

• Unnamed Item
• Unnamed Item
• Connectivity of the mutual \(k\)-nearest-neighbor graph in clustering and outlier detection
• Percolation
• Cluster Identification in Nearest-Neighbor Graphs
• Threshold Functions, Node Isolation, and Emergent Lacunae in Sensor Networks
• Consistency of Single Linkage for High-Density Clusters
• Random Geometric Graphs
• Paths in graphs
• Probability Inequalities for Sums of Bounded Random Variables
• A graph-based estimator of the number of clusters
• Combinatorial methods in density estimation