2017/04/22 by Chao Gao, John Lafferty, Gao, Chao +1
Biochemistry, Genetics and Molecular Biology · Physics and Astronomy · #Bioinformatics and Genomic Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Methodology (stat.ME) #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1704.06742
openalex publication_date 2017/04/22 · openalex created_date 2017/05/05 · openalex updated_date 2026/07/28
We study the problem of testing for structure in networks using relations between the observed frequencies of small subgraphs. We consider the statistics T3 amp; =(edge frequency)3 - triangle frequency
T2 amp; =3(edge frequency)2(1-edge frequency) - V-shape frequency and prove a central limit theorem for (T2, T3) under an Erdős-Rényi null model. We then analyze the power of the associated χ2 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.