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

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.