TESTING TRANSITIVITY IN GRAPHS

The situation is considered whether a graph can be assumed to have bee n generated by a random model capturing more transitivity than a simpl e uniform model. Three different test quantities based on induced tria d counts and local densities are used. A simulation study is made in o rder to estimate critical values of the tests for different significan ce levels. The powers of the tests are estimated against the Bernoulli triangle model, a simple random graph model in which the clustering a nd transitivity is higher than in the uniform model. The test based on the proportion of transitive triads has the highest power in most cas es, but the test based on density difference (the difference between m ean local density and overall graph density) is more powerful against models with high transitivity. The tests are applied to a large set of school class sociograms. In this situation, uniform randomness is rej ected in favor of transitivity most frequently when the test based on the proportion of transitive triads out of the non-vacuously transitiv e triads is used. It is concluded that this test, which also performed reasonably well when applied to random data, is the best at detecting transitivity. Although the Bernoulli triangle model fits to the empir ical data set better than the uniform model, there are fewer truly int ransitive triads in the data than could be expected under either of th e models. (C) 1997 Elsevier Science B.V.