On the Distribution of the Number of Copies of Weakly Connected Digraphs in Random $k$NN Digraphs

Abstract

In a digraph with $n$ vertices, a minuscule construct is a subdigraph with $m<<n$ vertices. We study the number of copies of a minuscule constructs in $k$ nearest neighbor ($k$NN) digraph of the data from a random point process in ${\mathbb{R}}^d$. Based on the asymptotic theory for functionals of point sets under homogeneous Poisson process and binomial point process, we provide a general result for the asymptotic behavior of the number of minuscule constructs and as corollaries, we obtain asymptotic results for the number of vertices with fixed indegree, the number of shared $k$NN pairs and the number of reflexive $k$NN's in a $k$NN digraph.

arXiv comment28 pages, 7 figures

References in corpus (3)

• Explicit laws of large numbers for random nearest-neighbour type graphs
• Laws of Large Numbers of Subgraphs in Directed Random Geometric Networks
• On the Number of Reflexive and Shared Nearest Neighbor Pairs in One-Dimensional Uniform Data