Triad Count Estimation in Graphs

 by Martin Karlberg

 Research Report 1995:3

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


Consider the problem of estimating the induced triad counts in a graph of known order using various kinds of information arising from a simple random sample of vertices. The four different kinds of information are: labeled local sets, unlabeled local sets, labeled local nets and unlabeled local nets. Triad count estimators are defined for these observation schemes, and by using simulation their properties in homogeneous (Bernoulli) and transitive random graphs are investigated and compared. It is found that the estimators based on labeled and unlabeled local nets are the most efficient for estimating the count of transitive triads in many situations, and that the estimator of the count of intransitive triads that is based on unlabeled local sets is, in spite of its bias due to model assumptions, the most efficient in all cases investigated.

 Key words: Triad Count, Local Set, Local Net, Network Sampling, Bernoulli Graph. 

Close this Window

Last update: 1997-12-16 / KH