Publication:287720

DOI10.1214/16-EJP4185zbMath1336.05117arXiv1407.1591OpenAlexW2093663313MaRDI QIDQ287720

Elchanan Mossel, Allan Sly, Joe Neeman

Publication date: 23 May 2016

Published in: Electronic Journal of Probability, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the case of logarithmic average degree.

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

zbMATH Keywords

consistencyphase transitionrandom graphthresholdcommunity detectionstochastic block modelplanted partition modelrandom networkgraph clusteringminimum bisection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

Related Items (46)

Iterative algorithm for discrete structure recovery ⋮ Uniform estimation in stochastic block models is slow ⋮ Optimal Bipartite Network Clustering ⋮ Community detection with a subsampled semidefinite program ⋮ Frequentist validity of Bayesian limits ⋮ Model assisted variable clustering: minimax-optimal recovery and algorithms ⋮ Optimal rates for community estimation in the weighted stochastic block model ⋮ Rate optimal Chernoff bound and application to community detection in the stochastic block models ⋮ PageRank Nibble on the sparse directed stochastic block model ⋮ Unnamed Item ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ Mutual information for the sparse stochastic block model ⋮ Asymptotic uncertainty quantification for communities in sparse planted bi-section models ⋮ Unnamed Item ⋮ Spectral norm bounds for block Markov chain random matrices ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Recovering Structured Probability Matrices ⋮ Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding ⋮ Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Maximum likelihood estimation of sparse networks with missing observations ⋮ On semidefinite relaxations for the block model ⋮ Contiguity and non-reconstruction results for planted partition models: the dense case ⋮ Random Laplacian matrices and convex relaxations ⋮ Submatrix localization via message passing ⋮ Clustering in block Markov chains ⋮ Distribution-Free, Size Adaptive Submatrix Detection with Acceleration ⋮ 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 ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ Community detection in degree-corrected block models ⋮ On the estimation of latent distances using graph distances ⋮ Unnamed Item ⋮ Pair-matching: link prediction with adaptive queries ⋮ Rate-optimal graphon estimation ⋮ Community detection with dependent connectivity ⋮ Exact recovery in the hypergraph stochastic block model: a spectral algorithm ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ A spectral method for community detection in moderately sparse degree-corrected stochastic block models ⋮ Unnamed Item ⋮ Non-convex exact community recovery in stochastic block model ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ Global and individualized community detection in inhomogeneous multilayer networks ⋮ Detecting Overlapping Communities in Networks Using Spectral Methods

Uses Software

• Graphs

This page was built for publication: Consistency thresholds for the planted bisection model