Finding one community in a sparse graph

DOI10.1007/s10955-015-1338-2zbMath1327.82091arXiv1502.05680OpenAlexW1692749124MaRDI QIDQ892403

Andrea Montanari

Publication date: 19 November 2015

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

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

zbMATH Keywords

phase transitionsrandom graphsstatistical inferencepolynomial algorithmscavity methodhidden clique

Mathematics Subject Classification ID

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

Related Items

Tensor clustering with planted structures: statistical optimality and computational limits, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Asymptotic mutual information for the balanced binary stochastic block model, Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications, Parallel tempering for the planted clique problem, Fundamental limits of symmetric low-rank matrix estimation, Finding a large submatrix of a Gaussian random matrix, Community Detection and Stochastic Block Models, 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, The overlap gap property in principal submatrix recovery, Global and individualized community detection in inhomogeneous multilayer networks, Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model

Uses Software

• LAS

Cites Work

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