Randomized near-neighbor graphs, giant components and applications in data science

DOI10.1017/jpr.2020.21zbMath1446.60013arXiv1711.04712OpenAlexW3042432370WikidataQ99350568 ScholiaQ99350568MaRDI QIDQ3299443

Gal Mishne, Stefan Steinerberger, George C. Linderman, Yuval Kluger, Ariel Jaffe

Publication date: 22 July 2020

Published in: Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

connectivityrandom graphsparsification\(k\)-nn graph

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Connectivity (05C40) Statistical aspects of big data and data science (62R07)

Uses Software

• RCV1
• t-SNE
• Algorithm 971
• SpectralNet

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Small components in \(k\)-nearest neighbour graphs
• A new lower bound for the geometric traveling salesman problem in terms of discrepancy
• Highly connected random geometric graphs
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Probability theory of classical Euclidean optimization problems
• Weak laws of large numbers in geometric probability
• \(k\)-nearest-neighbor clustering and percolation theory
• Diffusion maps
• From graph to manifold Laplacian: the convergence rate
• Connectivity threshold of Bluetooth graphs
• The Scottish Book
• Sharpness in the k-Nearest-Neighbours Random Geometric Graph Model
• Algorithm 971
• The shortest path and the shortest road through n points
• Algorithms for the Assignment and Transportation Problems
• A Randomized Algorithm for Principal Component Analysis
• A critical constant for the k nearest-neighbour model
• Shortest Paths Through Pseudo-Random Points in the d-Cube
• Random Geometric Graphs
• Connectivity of random k-nearest-neighbour graphs
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Large deviations for discrete and continuous percolation
• Clustering with t-SNE, Provably
• New Bounds for the Traveling Salesman Constant
• Probability Inequalities for Sums of Bounded Random Variables
• How the result of graph clustering methods depends on the construction of the graph
• Learning Theory

This page was built for publication: Randomized near-neighbor graphs, giant components and applications in data science