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.

References in corpus (12)

• Emergence of scaling in random networks
• Stochastic blockmodels and community structure in networks
• Fast community detection by SCORE
• Detection of an anomalous cluster in a network
• Stochastic Block Models and Reconstruction
• Coauthorship and Citation Networks for Statisticians
• Block Models and Personalized PageRank
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Mixed Membership Estimation for Social Networks
• Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections
• Information-theoretic thresholds for community detection in sparse networks
• Community Detection in Degree-Corrected Block Models

Cited by in corpus (15)

• Testing network correlation efficiently via counting trees
• Testing Community Structures for Hypergraphs
• Hierarchical community detection by recursive partitioning
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Universal Rank Inference via Residual Subsampling with Application to Large Networks
• Using Maximum Entry-Wise Deviation to Test the Goodness-of-Fit for Stochastic Block Models
• DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
• On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
• Informative core identification in complex networks
• Detecting Statistically Significant Communities
• Graph Clustering Via QUBO and Digital Annealing
• Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient
• Random geometric graphs and the spherical Wishart matrix
• A Practical Two-Sample Test for Weighted Random Graphs
• The Hierarchy of Block Models