Selecting the Number of Communities in Stochastic Blockmodels

• Activity Number: 439
• Type: Contributed
• Date/Time: Tuesday, August 6, 2013 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Diego Franco Saldana*+ and Yi Yu and Yang Feng
• Companies: Columbia University and University of Cambridge and Columbia University
• Keywords: Stochastic blockmodel ; Community detection ; Composite BIC ; Likelihood-based inference ; Spectral clustering ; Model selection

Abstract

Stochastic blockmodels for network data have been widely used to model community structure within social networks. Under this framework, the community detection problem consists in assigning each node in the network to its corresponding "true" community or cluster. When the number of clusters K in the network is allowed to grow with the number of nodes, both likelihood-based procedures as well as spectral clustering algorithms exhibit a vanishing fraction of misclustered nodes. However, for finite samples, both of these fitting procedures assume the number of communities K is given. In this paper, we propose a composite BIC strategy for selecting the total number of communities in the stochastic blockmodel. Corresponding degree-of-freedom calculations for the stochastic blockmodel parameters are derived, and consistency results are established for choosing the true K in both the likelihood-based method and the spectral clustering procedure. We illustrate our composite BIC method for choosing K in three simulated networks and in two scientific collaboration networks.