Notation

• $D$, Let $D \subset \Bbb R^d$ be a set of d-dimensional points
• $N_k(\mathbf x)$, the number of k-occurrences of point $\mathbf x$, that is the number of times $\mathbf x$ occurs among k nearest neighbors of all other points in a data set
  • $N_k(\mathbf x)$ is the in-degree of node $\mathbf x$ in the k-NN digraph
  • It was observed that the distribution of $N_k$ can become skewed, resulting in the emergence of hubs – points with high $N_k$