# Community Detection in the Multi-View Stochastic Block Model

arXiv: https://arxiv.org/abs/2401.09510 · HTML: https://mlsanity.com/paper/2401.09510/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 39 references that are in the map.
- First posted on arXiv 17 Jan 2024.

## Builds on (most cited first, 20 of 20)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Multilayer Networks](https://mlsanity.com/paper/1309.7233/) (2013)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [Community detection, link prediction, and layer interdependence in multilayer networks](https://mlsanity.com/paper/1701.01369/) (2017)
- [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Correlated randomly growing graphs](https://mlsanity.com/paper/2004.13537/) (2020)
- [Optimal De-Anonymization in Random Graphs with Community Structure](https://mlsanity.com/paper/1602.01409/) (2016)
- [On the Minimax Misclassification Ratio of Hypergraph Community Detection](https://mlsanity.com/paper/1802.00926/) (2018)
- [Global and Individualized Community Detection in Inhomogeneous Multilayer Networks](https://mlsanity.com/paper/2012.00933/) (2020)
- [Clustering Network Layers With the Strata Multilayer Stochastic Block Model](https://mlsanity.com/paper/1507.01826/) (2015)
- [Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence](https://mlsanity.com/paper/1509.06418/) (2015)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs](https://mlsanity.com/paper/2006.04373/) (2020)
- [Semidefinite Programming for Community Detection with Side Information](https://mlsanity.com/paper/2105.02816/) (2021)
- [Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables](https://mlsanity.com/paper/2301.04088/) (2023)

## Built on by (most cited first, 1 of 1)

- [A Spectral Framework for Tracking Communities in Evolving Networks](https://mlsanity.com/paper/2412.07378/) (2024)

## Abstract (arXiv)

This paper considers the problem of community detection on multiple potentially correlated graphs from an information-theoretical perspective. We first put forth a random graph model, called the multi-view stochastic block model (MVSBM), designed to generate correlated graphs on the same set of nodes (with cardinality n). The n nodes are partitioned into two disjoint communities of equal size. The presence or absence of edges in the graphs for each pair of nodes depends on whether the two nodes belong to the same community or not. The objective for the learner is to recover the hidden communities with observed graphs. Our technical contributions are two-fold: (i) We establish an information-theoretic upper bound (Theorem~1) showing that exact recovery of community is achievable when the model parameters of MVSBM exceed a certain threshold. (ii) Conversely, we derive an information-theoretic lower bound (Theorem~2) showing that when the model parameters of MVSBM fall below the aforementioned threshold, then for any estimator, the expected number of misclassified nodes will always be greater than one. Our results for the MVSBM recover several prior results for community detection in the standard SBM as well as in multiple independent SBMs as special cases.