On Consistency of Community Detection in Networks

• Activity Number: 73
• Type: Topic Contributed
• Date/Time: Sunday, August 4, 2013 : 4:00 PM to 5:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Yunpeng Zhao*+ and Liza Levina and Ji Zhu
• Companies: George Mason University and University of Michigan and University of Michigan
• Keywords: Network ; Stochastic blockmodels

Abstract

Community detection is a fundamental problem in network analysis. The stochastic block model is a common tool for model-based community detection. However, the block model is limited by its assumption that all nodes within a community are stochastically equivalent, and provides a poor fit to networks with hubs or highly varying node degrees within communities, which are common in practice. The degree-corrected block model was proposed to address this shortcoming, and allows variation in node degrees within a community while preserving the overall block model community structure. In this talk, we establish general theory for checking consistency of community detection under the degree-corrected block model, and compare several community detection criteria under both the standard and the degree-corrected block models. We find that methods based on the degree-corrected block model, which includes the standard block model as a special case, are consistent under a wider class of models; and that modularity-type methods require parameter constraints for consistency, whereas likelihood-based methods do not.