Title: Testing for Global Network Structure Using Small Subgraph Statistics,
Abstract: We study the problem of testing for community structure in networks using
relations between the observed frequencies of small subgraphs. We propose a
simple test for the existence of communities based only on the frequencies of
three-node subgraphs. The test statistic is shown to be asymptotically normal
under a null assumption of no community structure, and to have power
approaching one under a composite alternative hypothesis of a degree-corrected
stochastic block model. We also derive a version of the test that applies to
multivariate Gaussian data. Our approach achieves near-optimal detection rates
for the presence of community structure, in regimes where the signal-to-noise
is too weak to explicitly estimate the communities themselves, using existing
computationally efficient algorithms. We demonstrate how the method can be
effective for detecting structure in social networks, citation networks for
scientific articles, and correlations of stock returns between companies on the
S\&P 500.