The distribution of the relative arc density of a family of interval catch digraph based on uniform data

DOI10.1007/S00184-011-0351-YzbMATH Open1410.62078arXiv1002.2957OpenAlexW2012302297MaRDI QIDQ715495FDOQ715495

Authors: Elvan Ceyhan 

Publication date: 29 October 2012

Published in: Metrika (Search for Journal in Brave)

Abstract: The vertex-random graphs called proximity catch digraphs (PCDs) have been introduced recently and have applications in pattern recognition and spatial pattern analysis. A PCD is a random directed graph (i.e., digraph) which is constructed from data using the relative positions of the points from various classes. Different PCDs result from different definitions of the proximity region associated with each data point. We consider the underlying and reflexivity graphs based on a family of PCDs which is determined by a family of parameterized proximity maps called proportional-edge (PE) proximity map. The graph invariant we investigate is the relative edge density of the underlying and reflexivity graphs. We demonstrate that, properly scaled, relative edge density of these graphs is a $U$-statistic, and hence obtain the asymptotic normality of the relative edge density for data from any distribution that satisfies mild regulatory conditions. By detailed probabilistic and geometric calculations, we compute the explicit form of the asymptotic normal distribution for uniform data on a bounded region in the usual Euclidean plane. We also compare the relative edge densities of the two types of the graphs and the relative arc density of the PE-PCDs. The approach presented here is also valid for data in higher dimensions.

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

Recommendations

• Density of a random interval catch digraph family and its use for testing uniformity
• The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data
• Domination number of an interval catch digraph family and its use for testing uniformity
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• On the interval number of random graphs
• On some subclasses of interval catch digraphs
• On the Distribution of the Domination Number of a New Family of Parametrized Random Digraphs
• A characterization of interval catch digraphs
• The interval number of dense graphs
• scientific article; zbMATH DE number 2090219

zbMATH Keywords

\(U\)-statisticsrandom graphproximity mapproximity catch digraphclass cover catch digraphintersection digraph

Mathematics Subject Classification ID

Multivariate distribution of statistics (62H10) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Approximations to statistical distributions (nonasymptotic) (62E17) Combinatorial probability (60C05)

Cites Work

• The relative neighbourhood graph of a finite planar set
• On the distribution of the domination number for random class cover catch digraphs
• Classification using class cover catch digraphs
• Characterizing the scale dimension of a high-dimensional classification problem
• A new family of proximity graphs: class cover catch digraphs
• The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new family of random graphs for testing spatial segregation
• Class cover catch digraphs for latent class discovery in gene expression monitoring by DNA microarrays
• Relative density of the random \(R\)-factor proximity catch digraph for testing spatial patterns of segregation and association
• Title not available (Why is that?)
• Algorithms for interval catch digraphs
• Inequalities for minimal covering sets in set systems of given rank
• Approximation algorithms for the class cover problem
• Title not available (Why is that?)
• Circular‐arc digraphs: A characterization
• The Berry-Esseen theorem for U-statistics
• On the Distribution of the Domination Number of a New Family of Parametrized Random Digraphs

Cited In (6)

• On some subclasses of interval catch digraphs
• Domination number of an interval catch digraph family and its use for testing uniformity
• Comparison of relative density of two random geometric digraph families in testing spatial clustering
• Density of a random interval catch digraph family and its use for testing uniformity
• Edge density of new graph types based on a random digraph family
• The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data

This page was built for publication: The distribution of the relative arc density of a family of interval catch digraph based on uniform data

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