Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log*|V|) time
From MaRDI portal
Publication:4684942
DOI10.1017/jpr.2018.22zbMath1401.62085arXiv1510.02786OpenAlexW2962826276MaRDI QIDQ4684942
Jiaming Xu, Yihong Wu, Bruce Hajek
Publication date: 26 September 2018
Published in: Journal of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1510.02786
Estimation in multivariate analysis (62H12) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Detection theory in information and communication theory (94A13)
Related Items
Test dense subgraphs in sparse uniform hypergraph, Community Detection in Censored Hypergraph, Convex optimization for the densest subgraph and densest submatrix problems, Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- Reconstruction and estimation in the planted partition model
- Nuclear norm minimization for the planted clique and biclique problems
- Finding one community in a sparse graph
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Community detection in dense random networks
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Sum-of-squares Lower Bounds for Planted Clique
- Spectral redemption in clustering sparse networks
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Large Cliques Elude the Metropolis Process
- Community detection thresholds and the weak Ramanujan property
- Probability Inequalities for Sums of Bounded Random Variables
- Information Limits for Recovering a Hidden Community
- Finding Hidden Cliques in Linear Time with High Probability
- Probability and Computing
- The Rotation of Eigenvectors by a Perturbation. III
- Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
