Finding one community in a sparse graph

DOI10.1007/S10955-015-1338-2zbMATH Open1327.82091arXiv1502.05680OpenAlexW1692749124MaRDI QIDQ892403FDOQ892403

Authors: Andrea Montanari 

Publication date: 19 November 2015

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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 ${mdeg}_{min}-{mdeg}_{mout}>sqrt{mdeg}_{mout}/e$ and fail for ${mdeg}_{min}-{mdeg}_{mout}<sqrt{mdeg}_{mout}/e$ (with ${mdeg}_{min}$, ${mdeg}_{mout}$ 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 ${mdeg}_{min}-{mdeg}_{mout}<sqrt{mdeg}_{mout}/e$.

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

Recommendations

• Community detection in sparse random networks
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• Community detection in the sparse hypergraph stochastic block model
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models

zbMATH Keywords

phase transitionsstatistical inferencerandom graphspolynomial algorithmscavity methodhidden clique

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Phase transitions (general) in equilibrium statistical mechanics (82B26) Dynamic and nonequilibrium phase transitions (general) in statistical mechanics (82C26) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Cites Work

• Title not available (Why is that?)
• A proof of the block model threshold conjecture
• Spectral redemption in clustering sparse networks
• Optimal Transport
• Community detection in dense random networks
• Finding Hidden Cliques in Linear Time with High Probability
• Community detection in sparse random networks
• Matrix Completion From a Few Entries
• Phase transitions for the cavity approach to the clique problem on random graphs
• Some spin glass ideas applied to the clique problem
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• Information, Physics, and Computation
• Limits of locally-globally convergent graph sequences
• On the solution-space geometry of random constraint satisfaction problems
• Statistical Physics of Spin Glasses and Information Processing
• Spectral techniques applied to sparse random graphs
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Finding and certifying a large hidden clique in a semirandom graph
• Graph partitioning via adaptive spectral techniques
• Modern Coding Theory
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Finding large average submatrices in high dimensional data
• Limits of local algorithms over sparse random graphs
• Quiet planting in the locked constraint satisfaction problems
• On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
• Local algorithms for independent sets are half-optimal
• Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration
• Title not available (Why is that?)

Cited In (13)

• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Asymptotic mutual information for the balanced binary stochastic block model
• Global and individualized community detection in inhomogeneous multilayer networks
• Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information
• Finding a large submatrix of a Gaussian random matrix
• Tensor clustering with planted structures: statistical optimality and computational limits
• Fundamental limits of symmetric low-rank matrix estimation
• Parallel tempering for the planted clique problem
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Community Detection and Stochastic Block Models
• The overlap gap property in principal submatrix recovery
• Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time
• Convex optimization for the densest subgraph and densest submatrix problems

Uses Software

• LAS

This page was built for publication: Finding one community in a sparse graph

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