The Application of Random Coincidence Graphs for Testing the Homogeneity of Data

Graph-theoretic classification models provide us with probability models which can be used to study the structure of a data set. In models of random interval graphs or, generally, random coincidence graphs, points are drawn “at random” and joined by lines if their mutual distances are smaller than a threshold d. This is exactly the procedure of finding linkage clusters. We present exact and asymptotic results for properties of those random graphs, especially for the properties that the expected numbers of isolated edges and of isolated vertices remain positive finite as the total number of vertices grows. These properties can serve as test statistics for testing the homogeneity in a data set; they can be used to derive tests for goodness of fit as well.