Stochastic blockmodels and community structure in networks

By Brian Karrer, Mark Newman. 2010

2,147 citations recorded by the source corpus.

Stochastic blockmodels have been proposed as a tool for detecting community structure in networks as well as for generating synthetic networks for use as benchmarks. Most blockmodels, however, ignore variation in vertex degree, making them unsuitable for applications to real-world networks, which typically display broad degree distributions that can significantly affect the results. Here we demonstrate how the generalization of blockmodels to incorporate this missing element leads to an improved objective function for community detection in complex networks. We also propose a heuristic algorithm for community detection using this objective function or its non-degree-corrected counterpart and show that the degree-corrected version dramatically outperforms the uncorrected one in both real-world and synthetic networks.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

How researchers see this paper

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

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

NetGAN: Generating Graphs via Random Walks (2018, methodology): “We compare to the following baselines: configuration model (Molloy & Reed, 1995), degree-corrected stochastic blockmodel (DC-SBM) (Karrer & Newman, 2011), exponential random graph model (ERGM) (Holland & Leinhardt, 1981) and the block twolevel Erdős-Réniy random graph model (BTER) (Seshadhri et…”
Community detection and stochastic block models: recent developments (2017, background): “ Section3.5); Degree-corrected SBMs: allowing for a degree parameter for each vertex that scales the edge probabilities in order to makes expected degrees match the observed degrees (see for example [KN11]); Overlapping SBMs: allowing for the communities to overlap, such as in the mixedmembership SB”
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery (2015, background): “Recently, similar phenomena have been identified for the stochastic block model (SBM), one of the most popular network models exhibiting community structures [20], [21], [22], [23], [24], [25].”
Handbook of Big Data (2016, methodology): “In Lunagomez and Airoldi (2014), the authors tackle the problem of jointly modeling the sampling mechanism for causal inference as well as the underlying network on which the data was collected. The model selected for the network in this chapter is the simple Erdos–Renyi model that depends on a sing”
Overlapping Communities Explain Core–Periphery Organization of Networks (2014, background): “Stochastic Block Models We show that three variants of stochastic block models are unable to correctly discover communities with dense overlaps: the traditional stochastic block model [45], the degree-corrected stochastic block model [48], and the MMSB model [7].”
Structure and inference in annotated networks (2015, methodology): “This leads to an iterative algorithm analogous to the EM algorithm in which one computes the Qsu j from (28) and then, using those values, computes the maximum with respect to gsj by differentiating the right-hand NATURE COMMUNICATIONS | DOI: 10.”
Consistency of community detection in networks under degree-corrected stochastic block models (2011, methodology): “The results in Figure 4 show that the degree-corrected block model likelihood and Newman–Girvan modularity still perform well, which suggests that the discreteness of θ is not a crucial assumption.”
FAST COMMUNITY DETECTION BY SCORE (2012, background): “Write for short Note that (cid:8) θ (k) can be interpreted as the overall degree intensities of the k th community.”
Communities, modules and large-scale structure in networks (2011, positive): “Figure 4b shows a different fit to the same network using now a ‘degree-corrected’ block model that allows for widely varying degrees 49 .”
An efficient and principled method for detecting communities in networks (2011, background): “[18].)”
Measuring Scholarly Impact (2014, methodology): “Block models Methods based on block models identify blocks of nodes (Gopalan & Blei, 2013; Karrer & Newman, 2011; Peixoto, 2013) with common properties.”
Exact Recovery in the Stochastic Block Model (2014, background): “More specifically, the stochastic block model has been at the center of the attention in a large body of literature [14]–[16], [19], [24], [26], [29], [30], [32], [33], [35], [38], [39], as a testbed for algorithms (see [10] for a survey) as well as a scalable model for large data sets (see [22] and”
Designing Random Graph Models Using Variational Autoencoders With Applications to Chemical Design (2018, methodology): “Since the seminal random graph model by Erdos-Rényi [12], where each pair of nodes is connected by an edge with probability p, there is a long history of random graph models in the literature [40, 41, 7, 21, 29, 28, 18].”