Method and system for detecting fake accounts in online social networks
View Patent ↗A system and method for detecting fake accounts in OSNs is proposed to aid the OSN provider 20 against fake users, wherein a social graph G of the OSN, with n nodes, a non-Sybil region G H and a Sybil region G S , is obtained and the following steps are performed: a trust value T (i) (v) is computed through i power iterations on each node v of the social graph G, i=0, 1, . . . O(log n) the power iterations distribute the trust value T (i) (v) from each node v to its neighbor nodes, after O(log n) power iterations, ranking nodes by a degree-normalized trust T ^ v = T ( w ) ( v ) deg ( v ) in order to obtain a ranked list of nodes, detecting fake accounts based on the obtained ranked list assigning intervals in the ranked list to a fake portion, determined by manual inspection means of the OSN provider, based on the degree-normalized trust of the nodes belonging to the intervals.
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 G H and a Sybil region G S , characterized in that the method further comprises:
computing, by a computer device, 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.
2. The method according to claim 1 wherein distributing the trust value T (i) (v) through the entire social graph G comprises:
selecting K nodes of the social graph G, K≧1, as trust seeds;
setting a total trust T G of the social graph G;
computing an initial trust value T (o) (v) as:
T
(
o
)
(
v
)
=
{
T
G
K
if
node
v
is
one
of
the
K
trust
seeds
0
else
collecting trust values distributed by the neighbour nodes u of the node v;
according to the collected trust values, updating the trust value T (i) (v) to be distributed using the expression:
T
(
i
)
(
v
)
=
∑
(
u
,
v
)
∈
E
T
(
i
-
1
)
(
u
)
deg
(
u
)
where E is a set of edges connecting nodes of the social graph G.
3. The method according to claim 2 , wherein distributing the trust value T (i) (v) through the entire social graph G comprises selecting any node of the non-Sybil region G H as trust seed.
4. The method according to claim 2 , wherein distributing the trust value T (i) (v) through the entire social graph G comprises selecting multiple nodes of the entire social graph G as trust seeds.
5. The method according to claim 1 , wherein the degree-normalized trust {circumflex over (T)} v of the node v is computed as:
T
^
v
=
T
(
w
)
(
v
)
deg
(
v
)
.
6. The method according to claim 1 , wherein the degree-normalized trust is substantially equal for all nodes of the non-Sybil region G H .
7. The method according to claim 1 , wherein the power iterations are initialized with nodes of the non-Sybil region G H .
8. The method according to claim 1 , wherein the detection of fake accounts using the ranked list obtained by ranking nodes by their degree-normalized trust comprises assigning intervals of a certain size in the ranked list to a fake portion as determined by manual inspection.
9. A hardware system for detecting fake accounts in online social networks, wherein an online social network has associated a social graph G comprising two disjoint is regions, a non-Sybil region G H and a Sybil region G S , the hardware system characterized by further comprising:
computational means adapted to compute 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;
communication means adapted to distribute the trust value T (i) (v) by the power iterations, obtained by the computational means, from each node v to its neighbour nodes, through the entire social graph G with a bias towards the non-Sybil region G H distributing the trust value from at least one node of the non-Sybil region G H selected as trust seed;
node ranking means adapted to rank nodes, after an early ending number w=O(log n) of power iterations, 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 of the number of adjacent nodes to node v in the social graph G;
account detection means adapted to detect fake accounts in the Sybil region G S based on the ranked list obtained by the node ranking means.
10. The system according to claim 9 wherein the computational means are to adapted to:
select K nodes of the social graph G, K≧1, as trust seeds;
set a total trust T G of the social graph G;
compute an initial trust value T (o) (v) as:
T
(
o
)
(
v
)
=
{
T
G
K
if
node
v
is
one
of
the
K
trust
seeds
0
else
collect trust values distributed by the neighbour nodes u of the node v;
according to the collected trust values, update the trust value T (i) (v) to be distributed using the expression:
T
(
i
)
(
v
)
=
∑
(
u
,
v
)
∈
E
T
(
i
-
1
)
(
u
)
deg
(
u
)
where E is a set of edges connecting nodes of the social graph G.
11. The system according to claim 10 , wherein the computational means are adapted to select any node of the non-Sybil region G H as trust seed.
12. The system according to claim 10 , wherein the computational means are adapted to select multiple nodes of the entire social graph G as trust seeds.
13. The system according to claim 9 , wherein the computational means are adapted to compute the degree-normalized trust {circumflex over (T)} v of the node v as:
T
^
v
=
T
(
w
)
(
v
)
deg
(
v
)
.
14. The system according to claim 9 , wherein the degree-normalized trust is substantially identical to all nodes of the non-Sybil region G H .
15. The system according to claim 9 , wherein the computational means are adapted to initialize the power iterations with nodes of the non-Sybil region G H .
16. The system according to claim 9 , wherein the fake account detection means are adapted to assign intervals of a certain size in the ranked list to a fake portion determined by manual inspection based on the degree-normalized trust of the nodes belonging to the intervals.
17. A non-transitory digital data storage medium storing a computer program product comprising instructions causing a computer executing the program, to perform all steps of a method comprising:
associating an online social network with a social graph G which comprises two disjoint regions, a non-Sybil region G H and a Sybil region G S ,
characterized in that the method further comprises:
computing, using a computing device, 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 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.