hide
Free keywords:
-
Abstract:
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.
