  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.
