Patent Document ID: 20140317736
Application ID: 13868331
Patent Status: 0

Claim One:
1. A method for detecting fake accounts in online social networks, comprising: associating an online social network with a social graph G which comprises two disjoint regions, a non-Sybil region GM and a Sybil region G S , characterized in that the method further comprises: computing a trust value T (i) (v) through i power iterations on each node v of the social graph G, where i=0, 1,. .. O(log n) and n being the number of nodes in the social graph G; the power iterations distribute the trust value T (i) (v) from each node v to its neighbour nodes, through the entire social graph G with a bias towards the non-Sybil region G H by distributing the trust value from at least one node of the non-Sybil region G H selected as trust seed; after an early ending number w=O(log n) of power iterations, ranking is nodes by a degree-normalized trust to obtain a ranked list of nodes, the degree-normalized trust of the node v being computed based on dividing the trust value T (i) (v) by a degree deg(v) of the node v in the social graph G, i=w and the degree deg(v) being the number of adjacent nodes to node v in the social graph G; detecting fake accounts in the Sybil region G S based on the obtained ranked list.