On the number of weakly connected subdigraphs in random kNN digraphs

DOI10.1007/S00454-020-00218-8MaRDI QIDQ2223629zbMATH OpenOpenAlexFDO

Authors Selim Bahadır, Elvan Ceyhan

Publication date 29 January 2021

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

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

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)

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.

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

Cites work

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

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)