Uniform estimation in stochastic block models is slow
From MaRDI portal
Abstract: We explicitly quantify the empirically observed phenomenon that estimation under a stochastic block model (SBM) is hard if the model contains classes that are similar. More precisely, we consider estimation of certain functionals of random graphs generated by a SBM. The SBM may or may not be sparse, and the number of classes may be fixed or grow with the number of vertices. Minimax lower and upper bounds of estimation along specific submodels are derived. The results are nonasymptotic and imply that uniform estimation of a single connectivity parameter is much slower than the expected asymptotic pointwise rate. Specifically, the uniform quadratic rate does not scale as the number of edges, but only as the number of vertices. The lower bounds are local around any possible SBM. An analogous result is derived for functionals of a class of smooth graphons.
Recommendations
- When is non-trivial estimation possible for graphons and stochastic block models?
- Rate-optimal graphon estimation
- Consistency of maximum-likelihood and variational estimators in the stochastic block model
- Minimax rates of community detection in stochastic block models
- Classification and estimation in the stochastic blockmodel based on the empirical degrees
Cites work
- A nonparametric view of network models and Newman–Girvan and other modularities
- A survey of statistical network models
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Asymptotic Statistics
- Bayesian community detection
- Classification and estimation in the stochastic blockmodel based on the empirical degrees
- Community detection in dense random networks
- Community detection in sparse random networks
- Consistency of maximum-likelihood and variational estimators in the stochastic block model
- Consistency of spectral clustering in stochastic block models
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Detection of an anomalous cluster in a network
- Generic sample splitting for refined community recovery in degree corrected stochastic block models
- Graphons, cut norm and distance, couplings and rearrangements
- scientific article; zbMATH DE number 1064667 (Why is no real title available?)
- scientific article; zbMATH DE number 6791314 (Why is no real title available?)
- scientific article; zbMATH DE number 6026126 (Why is no real title available?)
- Latent Space Approaches to Social Network Analysis
- Minimax rates of community detection in stochastic block models
- Modeling social networks from sampled data
- Networks, crowds and markets. Reasoning about a highly connected world.
- New consistent and asymptotically normal parameter estimates for random-graph mixture models
- Oracle inequalities for network models and sparse graphon estimation
- Parameter identifiability in a class of random graph mixture models
- Parameter recovery in two-component contamination mixtures: the \(L^2\) strategy
- Rate-optimal graphon estimation
- Statistical analysis of network data. Methods and models
- Strong identifiability and optimal minimax rates for finite mixture estimation
- The method of moments and degree distributions for network models
Cited in
(3)
This page was built for publication: Uniform estimation in stochastic block models is slow
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2137819)
