Testing for Global Network Structure Using Small Subgraph Statistics
Preprint
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.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- A Proof of the Block Model Threshold ConjectureCombinatorica, 2017
- Block models and personalized PageRankProceedings of the National Academy of Sciences, 2016
- Testing for high‐dimensional geometry in random graphsRandom Structures & Algorithms, 2016
- Reconstruction and estimation in the planted partition modelProbability Theory and Related Fields, 2014
- Large Networks and Graph Limits2012
- Parameter identifiability in a class of random graph mixture modelsJournal of Statistical Planning and Inference, 2011
- A nonparametric view of network models and Newman–Girvan and other modularitiesProceedings of the National Academy of Sciences, 2009
- On the Minimal Density of Triangles in GraphsCombinatorics, Probability and Computing, 2008
- Stochastic blockmodels: First stepsSocial Networks, 1983
- A general theory of bibliometric and other cumulative advantage processesJournal of the American Society for Information Science, 1976