Consistency of community detection in networks under degree-corrected stochastic block models

By Yunpeng Zhao, Elizaveta Levina, Ji Zhu. 2011

459 citations recorded by the source corpus.

Community detection is a fundamental problem in network analysis, with applications in many diverse areas. The stochastic block model is a common tool for model-based community detection, and asymptotic tools for checking consistency of community detection under the block model have been recently developed. 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 stochastic block model was proposed to address this shortcoming and allows variation in node degrees within a community while preserving the overall block community structure. In this paper we establish general theory for checking consistency of community detection under the degree-corrected stochastic block model and compare several community detection criteria under both the standard and the degree-corrected models. We show which criteria are consistent under which models and constraints, as well as compare their relative performance in practice. 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. On the other hand, in practice, the degree correction involves estimating many more parameters, and empirically we find it is only worth doing if the node degrees within communities are indeed highly variable. We illustrate the methods on simulated networks and on a network of political blogs.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/e78f0e0dbb84c1a9f9d9bc31ca1c25ac56bcb2a2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning (2021, background): “DCSBM DCSBM (2012) [50] Introduce expected values to basic SBM to adapt multi-edges and self-edges contained in social networks.”
Pseudo-likelihood methods for community detection in large sparse networks (2012, background): “ within communities, the block model can provide a poor ﬁt, essentially dividing the nodes into low-degree and high-degree groups. This has been both observed empirically [21] and supported by theory [37]. The extension of the block model designed to cope with this situation, the degree-corrected bl”
Consistency of spectral clustering in stochastic block models (2013, methodology): “See, in particular, modularity maximization (Newman & Girvan, 2004), likelihood methods (Bickel & Chen, 2009; Choi et al., 2012; Zhao et al., 2012; Amini et al., 2012; Celisse et al., 2012), method of moments (Anandkumar et al., 2013), belief propagation (Decelle et al., 2011), convex optimization…”