Testing transitivity in digraphs

The problem of testing the transitivity of a relationship observed in a dig raph, taking as many nontransitivity related irregularities as possible int o account, is studied. Two test quantities are used: (I) the proportion of transitive triples out of all nonvacuously transitive triples, and (2) the density difference (the difference between,mean local transitivity density and overall edge density). The null distribution used is the rather complex uniform distribution on digraphs conditional an the indegrees and outdegre es. A simulation study is made in order to estimate critical values of the tests for different significance levels. When all vertices have the same in degree and outdegree, the occurrence of transitive triples is rather infreq uent in most conditional uniform graphs; this is reflected by low critical values of the transitivity-related test statistics. When both the indegree and outdegree sequences are skewed in the same direction, there is a small number of vertices with large indegrees and outdegrees. This results in a c lustering structure, in which transitive triples occur frequently in such c onditional uniform graphs, the critical values of the test statistics are r ather high. The powers of the tests are estimated against the Bernoulli transitive trip le model, which assumes a simple random graph distribution in which the tra nsitivity is high. The test based on density difference has the highest pow er in many cases. The tests are applied to a large set of classroom sociogr ams, and in this situation it is also found that uniform randomness is reje cted in flavor of transitivity most frequently when the test based on the d ensity difference is used. However, the vast majority of these sociograms a re 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 best detector of transiti vity related to the measures examined.