Side Information in the Binary Stochastic Block Model: Exact Recovery
arXiv:1708.04972
Abstract
In the community detection problem, one may have access to additional observations (side information) about the label of each node. This paper studies the effect of the quality and quantity of side information on the phase transition of exact recovery in the binary symmetric stochastic block model (SBM) with nodes. When the side information consists of the label observed through a binary symmetric channel with crossover probability , and when , it is shown that side information has a positive effect on phase transition; the new phase transition under this condition is characterized. When is constant or approaches zero sufficiently slowly, i.e., , it is shown that side information does not help exact recovery. When the side information consists of the label observed through a binary erasure channel with parameter , and when , it is shown that side information improves exact recovery and the new phase transition is characterized. If , then it is shown that side information is not helpful. The results are then generalized to an arbitrary side information of finite cardinality. Necessary and sufficient conditions are derived for exact recovery that are tight, except for one special case under -ary side information. An efficient algorithm that incorporates the effect of side information is proposed that uses a partial recovery algorithm combined with a local improvement procedure. Sufficient conditions are derived for exact recovery under this efficient algorithm.
arXiv commentWithdrawn due to errors
References in corpus (16)
- Community structure in social and biological networks
- Community detection in graphs
- Community detection algorithms: a comparative analysis
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Phase transition in the detection of modules in sparse networks
- Structure and inference in annotated networks
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
- A Tensor Approach to Learning Mixed Membership Community Models
- Community Detection via Random and Adaptive Sampling
- Inference via Message Passing on Partially Labeled Stochastic Block Models
- Community Detection in Networks with Node Features
- Community detection thresholds and the weak Ramanujan property
- Global and Local Information in Clustering Labeled Block Models
- Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs
- The Power of Side-information in Subgraph Detection