Friend or Faux: Graph-Based Early Detection of Fake Accounts on Social
  Networks
  In this paper, we study the problem of early detection of fake user accounts
on social networks based solely on their network connectivity with other users.
Removing such accounts is a core task for maintaining the integrity of social
networks, and early detection helps to reduce the harm that such accounts
inflict. However, new fake accounts are notoriously difficult to detect via
graph-based algorithms, as their small number of connections are unlikely to
reflect a significant structural difference from those of new real accounts. We
present the SybilEdge algorithm, which determines whether a new user is a fake
account (`sybil') by aggregating over (I) her choices of friend request targets
and (II) these targets' respective responses. SybilEdge performs this
aggregation giving more weight to a user's choices of targets to the extent
that these targets are preferred by other fakes versus real users, and also to
the extent that these targets respond differently to fakes versus real users.
We show that SybilEdge rapidly detects new fake users at scale on the Facebook
network and outperforms state-of-the-art algorithms. We also show that
SybilEdge is robust to label noise in the training data, to different
prevalences of fake accounts in the network, and to several different ways
fakes can select targets for their friend requests. To our knowledge, this is
the first time a graph-based algorithm has been shown to achieve high
performance (AUC>0.9) on new users who have only sent a small number of friend
requests.
