English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

MPS-Authors
/persons/resource/persons45527

Sozio,  Mauro
Databases and Information Systems, MPI for Informatics, Max Planck Society;

/persons/resource/persons44267

Crecelius,  Tom
Databases and Information Systems, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

/persons/resource/persons45166

Xavier Parreira,  Josiane
Databases and Information Systems, MPI for Informatics, Max Planck Society;

/persons/resource/persons45720

Weikum,  Gerhard
Databases and Information Systems, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Sozio, M., Crecelius, T., Xavier Parreira, J., & Weikum, G. (2008). Good Guys vs. Bad Guys: Countering Cheating in Peer-to-Peer Authority Computations over Social Networks. In 11th International Workshop on the Web and Databases (WebDB 2008) (pp. 103-108). Como: Politecnico di Milano.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1BD3-A
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.