Provable Overlapping Community Detection in Weighted Graphs
  Community detection is a widely-studied unsupervised learning problem in
which the task is to group similar entities together based on observed pairwise
entity interactions. This problem has applications in diverse domains such as
social network analysis and computational biology. There is a significant
amount of literature studying this problem under the assumption that the
communities do not overlap. When the communities are allowed to overlap, often
a pure nodes assumption is made, i.e. each community has a node that belongs
exclusively to that community. This assumption, however, may not always be
satisfied in practice. In this paper, we provide a provable method to detect
overlapping communities in weighted graphs without explicitly making the pure
nodes assumption. Moreover, contrary to most existing algorithms, our approach
is based on convex optimization, for which many useful theoretical properties
are already known. We demonstrate the success of our algorithm on artificial
and real-world datasets.
