Combating Friend Spam Using Social Rejections

Conference Paper

Unwanted friend requests in online social networks (OSNs), also known as friend spam, are among the most evasive malicious activities. Friend spam can result in OSN links that do not correspond to social relationship among users, thus pollute the underlying social graph upon which core OSN functionalities are built, including social search engine, ad targeting, and OSN defense systems. To effectively detect the fake accounts that act as friend spammers, we propose a system called Rejecto. It stems from the observation on social rejections in OSNs, i.e., Even well-maintained fake accounts inevitably have their friend requests rejected or they are reported by legitimate users. Our key insight is to partition the social graph into two regions such that the aggregate acceptance rate of friend requests from one region to the other is minimized. This design leads to reliable detection of a region that comprises friend spammers, regardless of the request collusion among the spammers. Meanwhile, it is resilient to other strategic manipulations. To efficiently obtain the graph cut, we extend the Kernighan-Lin heuristic and use it to iteratively detect the fake accounts that send out friend spam. Our evaluation shows that Rejecto can discern friend spammers under a broad range of scenarios and that it is computationally practical.

Full Text

Duke Authors

Cited Authors

  • Cao, Q; Sirivianos, M; Yang, X; Munagala, K

Published Date

  • July 22, 2015

Published In

  • Proceedings International Conference on Distributed Computing Systems

Volume / Issue

  • 2015-July /

Start / End Page

  • 235 - 244

International Standard Book Number 13 (ISBN-13)

  • 9781467372145

Digital Object Identifier (DOI)

  • 10.1109/ICDCS.2015.32

Citation Source

  • Scopus