Local algorithms for block models with side information

DOI10.1145/2840728.2840749zbMATH Open1334.68161arXiv1508.02344OpenAlexW2963040507MaRDI QIDQ2800554FDOQ2800554

Authors: Elchanan Mossel, Jiaming Xu 

Publication date: 15 April 2016

Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Abstract: There has been a recent interest in understanding the power of local algorithms for optimization and inference problems on sparse graphs. Gamarnik and Sudan (2014) showed that local algorithms are weaker than global algorithms for finding large independent sets in sparse random regular graphs. Montanari (2015) showed that local algorithms are suboptimal for finding a community with high connectivity in the sparse ErdH{o}s-R'enyi random graphs. For the symmetric planted partition problem (also named community detection for the block models) on sparse graphs, a simple observation is that local algorithms cannot have non-trivial performance. In this work we consider the effect of side information on local algorithms for community detection under the binary symmetric stochastic block model. In the block model with side information each of the $n$ vertices is labeled $+$ or $-$ independently and uniformly at random; each pair of vertices is connected independently with probability $a/n$ if both of them have the same label or $b/n$ otherwise. The goal is to estimate the underlying vertex labeling given 1) the graph structure and 2) side information in the form of a vertex labeling positively correlated with the true one. Assuming that the ratio between in and out degree $a/b$ is $Theta(1)$ and the average degree $(a+b)/2=n^{o(1)}$, we characterize three different regimes under which a local algorithm, namely, belief propagation run on the local neighborhoods, maximizes the expected fraction of vertices labeled correctly. Thus, in contrast to the case of symmetric block models without side information, we show that local algorithms can achieve optimal performance for the block model with side information.

Full work available at URL: https://arxiv.org/abs/1508.02344

Recommendations

• Belief propagation, robust reconstruction and optimal recovery of block models
• Local algorithms for graphs
• Limits of local algorithms over sparse random graphs
• Limits of local algorithms over sparse random graphs
• Global and local information in clustering labeled block models

zbMATH Keywords

community detectionrandom graphslocal algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• Local algorithms for graphs
• Mutual information for the sparse stochastic block model
• Global and local information in clustering labeled block models
• On the computational tractability of statistical estimation on amenable graphs
• Belief propagation, robust reconstruction and optimal recovery of block models

This page was built for publication: Local algorithms for block models with side information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800554)