Finding One Community in a Sparse Graph

Abstract

We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subset of vertices. This can be regarded as a model for the problem of finding a tightly knitted community in a social network, or a cluster in a relational dataset. In this paper we present two sets of contributions: $(i)$ We use the cavity method from spin glass theory to derive an exact phase diagram for the reconstruction problem. In particular, as the difference in edge probability increases, the problem undergoes two phase transitions, a static phase transition and a dynamic one. $(ii)$ We establish rigorous bounds on the dynamic phase transition and prove that, above a certain threshold, a local algorithm (belief propagation) correctly identify most of the hidden set. Below the same threshold \emph{no local algorithm} can achieve this goal. However, in this regime the subset can be identified by exhaustive search. For small hidden sets and large average degree, the phase transition for local algorithms takes an intriguingly simple form. Local algorithms succeed with high probability for ${\mathrm{deg}}_{\mathrm{in}}-{\mathrm{deg}}_{\mathrm{out}}>\sqrt{{\mathrm{deg}}_{\mathrm{out}}/e}$ and fail for ${\mathrm{deg}}_{\mathrm{in}}-{\mathrm{deg}}_{\mathrm{out}}<\sqrt{{\mathrm{deg}}_{\mathrm{out}}/e}$ (with ${\mathrm{deg}}_{\mathrm{in}}$, ${\mathrm{deg}}_{\mathrm{out}}$ the average degrees inside and outside the community). We argue that spectral algorithms are also ineffective in the latter regime. It is an open problem whether any polynomial time algorithms might succeed for ${\mathrm{deg}}_{\mathrm{in}}-{\mathrm{deg}}_{\mathrm{out}}<\sqrt{{\mathrm{deg}}_{\mathrm{out}}/e}$.

30 pages, 8 pdf figures

References in corpus (5)

• Phase transition in the detection of modules in sparse networks
• Finding large average submatrices in high dimensional data
• Phase Transitions in Sparse PCA
• Computational Lower Bounds for Community Detection on Random Graphs
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time

Cited by in corpus (22)

• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Typology of phase transitions in Bayesian inference problems
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Glassy nature of the hard phase in inference problems
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
• Parallel Tempering for the planted clique problem
• The Overlap Gap Property in Principal Submatrix Recovery
• Universality of Computational Lower Bounds for Submatrix Detection
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Detecting and Localizing Anomalous Cliques in Inhomogeneous Networks using Egonets
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Finding a Large Submatrix of a Gaussian Random Matrix
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• The Power of Side-information in Subgraph Detection
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Streaming Belief Propagation for Community Detection
• Random Subgraph Detection Using Queries
• How Well Do Local Algorithms Solve Semidefinite Programs?