SybilHP: Sybil Detection in Directed Social Networks with Adaptive Homophily Prediction

Abstract

Worries about the increasing number of Sybils in online social networks (OSNs) are amplified by a range of security issues; thus, Sybil detection has become an urgent real-world problem. Lightweight and limited data-friendly, LBP (Loopy Belief Propagation)-based Sybil-detection methods on the social graph are extensively adopted. However, existing LBP-based methods that do not utilize node attributes often assume a global or predefined homophily strength of edges in the social graph, while different user’s discrimination and preferences may vary, resulting in local homogeneity differences. Another issue is that the existing message-passing paradigm uses the same edge potential when propagating belief to both sides of a directed edge, which does not agree with the trust interaction in one-way social relationships. To bridge these gaps, we present SybilHP, a Sybil-detection method optimized for directed social networks with adaptive homophily prediction. Specifically, we incorporate an iteratively updated edge homophily estimation into the belief propagation to better adapt to the personal preferences of real-world social network users. Moreover, we endow message passing on edges with directionality by a direction-sensitive potential function design. As a result, SybilHP can better capture the local homophily and direction pattern in real-world social networks. Experiments show that SybilHP works with high detection accuracy on synthesized and real-world social graphs. Compared with various state-of-the-art graph-based methods on a large-scale Twitter dataset, SybilHP substantially outperforms existing methods.

Keywords

• social network
• sybil detection
• semi-supervised learning
• belief propagation