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