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 that is firstly given to honest seeds and detects Sybils based on the trust value. Furthermore, Zhang et al. proposed to avoid trust values from being distributed into Sybils by pruning suspicious relationships before 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 and thus the trust value is not evenly distributed. Against the latter one, a sophisticated 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. 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, based on 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.