Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
arXiv:1811.06055
Abstract
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection, and hypothesis testing. For each problem, we review state-of-the-art results in the literature followed by general principles behind the optimal procedures that lead to minimax estimation and testing. This allows us to connect problems in network analysis to other statistical inference problems from a general perspective.
References in corpus (28)
- Community structure in social and biological networks
- Stochastic blockmodels and community structure in networks
- Consistency of spectral clustering
- Matrix estimation by Universal Singular Value Thresholding
- Fast community detection by SCORE
- Sparse PCA: Optimal rates and adaptive estimation
- Graph limits and exchangeable random graphs
- Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
- Rate-optimal graphon estimation
- Sparse graphs using exchangeable random measures
- Network histograms and universality of blockmodel approximation
- Nonparametric graphon estimation
- Computational barriers in minimax submatrix detection
- Sparse exchangeable graphs and their limits via graphon processes
- The Class of Random Graphs Arising from Exchangeable Random Measures
- Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
- Optimal Estimation and Completion of Matrices with Biclustering Structures
- A Consistent Histogram Estimator for Exchangeable Graph Models
- Testing for Global Network Structure Using Small Subgraph Statistics
- Optimal hypothesis testing for stochastic block models with growing degrees
- Exact Exponent in Optimal Rates for Crowdsourcing
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Edge exchangeable models for network data
- A General Framework for Bayes Structured Linear Models
- Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
- Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
- Phase Transitions in Approximate Ranking
- Network Global Testing by Counting Graphlets