Social balance theory deals with signed graphs. It assumes that interactions have to be balanced in a certain way, reminiscent of the age-old adage of “the enemy of my enemy is my friend”. In network theory, we think of this as (un)balanced triads. If all triads are balanced, then the network itself is also balanced. Moreover, it can then be split in two factions, such that there are only positive links between factions and negative links within factions.
In this project we are studying models for building reputations from local interactions. Such models are useful for understanding how for example cooperation can stabilize. Often it is assumed that people will cooperate with someone who has a good reputation, treating the reputation as an objective value. However, reputation is something constructed locally through interactions. These interactions elicit gossip amongst people, sharing information about a third party. Relevant questions here are whether such gossiping models are evolutionary stable strategies; what type of interaction patterns can emerge; how the amount of cooperation will evolve, et cetera.
One particular questions concerns how social balance may emerge. Certain dynamical processes might give rise to social balance, whereas other dynamics lead to other patterns. We have compared two models that could potentially explain the emergence of social balance. These models can be interpreted as representing gossiping processes. A first gossiping mechanism might be to ask other people what they think of a third party. Another possible mechanism is to talk to somebody to see if you have common friends or enemies. We are able to prove that our alternative model (almost) always leads to social balance, contrary to another earlier model.
This has also connections to the problem of evolution of cooperation. In particular, the models we studied are very close to something known as indirect reciprocity theory. The core of that theory is in biblical terms “give and you will receive”. In other words, if you help somebody out, you will be helped in turn by somebody else. In the above gossiping process, our alternative model also leads to cooperation. Yet, paradoxically, the model also leads to social balance. Hence, cooperation is able to evolve, yet it is likely that a population split in two factions.
Another, though related, approach is that of deciding on the reputation of nodes in a given network. Whereas in the previous approach we are looking from a dynamical point of view (how will relations of cooperation change over time, and how will that affect the reputation again), here we are looking from a more static point of view. Given a certain network where people for example indicate whether they (dis)trust each other, how should we reconstruct an accurate reputation? For example, if somebody new arrives in the network, who could he trust best? We explored this issue resulting in a measure known as Exponential Ranking. This ranking is able to take into account negative links, unlike PageRank.
