Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
arXiv:2107.06767
Abstract
We consider the task of learning latent community structure from multiple correlated networks. First, we study the problem of learning the latent vertex correspondence between two edge-correlated stochastic block models, focusing on the regime where the average degree is logarithmic in the number of vertices. We derive the precise information-theoretic threshold for exact recovery: above the threshold there exists an estimator that outputs the true correspondence with probability close to 1, while below it no estimator can recover the true correspondence with probability bounded away from 0. As an application of our results, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.
arXiv comment42 pages, 4 figures
References in corpus (14)
- Community detection in graphs
- De-anonymizing Social Networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Covariate-assisted spectral clustering
- Consistent estimation of dynamic and multi-layer block models
- Inference for multiple heterogeneous networks with a common invariant subspace
- Exact alignment recovery for correlated Erdős-Rényi graphs
- Contextual Stochastic Block Models
- From tree matching to sparse graph alignment
- Impossibility of Partial Recovery in the Graph Alignment Problem
- Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
- Null Models and Community Detection in Multi-Layer Networks
- On the Simultaneous Preservation of Privacy and Community Structure in Anonymized Networks
- Community Detection with Contextual Multilayer Networks