On the number of weakly connected subdigraphs in random kNN digraphs

DOI10.1007/S00454-020-00218-8zbMATH Open1456.05079arXiv1606.01944OpenAlexW2409083136MaRDI QIDQ2223629FDOQ2223629

Authors: Selim Bahadır, Elvan Ceyhan 

Publication date: 29 January 2021

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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.

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

Recommendations

• On nearest-neighbor graphs
• On nearest-neighbor graphs
• Connectivity of random k-nearest-neighbour graphs
• On the degree sequence of random geometric digraphs
• scientific article; zbMATH DE number 1222330

zbMATH Keywords

asymptotic normalitycentral limit theoremlaw of large numbersreflexivityindegreebinomial processhomogeneous point process

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Enumeration in graph theory (05C30) Connectivity (05C40)

Cites Work

• Central limit theorems for some graphs in computational geometry.
• Random Geometric Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph-theoretic measures of multivariate association and prediction
• Overall and pairwise segregation tests based on nearest neighbor contingency tables
• Title not available (Why is that?)
• Mutual and shared neighbor probabilities: finite- and infinite-dimensional results
• Intrinsic dimension identification via graph-theoretic methods
• Gaussian limits for random geometric measures
• Title not available (Why is that?)
• When are small subgraphs of a random graph normally distributed?
• On nearest-neighbor graphs
• Explicit laws of large numbers for random nearest-neighbour-type graphs
• Title not available (Why is that?)
• Upper tails for subgraph counts in random graphs
• Limit theory for random sequential packing and deposition
• The kissing number in four dimensions
• Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test
• On central limit theorems in geometrical probability
• On the fraction of random points by specified nearest-neighbour interrelations and degree of attraction
• Reflexive Nearest Neighbours
• Nearest neighbors and Voronoi regions in certain point processes
• On the number of subgraphs of a specified form embedded in a random graph
• Nearest neighbours in a Poisson ensemble
• Isolated nearest neighbors
• Subgraph counts in random graphs using incomplete U-statistics methods
• Testing spatial symmetry using contingency tables based on nearest neighbor relations
• Normal approximation for stabilizing functionals
• A large-dimensional independent and identically distributed property for nearest neighbor counts in Poisson processes
• On central limit theorems in stochastic geometry for add-one cost stabilizing functionals
• Laws of large numbers of subgraphs in directed random geometric networks
• A cluster problem as defined by nearest neighbours
• On the number of reflexive and shared nearest neighbor pairs in one-dimensional uniform data

Cited In (1)

• Laws of large numbers of subgraphs in directed random geometric networks

This page was built for publication: On the number of weakly connected subdigraphs in random \(k\)NN digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223629)