Category Archives: Network science

Measures of partial balance in signed networks

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

Experimental research

When I was a PhD student, stretching my horizons meant thinking about commutative ring theory, instead of general rings. Over my career I have gradually stretched further, taking in mathematical parts of computer science and social choice theory. However in recent years the stretching has become much larger. In addition to supervising PhD students in network science, my first (joint) work on experimental social science has been uploaded to the world.

In this work, ultimately inspired by a logical model developed by our colleague Patrick Girard and coauthors to describe belief changes in social networks, Valery Pavlov and I have conducted a laboratory experiment with human participants, designed to measure influence and social learning of factual information. A novelty was the way we allowed and incentivized participants to truthfully report “I don’t know” – this seemingly small change has large effects on the dynamics.

Almost everything about this was new to me, but I now feel confident about taking this work much further. Threshold-type diffusion models, as opposed to the infection-type models so common in network science, seem to be much more relevant to this kind of situation. Our work suggests a different model from the usual threshold model.

Who knows what the next decade will bring? Perhaps an art installation or a musical performance? There are still faculties of the university I haven’t been much involved with.