  Signed networks are graphs whose edges are labelled with either a positive or
a negative sign, and can be used to capture nuances in interactions that are
missed by their unsigned counterparts. The concept of balance in signed graph
theory determines whether a network can be partitioned into two perfectly
opposing subsets, and is therefore useful for modelling phenomena such as the
existence of polarized communities in social networks. While determining
whether a graph is balanced is easy, finding a large balanced subgraph is hard.
The few heuristics available in the literature for this purpose are either
ineffective or non-scalable. In this paper we propose an efficient algorithm
for finding large balanced subgraphs in signed networks. The algorithm relies
on signed spectral theory and a novel bound for perturbations of the graph
Laplacian. In a wide variety of experiments on real-world data we show that our
algorithm can find balanced subgraphs much larger than those detected by
existing methods, and in addition, it is faster. We test its scalability on
graphs of up to 34 million edges.
