Edge density of new graph types based on a random digraph family

Abstract

We consider two types of graphs based on a family of proximity catch digraphs (PCDs) and study their edge density. in particular, the PCDs we use are a parameterized digraph family called proportional-edge (PE) PCDs and the two associated graph types are the "underlying graphs" and the newly introduced "reflexivity graphs" based on the PE-PCDs. these graphs are extensions of random geometric graphs where distance is replaced with a dissimilarity measure and the threshold is not fixed but depends on the location of the points. PCDs and the associated graphs are constructed based on data points from two classes, say X and y, where one class (say class X) forms the vertices of the PCD and the Delaunay tessellation of the other class (i.e., class y) yields the (Delaunay) cells which serve as the support of class X points. We demonstrate that edge density of these graphs is a U-statistic, hence obtain the asymptotic normality of it for data from any distribution that satisfies mild regulatory conditions. the rate of convergence to asymptotic normality is sharper for the edge density of the reflexivity and underlying graphs compared to the arc density of the PE-PCDs. for uniform data in Euclidean plane where Delaunay cells are triangles, we demonstrate that the distribution of the edge density is geometry invariant (i.e., independent of the shape of the triangular support). We compute the explicit forms of the asymptotic normal distribution for uniform data in one Delaunay triangle in the Euclidean plane utilizing this geometry invariance property. We also provide various versions of edge density in the multiple triangle case. the approach presented here can also be extended for application to data in higher dimensions.