Community detection in sparse networks via Grothendieck's inequality
Preprint
Abstract
We present a simple and flexible method to prove consistency of semidefinite optimization problems on random graphs. The method is based on Grothendieck's inequality. Unlike the previous uses of this inequality that lead to constant relative accuracy, we achieve arbitrary relative accuracy by leveraging randomness. We illustrate the method with the problem of community detection in sparse networks. Despite much progress in the recent years, almost no rigorous results have been known for totally sparse networks -- those with bounded average degrees. We demonstrate that even in this regime, various natural semidefinite programs can be used to recover the community structure up to an arbitrarily small fraction of misclassified vertices. The method is general; it can be applied to a variety of stochastic models of networks and semidefinite programs.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Grothendieck‐Type Inequalities in Combinatorial OptimizationCommunications on Pure and Applied Mathematics, 2012
- Nuclear norm minimization for the planted clique and biclique problemsMathematical Programming, 2011
- Singular vectors under random perturbationRandom Structures & Algorithms, 2011
- A nonparametric view of network models and Newman–Girvan and other modularitiesProceedings of the National Academy of Sciences, 2009
- Graph Partitioning via Adaptive Spectral TechniquesCombinatorics, Probability and Computing, 2009
- Exploring complex networksNature, 2001
- Semidefinite relaxation and nonconvex quadratic optimizationOptimization Methods and Software, 1998
- Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block StructureJournal of Classification, 1997
- The solution of some random NP-hard problems in polynomial expected timeJournal of Algorithms, 1989
- Graph bisection algorithms with good average case behaviorCombinatorica, 1987