Deterministic finite nearest-neighbor lists and graph symmetrizations

Let $x_1,\dots ,x_n\in {\mathbb{R}}^p$ with $n\ge 2$, using the Euclidean norm $\mathrm{\parallel }v{\mathrm{\parallel }}_2=({\sum }_{a=1}^p{v}_a^2{)}^{1\mathrm{/}2}$. For $1\le k<n$, the deterministic $k$-nearest-neighbor list $N_k(i)$ consists of the first $k$ indices $j\mathrm{\ne }i$ when the other indices are ordered by increasing pair $(\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2,j)$ lexicographically; thus equal distances are broken by increasing sample index. All graphs below have vertex set $\{1,\dots ,n\}$. The union symmetrization has edge $\{i,j\}$ when $j\in N_k(i)$ or $i\in N_k(j)$; the mutual symmetrization has edge $\{i,j\}$ exactly when both inclusions hold. Each included edge may be assigned weight $\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2$. For a radius $r>0$, the radius graph has edge $\{i,j\}$ exactly when $\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2\le r$ for $1\le i<j\le n$. An undirected graph is connected when every two vertices are joined by a finite edge path.

Hastie, Tibshirani, and Friedman, ESL II, §14.9, printed pp. 572–574

Cameron, Linear and Nonlinear Dimensionality Reduction, §6 and §7, PDF pp. 9–15