Efficient inference of overlapping communities in complex networks
This addresses the challenge of modeling overlapping communities in networks, which is important for social network analysis and other domains, though it appears incremental as an extension of existing stochastic blockmodel approaches.
The paper tackles the problem of inferring overlapping communities in complex networks by proposing a multiple-networks stochastic blockmodel (MNSBM) that separates networks into subnetworks for easier structure inference. Results show effective recovery of planted structure in synthetic networks and encouraging link prediction performance on real-world datasets.
We discuss two views on extending existing methods for complex network modeling which we dub the communities first and the networks first view, respectively. Inspired by the networks first view that we attribute to White, Boorman, and Breiger (1976)[1], we formulate the multiple-networks stochastic blockmodel (MNSBM), which seeks to separate the observed network into subnetworks of different types and where the problem of inferring structure in each subnetwork becomes easier. We show how this model is specified in a generative Bayesian framework where parameters can be inferred efficiently using Gibbs sampling. The result is an effective multiple-membership model without the drawbacks of introducing complex definitions of "groups" and how they interact. We demonstrate results on the recovery of planted structure in synthetic networks and show very encouraging results on link prediction performances using multiple-networks models on a number of real-world network data sets.