A formalism to measure trust and distrust based on extended structural balance theory
In our upcoming paper on PST 2013 Conference on Privacy, Security and Trust, we introduce a formal theory for measuring trust and distrust. The paper can be found here (YA_PST2013.pdf).
Our method formalizes the assumptions behind most trust prediction algorithms: structural balance theory (SBT). According to this theory, certain relationships are balanced and do not cause tension. If we use plus to indicate friendship or trust, and minus to represent hatred or distrust, we can consider the above three way relationships.
For example, triangles one and two above are balanced in both strong and weak structural balance theory, and triangle four is unbalanced in both. Weak SBT also considers triangle three as balanced. For example, in triangle four, A and C are two friends of B that cannot get along. This causes tension because B now has to make sure that she does not meet with A and C at the same time. Furthermore, SBT claims that networks tend to converge towards balance as individuals try to reduce the tension in relationships. This logic has been used in many algorithms including clustering methods.
In real life networks, the support for SBT has been mixed. To address this issue, we introduce an extension of SBT (ESBT) that takes into account that the strengths of the ties matter as much as their valance (positive or negative). We introduce a new theory that explains structural balance. In our model, we have a continuum of levels of trust from strong trust to strong distrust. This spectrum also includes weak biases in either direction as well as neutral relations with no bias or preconceived notions. ESBT is based on two basic axioms shown below:
Sunday, June 2, 2013
Case for trust is similar to the transitivity of trust. We note though that the stronger the relations between 1 and 2, and 2 and 3, the more likely it is that 1 and 3 are positively linked. If 1&2, or 2&3 are weak ties and as a result do not spend any time together, then there is no pressure on 1&3 to be friends.
The case for distrust emphasizes the lack of homophily causes a tension to distrust. If 2&3 are very close friends, but 1&2 hate each other, there is pressure on 1&3 to distrust each other through influence of 2 on 3. However, if the distrust between 1&2 or the relationship between 2&3 are not strong, there is less of a likelihood, that these relationships will have an effect on the relationship between 1&3.
We formalize our theory and the notion of convergence using the Metric Multidimensional Scaling problem. Our novel method has sound social and psychological basis, and captures the classical balance theory as a special case. We show that given a network, we can solve the edge sign prediction problem, i.e. finding if two people trust each other or have distrust, using a stress majorization (SM) algorithm. Using the datasets studied in past work, we show that our methods match and significantly outperform state of the art in trust prediction.
Software is available at github.com/rpitrust/structuralbalance
