Testing Transitivity in Digraphs

 by Martin Karlberg

 Research Report 1997:5

 Department of Statistics, Stockholm University, S-106 91 Stockholm, Sweden


The problem of testing whether irregularities observed in a digraph are due to transitivity is studied. Three test quantities are used: the proportion of transitive triples out of all triples, the proportion of transitive triples out of all non-vacuously transitive triples and the density difference (the difference between mean local density and overall graph density). The null distribution used is the rather complex uniform distribution of digraphs conditional on the in- and outdegrees. A simulation study is made in order to estimate critical values of the tests for different significance levels. The powers of the tests are estimated against the Bernoulli transitive triple model, which assumes a simple random graph distribution in which the transitivity is high. The test based on density difference has the highest power in many cases. The tests are applied to a large set of school class sociograms, and it is found that uniform randomness is rejected in favor of transitivity most frequently when the test based on the density difference is used. The vast majority of these sociograms are however so far from the uniform distribution, that the null hypothesis of uniform randomness is rejected regardless of which test is used. Nevertheless, the results imply that the density difference is the most useful of the measures examined at detecting transitivity.

 Key words: Transitivity, Local Set, Local Density, Conditional Uniform Random Graph Distribution. 

Close this Window

Last update: 1997-12-16 / KH