  The proliferation of models for networks raises challenging problems of model
selection: the data are sparse and globally dependent, and models are typically
high-dimensional and have large numbers of latent variables. Together, these
issues mean that the usual model-selection criteria do not work properly for
networks. We illustrate these challenges, and show one way to resolve them, by
considering the key network-analysis problem of dividing a graph into
communities or blocks of nodes with homogeneous patterns of links to the rest
of the network. The standard tool for doing this is the stochastic block model,
under which the probability of a link between two nodes is a function solely of
the blocks to which they belong. This imposes a homogeneous degree distribution
within each block; this can be unrealistic, so degree-corrected block models
add a parameter for each node, modulating its over-all degree. The choice
between ordinary and degree-corrected block models matters because they make
very different inferences about communities. We present the first principled
and tractable approach to model selection between standard and degree-corrected
block models, based on new large-graph asymptotics for the distribution of
log-likelihood ratios under the stochastic block model, finding substantial
departures from classical results for sparse graphs. We also develop
linear-time approximations for log-likelihoods under both the stochastic block
model and the degree-corrected model, using belief propagation. Applications to
simulated and real networks show excellent agreement with our approximations.
Our results thus both solve the practical problem of deciding on degree
correction, and point to a general approach to model selection in network
analysis.
