Co-clustering separately exchangeable network data

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 ${\mathcal{O}}_P(n^{-1/4})$ 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.

Published 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 (5)

• Modularity and community structure in networks
• Resolution limit in community detection
• Matrix estimation by Universal Singular Value Thresholding
• Graph limits and exchangeable random graphs
• The method of moments and degree distributions for network models

Cited by in corpus (19)

• 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
• 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
• Spectral clustering in the dynamic stochastic block model
• From which world is your graph?
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• Unfolding-Model-Based Visualization: Theory, Method and Applications
• Multiway empirical likelihood
• Co-factor analysis of citation networks