Community detection thresholds and the weak Ramanujan property

DOI10.1145/2591796.2591857zbMath1315.68210arXiv1311.3085OpenAlexW2023348178MaRDI QIDQ5259605

Laurent Massoulié

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

phase transitioncommunity detectionspectral clusteringspectral separation

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Random graphs (graph-theoretic aspects) (05C80) Learning and adaptive systems in artificial intelligence (68T05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

An impossibility result for reconstruction in the degree-corrected stochastic block model, Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM), Spectral gap in random bipartite biregular graphs and applications, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Optimal Bipartite Network Clustering, Iterative Collaborative Filtering for Sparse Matrix Estimation, On model selection for dense stochastic block models, Information-theoretic thresholds from the cavity method, MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass, Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks, 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, 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, Detection thresholds in very sparse matrix completion, Community detection in the sparse hypergraph stochastic block model, Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs, Unnamed Item, Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models, Entrywise eigenvector analysis of random matrices with low expected rank, Mutual information for the sparse stochastic block model, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Phase transitions in semidefinite relaxations, Asymptotic uncertainty quantification for communities in sparse planted bi-section models, Learning sparse graphons and the generalized Kesten-Stigum threshold, Spectral norm bounds for block Markov chain random matrices, Asymptotic mutual information for the balanced binary stochastic block model, Unnamed Item, Hidden Hamiltonian Cycle Recovery via Linear Programming, Recovering Structured Probability Matrices, Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers, Notes on computational-to-statistical gaps: predictions using statistical physics, Bethe states of random factor graphs, 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, Charting the replica symmetric phase, Maximum likelihood estimation of sparse networks with missing observations, Unnamed Item, On semidefinite relaxations for the block model, Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs, Charting the replica symmetric phase, Random Laplacian matrices and convex relaxations, Clustering in block Markov chains, Estimating the number of communities by spectral methods, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time, Spectral gap of sparse bistochastic matrices with exchangeable rows, Optimization via low-rank approximation for community detection in networks, 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, Detecting a planted community in an inhomogeneous random graph, The spectral gap of sparse random digraphs, Community detection in sparse networks via Grothendieck's inequality, Community detection in degree-corrected block models, Network Cross-Validation for Determining the Number of Communities in Network Data, Consistent nonparametric estimation for heavy-tailed sparse graphs, Community detection with dependent connectivity, Exact recovery in the hypergraph stochastic block model: a spectral algorithm, Exact recovery in the Ising blockmodel, On the computational tractability of statistical estimation on amenable 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, Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models, Non-convex exact community recovery in stochastic block model, Eigenvalues of random lifts and polynomials of random permutation matrices, Mean-field theory of graph neural networks in graph partitioning, 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, Eigenvalues of the non-backtracking operator detached from the bulk, Bootstrap percolation on the stochastic block model, Graph Powering and Spectral Robustness

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography