Testing Network Structure Using Relations Between Small Subgraph Probabilities

Abstract

We study the problem of testing for structure in networks using relations between the observed frequencies of small subgraphs. We consider the statistics \begin{align*} T_3 & =(\text{edge frequency})^3 - \text{triangle frequency}\\ T_2 & =3(\text{edge frequency})^2(1-\text{edge frequency}) - \text{V-shape frequency} \end{align*} and prove a central limit theorem for $(T_2,T_3)$ under an Erdős-Rényi null model. We then analyze the power of the associated ${\chi }^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.

References in corpus (2)

• Stochastic blockmodels and community structure in networks
• Private Graphon Estimation for Sparse Graphs

Cited by in corpus (16)

• Testing for Global Network Structure Using Small Subgraph Statistics
• Optimal hypothesis testing for stochastic block models with growing degrees
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Statistical inference for network samples using subgraph counts
• Testing network correlation efficiently via counting trees
• Variational principle for scale-free network motifs
• Optimal Single Sample Tests for Structured versus Unstructured Network Data
• Subgraphs in preferential attachment models
• Testing Community Structures for Hypergraphs
• Detecting Statistically Significant Communities
• Counting Motifs with Graph Sampling
• Graph Clustering Via QUBO and Digital Annealing
• Testing Changes in Communities for the Stochastic Block Model
• Combinatorial-Probabilistic Trade-Off: Community Properties Test in the Stochastic Block Models
• Testing for the Network Small-World Property
• Hoeffding-type decomposition for $U$-statistics on bipartite networks