Reconstruction and estimation in the planted partition model

DOI10.1007/s00440-014-0576-6zbMath1320.05113arXiv1202.1499OpenAlexW1974967023MaRDI 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

Social networks; opinion dynamics (91D30) Random graphs (graph-theoretic aspects) (05C80) Stochastic network models in operations research (90B15) Applications of branching processes (60J85)

Related Items

Testing community structure for hypergraphs, A likelihood-ratio type test for stochastic block models with bounded degrees, An impossibility result for reconstruction in the degree-corrected stochastic block model, On the Complexity of Random Satisfiability Problems with Planted Solutions, Bayesian community detection, Storage capacity in symmetric binary perceptrons, Unnamed Item, Hypothesis testing in sparse weighted stochastic block model, Gravitational community detection by predicting diameter, Application of the information-percolation method to reconstruction problems on graphs, Statistical limits of spiked tensor models, Joint Community Detection and Rotational Synchronization via Semidefinite Programming, Find Your Place: Simple Distributed Algorithms for Community Detection, PageRank Nibble on the sparse directed stochastic block model, Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems, Community detection in the sparse hypergraph stochastic block model, Power enhancement and phase transitions for global testing of the mixed membership stochastic block model, Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs, Testing correlation of unlabeled random graphs, Combinatorial statistics and the sciences, Unnamed Item, Random geometric graph: some recent developments and perspectives, Mutual information for the sparse stochastic block model, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Asymptotic uncertainty quantification for communities in sparse planted bi-section models, Learning sparse graphons and the generalized Kesten-Stigum threshold, Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks, Community Detection in Censored Hypergraph, Spectral norm bounds for block Markov chain random matrices, New mathematical techniques in information theory. Abstracts from the workshop held March 13--19, 2022, Estimation of spillover effects with matched data or longitudinal network data, ADDITIVITY PROPERTIES OF SOFIC ENTROPY AND MEASURES ON MODEL SPACES, Modularity of Erdős‐Rényi random graphs, Phase transitions for detecting latent geometry in random graphs, Bethe states of random factor graphs, The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Optimal couplings between sparse block models, Testing goodness of fit of random graph models, Disentangling group and link persistence in dynamic stochastic block models, Charting the replica symmetric phase, Unnamed Item, Unnamed Item, 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, Community Detection and Stochastic Block Models, Clustering in block Markov chains, Spin systems on Bethe lattices, Estimating the number of communities by spectral methods, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time, Convex relaxation methods for community detection, Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing, Nonreconstruction of high-dimensional stochastic block model with bounded degree, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, Detecting a planted community in an inhomogeneous random graph, Limit theorems for eigenvectors of the normalized Laplacian for random graphs, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Consistent structure estimation of exponential-family random graph models with block structure, Weighted community detection and data clustering using message passing, Generalized quasirandom properties of expanding graph sequences, Fluctuation of the free energy of Sherrington-Kirkpatrick model with Curie-Weiss interaction: the paramagnetic regime, Birds of a feather or opposites attract - effects in network modelling, 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, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, The number of solutions for random regular NAE-SAT, Optimal adaptivity of signed-polygon statistics for network testing, Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models, The replica symmetric phase of random constraint satisfaction problems, The all-or-nothing phenomenon in sparse linear regression, Mean-field theory of graph neural networks in graph partitioning, Optimal signal detection in some spiked random matrix models: likelihood ratio tests and linear spectral statistics, Unnamed Item, Unnamed Item, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Global and individualized community detection in inhomogeneous multilayer networks, Eigenvalues of the non-backtracking operator detached from the bulk

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