Networks in which the edges can be positive or negative occur in many applications (for example, in international relations, states may be allied or official enemies). A widely-used theory of “balance” predicts that networks should become more balanced over time. However there are no clearly agreed measures of partial balance. Samin Aref and I made a start on improving this situation.

Abstract: Is the enemy of an enemy necessarily a friend, or a friend of a friend a
friend? If not, to what extent does this tend to hold? Such questions were
formulated in terms of signed (social) networks and necessary and sufficient
conditions for a network to be “balanced” were obtained around 1960. Since then
the idea that signed networks tend over time to become more balanced has been
widely used in several application areas, such as international relations.
However investigation of this hypothesis has been complicated by the lack of a
standard measure of partial balance, since complete balance is almost never
achieved in practice.
We formalise the concept of a measure of partial balance, compare several
known measures on real-world and synthetic datasets, as well as investigating
their axiomatic properties. We use both well-known datasets from the sociology
literature, such as Read’s New Guinean tribes, and much more recent ones
involving senate bill co-sponsorship. The synthetic data involves both
ErdH{o}s-R’enyi and Barab’asi-Albert graphs.
We find that under all our measures, real-world networks are more balanced
than random networks. We also show that some measures behave better than others
in terms of axioms, computational tractability and ability to differentiate
between graphs. We make some recommendations for measures to be used in future
work.

Link to preprint: http://arxiv.org/abs/1509.04037