Overlap graph clustering via successive removal

We study the following question: given a graph that represents interactions in a real system, can we group vertices with similar interests together? In many applications, we are often in a setting where vertices may potentially belong to multiple communities. In this paper, we propose an efficient algorithm for overlapping community detection which can successively recover all the communities. We provide theoretical guarantees on the performance of the algorithm by leveraging convex relaxation and exploiting the fact that in many networks there are often vertices that only belong to one community.