Paper Info
Title
Keep your friends close: Incorporating trust into social network-based Sybil defenses.
Abstract
Social network-based Sybil defenses exploit the algorithmic properties of social graphs to infer the extent to which an arbitrary node in such a graph should be trusted. However, these systems do not consider the different amounts of trust represented by different graphs, and different levels of trust between nodes, though trust is being a crucial requirement in these systems. For instance, co-authors in an academic collaboration graph are trusted in a different manner than social friends. Furthermore, some social friends are more trusted than others. However, previous designs for social network-based Sybil defenses have not considered the inherent trust properties of the graphs they use. In this paper we introduce several designs to tune the performance of Sybil defenses by accounting for differential trust in social graphs and modeling these trust values by biasing random walks performed on these graphs. Surprisingly, we find that the cost function, the required length of random walks to accept all honest nodes with overwhelming probability, is much greater in graphs with high trust values, such as co-author graphs, than in graphs with low trust values such as online social networks. We show that this behavior is due to the community structure in high-trust graphs, requiring longer walk to traverse multiple communities. Furthermore, we show that our proposed designs to account for trust, while increase the cost function of graphs with low trust value, decrease the advantage of attacker.
Year
DOI
Venue
2011
10.1109/INFCOM.2011.5934998
INFOCOM
Keywords
Field
DocType
graph theory,probability,security of data,social networking (online),Sybil defense,co-author graphs,cost function,differential trust,random walk bias,social graph,social network,trust behavior
Graph theory,Social network,Algorithm design,Random walk,Computer science,Computer network,Exploit,Collaboration graph,Knowledge engineering,Distributed computing,Traverse
Conference
ISSN
Citations 
PageRank 
0743-166X
16
0.68
References 
Authors
27
3
Name
Order
Citations
PageRank
Abedelaziz Mohaisen133830.36
Nicholas Hopper2146995.76
Yongdae Kim31944125.44