  Signed networks contain edge annotations to indicate whether each interaction
is friendly (positive edge) or antagonistic (negative edge). The model is
simple but powerful and it can capture novel and interesting structural
properties of real-world phenomena. The analysis of signed networks has many
applications from modeling discussions in social media, to mining user reviews,
and to recommending products in e-commerce sites. In this paper we consider the
problem of discovering polarized communities in signed networks. In particular,
we search for two communities (subsets of the network vertices) where within
communities there are mostly positive edges while across communities there are
mostly negative edges. We formulate this novel problem as a "discrete
eigenvector" problem, which we show to be NP-hard. We then develop two
intuitive spectral algorithms: one deterministic, and one randomized with
quality guarantee $\sqrt{n}$ (where $n$ is the number of vertices in the
graph), tight up to constant factors. We validate our algorithms against
non-trivial baselines on real-world signed networks. Our experiments confirm
that our algorithms produce higher quality solutions, are much faster and can
scale to much larger networks than the baselines, and are able to detect
ground-truth polarized communities.
