Contiguity and non-reconstruction results for planted partition models: the dense case

DOI10.1214/17-EJP128zbMath1387.05230arXiv1609.02854MaRDI QIDQ1748922

Debapratim Banerjee

Publication date: 15 May 2018

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionthresholdcommunity detectionstochastic block modellinear statisticsplanted partition modelrandom network

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (12)

Testing community structure for hypergraphs ⋮ A likelihood-ratio type test for stochastic block models with bounded degrees ⋮ Power enhancement and phase transitions for global testing of the mixed membership stochastic block model ⋮ Characterization of expansion-related properties of modular graphs ⋮ Fundamental limits of detection in the spiked Wigner model ⋮ Asymptotic uncertainty quantification for communities in sparse planted bi-section models ⋮ Critical window of the symmetric perceptron ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Fluctuation of the free energy of Sherrington-Kirkpatrick model with Curie-Weiss interaction: the paramagnetic regime ⋮ Optimal adaptivity of signed-polygon statistics for network testing ⋮ Permutation Tests for Infection Graphs ⋮ Optimal signal detection in some spiked random matrix models: likelihood ratio tests and linear spectral statistics

Uses Software

• STRUCTURE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consistency thresholds for the planted bisection model
• Belief propagation, robust reconstruction and optimal recovery of block models
• Reconstruction and estimation in the planted partition model
• Spectral clustering and the high-dimensional stochastic blockmodel
• A CLT for a band matrix model
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Hierarchical clustering schemes
• Testing for high-dimensional geometry in random graphs
• A nonparametric view of network models and Newman–Girvan and other modularities
• Exact Recovery in the Stochastic Block Model
• The solution of some random NP-hard problems in polynomial expected time
• Graph Partitioning via Adaptive Spectral Techniques
• An Introduction to Random Matrices
• Random graph models of social networks
• Community Detection and Stochastic Block Models
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Largest eigenvalue of large random block matrices: A combinatorial approach
• A Note on Asymptotic Joint Normality
• The Evaluation of the Collision Matrix

This page was built for publication: Contiguity and non-reconstruction results for planted partition models: the dense case