SybilExposer: An effective scheme to detect Sybil communities in online social networks
Satyajayant Misra, Abu Saleh Md Tayeen, Wen Qiang Xu · 2016
The popularity of online social networks (OSNs) has resulted in them being targeted with Sybil attacks, where an adversary forges many fake identities (called Sybils) to disrupt or control the normal functioning of the system. Several schemes have been proposed to defend against Sybil attacks. Most of these schemes work by computing the landing probability or statistical distribution of visiting frequency of random walks. These schemes usually have high running time cost and are highly dependent upon the proper choice of known trusted nodes. To address these limitations, in this paper we present SybilExposer, an efficient and effective Sybil community detection algorithm, which relies on the properties of social graph communities to rank communities according to their perceived likelihood of being fake or Sybil. Our experiments on several real-world OSN graphs illustrate that SybilExposer has close to 100% true positive rate and nearly zero false positive rate in identifying Sybil communities, and the best running time complexity compared to the state of the art.