Testing Network Structure Using Relations Between Small Subgraph Probabilities

We study the problem of testing for structure in networks using relations between the observed frequencies of small subgraphs. We consider the statistics beginalign* T3 & =(edge frequency)3 - triangle frequency T2 & =3(edge frequency)2(1-edge frequency) - V-shape frequency endalign* and prove a central limit theorem for (T2, T3) under an ErdHos-R'enyi null model. We then analyze the power of the associated chi2 test statistic under a general class of alternative models. In particular, when the alternative is a k-community stochastic block model, with k unknown, the power of the test approaches one. Moreover, the signal-to-noise ratio required is strictly weaker than that required for community detection. We also study the relation with other statistics over three-node subgraphs, and analyze the error under two natural algorithms for sampling small subgraphs. Together, our results show how global structural characteristics of networks can be inferred from local subgraph frequencies, without requiring the global community structure to be explicitly estimated.