Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection

Andrea Montanari, Subhabrata Sen

Denote by $A$ the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing $⟨A-E\{A\},X⟩$ over the set of positive s…