Co-clustering separately exchangeable network data
arXiv:1212.4093 · doi:10.1214/13-AOS1173
Abstract
This article establishes the performance of stochastic blockmodels in addressing the co-clustering problem of partitioning a binary array into subsets, assuming only that the data are generated by a nonparametric process satisfying the condition of separate exchangeability. We provide oracle inequalities with rate of convergence corresponding to profile likelihood maximization and mean-square error minimization, and show that the blockmodel can be interpreted in this setting as an optimal piecewise-constant approximation to the generative nonparametric model. We also show for large sample sizes that the detection of co-clusters in such data indicates with high probability the existence of co-clusters of equal size and asymptotically equivalent connectivity in the underlying generative process.
arXiv commentPublished in at http://dx.doi.org/10.1214/13-AOS1173 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (13)
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Resolution limit in community detection
- Spectral clustering and the high-dimensional stochastic blockmodel
- Matrix estimation by Universal Singular Value Thresholding
- Graph limits and exchangeable random graphs
- Consistency of community detection in networks under degree-corrected stochastic block models
- Stochastic blockmodels with growing number of classes
- Community extraction for social networks
- Multiplicative Attribute Graph Model of Real-World Networks
- The method of moments and degree distributions for network models
- Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
Cited by in corpus (20)
- Matrix estimation by Universal Singular Value Thresholding
- Sparse graphs using exchangeable random measures
- Network histograms and universality of blockmodel approximation
- Nonparametric graphon estimation
- Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
- Optimal Estimation and Completion of Matrices with Biclustering Structures
- A Consistent Histogram Estimator for Exchangeable Graph Models
- Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
- Estimating Causal Peer Influence in Homophilous Social Networks by Inferring Latent Locations
- Estimating network edge probabilities by neighborhood smoothing
- Network cross-validation by edge sampling
- Generalized linear models with low rank effects for network data
- EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
- Profile Likelihood Biclustering
- From which world is your graph?
- Spectral clustering in the dynamic stochastic block model
- Unfolding-Model-Based Visualization: Theory, Method and Applications
- Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
- Co-factor analysis of citation networks
- Multiway empirical likelihood