  We analyse signed networks from the perspective of balance theory which
predicts structural balance as a global structure for signed social networks
that represent groups of friends and enemies. The scarcity of balanced networks
encouraged us to define the notion of partial balance in order to quantify the
extent to which a network is balanced. We evaluate several numerical measures
of partial balance and recommend using the frustration index, a measure that
satisfies key axiomatic properties and allows us to analyse graphs based on
their levels of partial balance. The exact algorithms used in the literature to
compute the frustration index, also called the line index of balance, are not
scalable and cannot process graphs with a few hundred edges. We formulate
computing the frustration index as a graph optimisation problem to find the
minimum number of edges whose removal results in a balanced network given
binary decision variables associated with graph nodes and edges. We use our
first optimisation model to analyse graphs with up to 3000 edges. Reformulating
the optimisation problem, we develop three more efficient binary linear
programming models. Equipping the models with valid inequalities and
prioritised branching as speed-up techniques allows us to process graphs with
15000 edges on inexpensive hardware. Besides making exact computations possible
for large graphs, we show that our models outperform heuristics and
approximation algorithms suggested in the literature by orders of magnitude. We
extend the concepts of balance and frustration in signed networks to
applications beyond the classic friend-enemy interpretation of balance theory
in social context. Using a high-performance computer, we analyse graphs with up
to 100000 edges to investigate a range of applications from biology and
chemistry to finance, international relations, and physics.
