  The problem of detecting communities in a graph is maybe one the most studied
inference problems, given its simplicity and widespread diffusion among several
disciplines. A very common benchmark for this problem is the stochastic block
model or planted partition problem, where a phase transition takes place in the
detection of the planted partition by changing the signal-to-noise ratio.
Optimal algorithms for the detection exist which are based on spectral methods,
but we show these are extremely sensible to slight modification in the
generative model. Recently Javanmard, Montanari and Ricci-Tersenghi
(arXiv:1511.08769) have used statistical physics arguments, and numerical
simulations to show that finding communities in the stochastic block model via
semidefinite programming is quasi optimal. Further, the resulting semidefinite
relaxation can be solved efficiently, and is very robust with respect to
changes in the generative model. In this paper we study in detail several
practical aspects of this new algorithm based on semidefinite programming for
the detection of the planted partition. The algorithm turns out to be very
fast, allowing the solution of problems with $O(10^5)$ variables in few second
on a laptop computer.
