Trust-based Sybil nodes detection with robust seed selection and graph pruning on SNS

Shuichiro Haruta, Kentaroh Toyoda, Iwao Sasase

研究成果: Article査読


On SNS (Social Networking Services), detecting Sybils is an urgent demand. The most famous approach is called "SybilRank" scheme where each node evenly distributes its trust value starting from honest seeds and detects Sybils based on the trust value. Furthermore, Zhang et al. propose to avoid trust values from being distributed into Sybils by pruning suspicious relationships before performing SybilRank. However, we point out that the above two schemes have shortcomings that must be remedied. In the former scheme, seeds are concentrated on the specific communities because they are selected from nodes that have largest number of friends, and thus the trust value is not evenly distributed. In the latter one, asophisticated attacker can avoid graph pruning by making relationships between Sybil nodes. In this paper, we propose a robust seed selection and graph pruning scheme to detect Sybil nodes more accurately. To more evenly distribute trust value into honest nodes, we first detect communities in the SNS and select honest seeds from each detected community. And then, by leveraging the fact that Sybils cannot make dense relationships with honest nodes, we also propose a graph pruning scheme based on the density of relationships between trusted nodes. We prune the relationships which have sparse relationships with trusted nodes and this enables robust pruning malicious relationships even if the attackers make a large number of common friends. By the computer simulation with real dataset, we show that our scheme improves the detection accuracy of both Sybil and honest nodes.

ジャーナルIEICE Transactions on Communications
出版ステータスPublished - 2016 5月

ASJC Scopus subject areas

  • ソフトウェア
  • コンピュータ ネットワークおよび通信
  • 電子工学および電気工学


「Trust-based Sybil nodes detection with robust seed selection and graph pruning on SNS」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。