Reconstruction and estimation in the planted partition model

DOI10.1007/s00440-014-0576-6zbMath1320.05113arXiv1202.1499MaRDI QIDQ495549

Joe Neeman, Allan Sly, Elchanan Mossel

Publication date: 14 September 2015

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

Mathematics Subject Classification ID

91D30: Social networks; opinion dynamics

05C80: Random graphs (graph-theoretic aspects)

90B15: Stochastic network models in operations research

60J85: Applications of branching processes

Related Items

Unnamed Item, On the Complexity of Random Satisfiability Problems with Planted Solutions, Community Detection and Stochastic Block Models, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time, Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models, Unnamed Item, Weighted community detection and data clustering using message passing, Find Your Place: Simple Distributed Algorithms for Community Detection, Modularity of Erdős‐Rényi random graphs, Optimal couplings between sparse block models, Generalized quasirandom properties of expanding graph sequences, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Mean-field theory of graph neural networks in graph partitioning, An impossibility result for reconstruction in the degree-corrected stochastic block model, Bayesian community detection, Bethe states of random factor graphs, Testing goodness of fit of random graph models, Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs, Contiguity and non-reconstruction results for planted partition models: the dense case, Charting the replica symmetric phase, Limit theorems for eigenvectors of the normalized Laplacian for random graphs, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Clustering in block Markov chains, Spin systems on Bethe lattices, Application of the information-percolation method to reconstruction problems on graphs, Statistical limits of spiked tensor models, Phase transitions for detecting latent geometry in random graphs, Nonreconstruction of high-dimensional stochastic block model with bounded degree, Consistent structure estimation of exponential-family random graph models with block structure, Fluctuation of the free energy of Sherrington-Kirkpatrick model with Curie-Weiss interaction: the paramagnetic regime, Exact recovery in the hypergraph stochastic block model: a spectral algorithm, Exact recovery in the Ising blockmodel, Testing for high-dimensional geometry in random graphs, ADDITIVITY PROPERTIES OF SOFIC ENTROPY AND MEASURES ON MODEL SPACES, Disentangling group and link persistence in dynamic stochastic block models

Uses Software

• STRUCTURE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectral clustering and the high-dimensional stochastic blockmodel
• Reconstruction for the Potts model
• Some simplified NP-complete graph problems
• Nearest-neighbor walks with low predictability profile and percolation in \(2+\varepsilon\) dimensions
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• The Metropolis algorithm for graph bisection
• On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
• A clustering algorithm based on graph connectivity
• Broadcasting on trees and the Ising model.
• Hierarchical clustering schemes
• A nonparametric view of network models and Newman–Girvan and other modularities
• The solution of some random NP-hard problems in polynomial expected time
• Asymptotic equivalence and contiguity of some random graphs
• The Poisson Approximation to the Poisson Binomial Distribution
• A proof of Alon’s second eigenvalue conjecture and related problems
• Graph Partitioning via Adaptive Spectral Techniques
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Random graph models of social networks
• Community structure in social and biological networks
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• The phase transition in inhomogeneous random graphs
• Exploring complex networks
• A Limit Theorem for Multidimensional Galton-Watson Processes