Overlapping stochastic block models with application to the French political blogosphere

Abstract

Complex systems in nature and in society are often represented as networks, describing the rich set of interactions between objects of interest. Many deterministic and probabilistic clustering methods have been developed to analyze such structures. Given a network, almost all of them partition the vertices into disjoint clusters, according to their connection profile. However, recent studies have shown that these techniques were too restrictive and that most of the existing networks contained overlapping clusters. To tackle this issue, we present in this paper the Overlapping Stochastic Block Model. Our approach allows the vertices to belong to multiple clusters, and, to some extent, generalizes the well-known Stochastic Block Model [Nowicki and Snijders (2001)]. We show that the model is generically identifiable within classes of equivalence and we propose an approximate inference procedure, based on global and local variational techniques. Using toy data sets as well as the French Political Blogosphere network and the transcriptional network of Saccharomyces cerevisiae, we compare our work with other approaches.

Published in at http://dx.doi.org/10.1214/10-AOAS382 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• Uncovering the overlapping community structure of complex networks in nature and society
• Mixture models and exploratory analysis in networks
• Identifiability of parameters in latent structure models with many observed variables
• A Bayesian Approach to Network Modularity
• Mixed membership analysis of high-throughput interaction studies: Relational data

Cited by in corpus (16)

• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• The Stochastic Topic Block Model for the Clustering of Vertices in Networks with Textual Edges
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Mixed-Membership of Experts Stochastic Blockmodel
• The random subgraph model for the analysis of an ecclesiastical network in Merovingian Gaul
• Convergence of the groups posterior distribution in latent or stochastic block models
• Overlapping community detection in signed networks
• Mixing patterns and individual differences in networks
• Variational Bayes model averaging for graphon functions and motif frequencies inference in W-graph models
• Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
• Node Copying: A Random Graph Model for Effective Graph Sampling
• A Hidden Challenge of Link Prediction: Which Pairs to Check?
• Dynamic degree-corrected blockmodels for social networks: a nonparametric approach
• Overlapping community detection in networks via sparse spectral decomposition