Community Detection in the Labelled Stochastic Block Model

Abstract

We consider the problem of community detection from observed interactions between individuals, in the context where multiple types of interaction are possible. We use labelled stochastic block models to represent the observed data, where labels correspond to interaction types. Focusing on a two-community scenario, we conjecture a threshold for the problem of reconstructing the hidden communities in a way that is correlated with the true partition. To substantiate the conjecture, we prove that the given threshold correctly identifies a transition on the behaviour of belief propagation from insensitive to sensitive. We further prove that the same threshold corresponds to the transition in a related inference problem on a tree model from infeasible to feasible. Finally, numerical results using belief propagation for community detection give further support to the conjecture.

9 pages

References in corpus (2)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Stochastic Block Models and Reconstruction

Cited by in corpus (27)

• Statistical physics of inference: Thresholds and algorithms
• Nonparametric weighted stochastic block models
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Community Detection via Random and Adaptive Sampling
• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
• Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Clustering from Sparse Pairwise Measurements
• Community detection thresholds and the weak Ramanujan property
• Optimal Rates for Community Estimation in the Weighted Stochastic Block Model
• Regular Decomposition: an information and graph theoretic approach to stochastic block models
• A Semi-Definite Programming approach to low dimensional embedding for unsupervised clustering
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Fast Randomized Semi-Supervised Clustering
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method
• Community Detection with Node Attributes and its Generalization
• On the Log Partition Function of Ising Model on Stochastic Block Model
• Parallel and Distributed Approaches for Graph Based Semi-supervised Learning
• Uniqueness of communities in regular stochastic block models
• Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• Community Detection and Matrix Completion with Social and Item Similarity Graphs
• Information-theoretic Limits for Community Detection in Network Models
• Reconstruction in the Labeled Stochastic Block Model