Stochastic blockmodels and community structure in networks

Abstract

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 distort 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.

11 pages, 3 figures

References in corpus (9)

• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mixture models and exploratory analysis in networks
• A Bayesian Approach to Network Modularity
• Community Detection as an Inference Problem
• Role models for complex networks

Cited by in corpus (2)

• Phase transition in the detection of modules in sparse networks
• Clustering and Classification in Text Collections Using Graph Modularity