Multigraphs for the Uncovering and Testing of Structures

The main difficulty in deriving test statistics for testing hypotheses of the structure of a data set lies in finding a suitable mathematical definition of the term “homogeneity” or vice versa to define a mathematical model which “fits” to a real, but homogeneous, world. This model should be both realistic and mathematically tractable. Graph-theoretic cluster analysis provides the analyst with probability models from which tests for the hypothesis of homogeneity within a data set can be derived for many environments. Because of variations of the scale levels between the different attributes of the objects of a sample, it is better not to compute one single similarity between any pair of vertices but more — say t — similarities. The structure of a set of mixed data then can more appropriately be described by a superposition of t graphs, a so-called “completely labeled multigraphs”. This multigraph model also provides researchers with more sophisticated and flexible probability models to formulate and test different hypotheses of homogeneity within sets of mixed data. Three different probability models for completely labelled random multigraphs are developed, their asymptotical equivalence is shown, and their advantages when applied to testing the “randomness” of clusters found by single-linkage classification algorithms are discussed.