Testing Transitivity in Graphs

 by Martin Karlberg

 Research Report 1995:2

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


The situation is considered whether a graph can be assumed to have been generated by a random model capturing more transitivity than a simple Bernoulli model. Five different test quantities based on degree variance, local densities and cycle counts are used. 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 random triangle model, a simple random graph model in which the clustering and transitivity is higher than in the Bernoulli model. The test based on density difference (the difference between mean local density and overall graph density) has the highest power in most situations. The tests are applied to a large set of school class sociograms. In this situation, Bernoulli randomness is rejected in favor of transitivity more frequently when the density difference is used. It is concluded that although the sociograms can be said to contain empirical transitivity, which not is so well described by the random triangle model, the test that proved to have the highest power against the random triangle model also seems to be good at detecting the transitivity structure of these data.

 Key words: Transitivity, Clustering, Bernoulli Model, Random Triangle Model, Local Set, Local Net, Local Density. 

Close this Window

Last update: 1997-12-16 / KH