Model Selection for Degree-corrected Block Models
Autor: | Lenka Zdeborová, Yaojia Zhu, Jacob E. Jensen, Cosma Rohilla Shalizi, Pan Zhang, Cristopher Moore, Xiaoran Yan, Florent Krzakala |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2012 |
Předmět: |
Statistics and Probability
FOS: Computer and information sciences Mathematical optimization Physics - Physics and Society Computer science FOS: Physical sciences Machine Learning (stat.ML) Mathematics - Statistics Theory Latent variable Statistics Theory (math.ST) Physics and Society (physics.soc-ph) Belief propagation Article Stochastic block model Statistics - Machine Learning Statistical inference FOS: Mathematics Condensed Matter - Statistical Mechanics Probability Random graph Social and Information Networks (cs.SI) Statistical Mechanics (cond-mat.stat-mech) Model selection Statistics Statistical and Nonlinear Physics Computer Science - Social and Information Networks Degree distribution Statistics Probability and Uncertainty Network analysis |
Popis: | 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 undertaking 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 overall 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. |
Databáze: | OpenAIRE |
Externí odkaz: |