Graph-based Sybil Detection in Social and Information Systems

Yazan Boshmaf ; Konstantin Beznosov ; Matei Ripeanu

23 May 2013

Abstract: Sybil attacks in social and information systems have serious security implications. Out of many defence schemes, Graph-based Sybil Detection (GSD) had the greatest attention by both academia and industry. Even though many GSD algorithms exist, there is no analytical framework to reason about their design, especially as they make different assumptions about the used adversary and graph models. In this paper, we bridge this knowledge gap and present a unified framework for systematic evaluation of GSD algorithms. We used this framework to show that GSD algorithms should be designed to find local community structures around known non-Sybil identities, while incrementally tracking changes in the graph as it evolves over time.

Keyword(s): Sybil attack ; Online Social Networks ; Graph-based Sybil Detection ; Graph Theory ; Community Detection

Published in: Yazan Boshmaf, Konstantin Beznosov, Matei Ripeanu. Graph-based Sybil Detection in Social and Information Systems. In the Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM'13), Niagara Falls, Canada, August 25-28, 2013.:

The record appears in these collections:
Refereed Conference Papers

 Record created 2013-05-23, last modified 2013-06-11

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)