Semidefinite programs on sparse random graphs and their application to community detection
From MaRDI portal
Publication:5361882
DOI10.1145/2897518.2897548zbMath1376.90043arXiv1504.05910OpenAlexW2216459995MaRDI QIDQ5361882
Subhabrata Sen, Andrea Montanari
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.05910
Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items (32)
Testing community structure for hypergraphs ⋮ A likelihood-ratio type test for stochastic block models with bounded degrees ⋮ Iterative algorithm for discrete structure recovery ⋮ Optimal Bipartite Network Clustering ⋮ Disordered systems insights on computational hardness ⋮ Information-theoretic thresholds from the cavity method ⋮ Hypothesis testing in sparse weighted stochastic block model ⋮ Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks ⋮ Rate optimal Chernoff bound and application to community detection in the stochastic block models ⋮ Convexified modularity maximization for degree-corrected stochastic block models ⋮ Unnamed Item ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ Phase transitions in semidefinite relaxations ⋮ Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization ⋮ TAP free energy, spin glasses and variational inference ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ Optimal couplings between sparse block models ⋮ Optimization of the Sherrington--Kirkpatrick Hamiltonian ⋮ A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian ⋮ Phase transition in random tensors with multiple independent spikes ⋮ On semidefinite relaxations for the block model ⋮ Community Detection and Stochastic Block Models ⋮ Convex relaxation methods for community detection ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Covariate Regularized Community Detection in Sparse Graphs ⋮ Robust group synchronization via cycle-edge message passing ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model ⋮ Graph Powering and Spectral Robustness
This page was built for publication: Semidefinite programs on sparse random graphs and their application to community detection
