Good Guys vs. Bad Guys: Countering Cheating in Peer-to-Peer Authority Computations over Social Networks

Eigenvector computations are an important building block for computing authority, trust, and reputation scores in social networks and other graphs. In peer-to-peer networks or other forms of decentralized settings (such as multi-agent platforms), this kind of analysis needs to be performed in a distributed manner and requires bilateral data exchanges between peers. This gives rise to the problem that dishonest peers may cheat in order to manipulate the computation’s outcome. This paper presents a distributed algorithm for countering the effects of such misbehavior, under the assumption that the fraction of dishonest peers is bounded and that there is an unforgeable mechanism for peer identities, which can be implemented using security tools available. The algorithm is based on general principles of replication and randomization and thus widely applicable to social network analysis, web link analysis, and other problems of this kind. Our algorithm converges to the correct result that the honest peers alone would compute. Experiments, on a realworld dataset from a large social-tagging platform, demonstrate the practical viability and performance properties of our algorithm