Finding one community in a sparse graph

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

Cited In (15)

• 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
• Community detection and stochastic block models: recent developments
• Finding a large submatrix of a Gaussian random matrix
• Tensor clustering with planted structures: statistical optimality and computational limits
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• Fundamental limits of symmetric low-rank matrix estimation
• Community detection on Euclidean random graphs
• Parallel tempering for the planted clique problem
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• The overlap gap property in principal submatrix recovery
• Convex optimization for the densest subgraph and densest submatrix problems
• Community detection in sparse random networks

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)