  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 any given relative accuracy by leveraging
randomness. We illustrate the method with the problem of community detection in
sparse networks, those with bounded average degrees. We demonstrate that even
in this regime, various simple and 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.
