  The problem of community detection with two equal-sized communities is
closely related to the minimum graph bisection problem over certain random
graph models. In the stochastic block model distribution over networks with
community structure, a well-known semidefinite programming (SDP) relaxation of
the minimum bisection problem recovers the underlying communities whenever
possible. Motivated by their superior scalability, we study the theoretical
performance of linear programming (LP) relaxations of the minimum bisection
problem for the same random models. We show that unlike the SDP relaxation that
undergoes a phase transition in the logarithmic average-degree regime, the LP
relaxation exhibits a transition from recovery to non-recovery in the linear
average-degree regime. We show that in the logarithmic average-degree regime,
the LP relaxation fails in recovering the planted bisection with high
probability.
