Transitive trust propagation on webs of trust (social networks representing trust relationships between
individuals) is a well-known pattern used to compute reputation, to defend against Sybil attacks and to
introduce incentives to cooperation in peer-to-peer applications. Based on the fact that it is difficult for an
attacker to get trusted by many honest users, it is possible to prove that some methods based on transitive
trust propagation are indeed resilient to attacks mounted by malicious users.
The other side of the coin is that honest users can be mistaken for malicious ones: such an event is likely
to happen when the web of trust has a high mixing time. Performing a random walk over the web of trust,
mixing time is the number of steps needed to ensure that the landing point of the random walk does not
depend on the starting node.
To help assessing the effectiveness of methods based on transitive trust propagation, we measure the mixing
time of four large and publicly available webs of trust. Our experimental results show that mixing time
is not directly related with well-known characteristics such as degree distribution or clustering coefficient.
Rather, they suggest that mixing time is an interesting metrics on its own, explained by the presence or
absence of long-range links in the social network.
