Finding one community in a sparse graph
From MaRDI portal
Publication:892403
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)
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: 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. 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 and fail for (with , 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 .
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
Cites work
- scientific article; zbMATH DE number 1220667 (Why is no real title available?)
- scientific article; zbMATH DE number 1303602 (Why is no real title available?)
- 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)- Finding a large submatrix of a Gaussian random matrix
- Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
- Asymptotic mutual information for the balanced binary stochastic block model
- Parallel tempering for the planted clique problem
- Tensor clustering with planted structures: statistical optimality and computational limits
- Convex optimization for the densest subgraph and densest submatrix problems
- Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
- 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 and stochastic block models: recent developments
- Global and individualized community detection in inhomogeneous multilayer networks
- The overlap gap property in principal submatrix recovery
- Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
- Community detection in sparse random networks
- Community detection on Euclidean random graphs
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)
