Testing Network Structure Using Relations Between Small Subgraph Probabilities
arXiv:1704.06742
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 under an Erdős-Rényi null model. We then analyze the power of the associated test statistic under a general class of alternative models. In particular, when the alternative is a -community stochastic block model, with 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 (12)
- Emergence of scaling in random networks
- Stochastic blockmodels and community structure in networks
- Fast community detection by SCORE
- Rate-optimal graphon estimation
- Detection of an anomalous cluster in a network
- Stochastic Block Models and Reconstruction
- Nonparametric graphon estimation
- Optimal Estimation and Completion of Matrices with Biclustering Structures
- Achieving Optimal Misclassification Proportion in Stochastic Block Model
- Private Graphon Estimation for Sparse Graphs
- The DFS Fused Lasso: Linear-Time Denoising over General Graphs
- Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections
Cited by in corpus (17)
- Sparse graphs using exchangeable random measures
- 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
- Variational principle for scale-free network motifs
- Testing network correlation efficiently via counting trees
- 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 -statistics on bipartite networks