The highest dimensional stochastic blockmodel with a regularized estimator

DOI10.5705/SS.2013.066MaRDI QIDQ3195174zbMATH OpenOpenAlexFDO

Authors Karl Rohe, Tai Qin, Haoyang Fan

Publication date 21 October 2015

Published in statistica Sinica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.2380

zbMATH Keywords

clusteringstochastic block modelconsistencyhigh dimensionalregularization

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Probabilistic graphical models (62H22) Applications of statistics to social sciences (62P25)

Abstract: In the high dimensional Stochastic Blockmodel for a random network, the number of clusters (or blocks) K grows with the number of nodes N. Two previous studies have examined the statistical estimation performance of spectral clustering and the maximum likelihood estimator under the high dimensional model; neither of these results allow K to grow faster than N^{1/2}. We study a model where, ignoring log terms, K can grow proportionally to N. Since the number of clusters must be smaller than the number of nodes, no reasonable model allows K to grow faster; thus, our asymptotic results are the "highest" dimensional. To push the asymptotic setting to this extreme, we make additional assumptions that are motivated by empirical observations in physical anthropology (Dunbar, 1992), and an in depth study of massive empirical networks (Leskovec et al 2008). Furthermore, we develop a regularized maximum likelihood estimator that leverages these insights and we prove that, under certain conditions, the proportion of nodes that the regularized estimator misclusters converges to zero. This is the first paper to explicitly introduce and demonstrate the advantages of statistical regularization in a parametric form for network analysis.

Recommendations

• Stochastic blockmodels with a growing number of classes
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of spectral clustering in stochastic block models
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Likelihood-based model selection for stochastic block models

Cited in

(9)

• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• Large-scale estimation of random graph models with local dependence
• Matrix estimation by universal singular value thresholding
• Nonreconstruction of high-dimensional stochastic block model with bounded degree
• Consistent structure estimation of exponential-family random graph models with block structure
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Exact clustering of weighted graphs via semidefinite programming
• The hierarchy of block models
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models

This page was built for publication: The highest dimensional stochastic blockmodel with a regularized estimator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3195174)