Maximizing circle of trust in online social networks
View Patent ↗Methods are provided for constructing an on-the-fly circle of trust for a user of an online social network to enable the user to reduce the likelihood that information will be leaked to an unwanted target. In one embodiment, a maximum circle of trust is constructed by using an iterative greedy construction (IGC) algorithm with leakage estimation using disjoint cut-sets. In another embodiment, the maximum circle of trust is constructed by using the IGC algorithm with leakage estimation using a hybrid method where the initial CT is constructed using the disjoint cut-sets and then the neighbors not included in the CT are sorted in non-decreasing order of visibilities and then each of these neighbors is included in the CT one at a time while checking if the leakage is below a threshold using a Sampling algorithm. In yet another embodiment, randomized rounding is used to construct the maximum circle of trust.
1. A computer-implemented method of controlling propagation of information posted on an online social network (OSN), the method comprising executing on a processor the steps of:
receiving a message and an unwanted target for the message from a source user of the OSN;
storing the message and the unwanted target on one or more computer readable media in operable communication with the processor;
obtaining a friend/follower list associated with the source user on the OSN;
constructing, from the friend/follower list and the unwanted target, a maximum circle of trust (MCT), the MCT comprising a largest set of trusted users of the OSN, wherein the MCT minimizes a probability that the message will be propagated to the unwanted target via the trusted users; and
rendering the message on the OSN, wherein the message is visible on the OSN only to the trusted users indicated by the MCT,
wherein constructing the MCT comprises executing on the processor the following steps:
representing the source user's network as a directed graph with a tuple of probability <a si , p si >, where a si is a sharing probability from the source user s to a friend user i and each a si is defined as
a
si
=
an
si
Ad
/
ad
si
Ad
,
where an si represents a numerator of a si , ad si represents a denominator of a si and Ad is the least common multiple of all denominators ad si ;
performing phase 1 scaling by scaling a si by a factor A to provide a scaled sharing probability
a
si
′
=
⌊
an
si
A
⌋
,
where
A
=
ɛ
max
{
an
si
Ad
ad
si
|
a
si
p
it
≤
τ
}
S
n
,
ε>0, τ is a leakage probability to the unwanted user t, and S n is the number of friends i of the source user s; and
performing phase 2 dynamic programming by performing a recursion function L i (a) for a=1 to S n ,
L
i
(
a
)
=
{
L
i
-
1
(
a
)
,
if
a
<
a
i
min
{
L
i
-
1
(
a
)
,
L
i
-
1
(
a
-
a
si
′
)
+
w
i
}
,
if
a
≥
a
i
where L i (a) is the minimum leakage probability of a subset of s's first i friends with a elide of trust Ca having size equal to a and w i =−log(1−a si p it ) corresponding to the neighbor i of s; and
wherein the MCT is arg max 1≦a≦S n {C a |L(a)≦τ}.
2. A computer-implemented method of controlling propagation of information posted on an online social network (OSN), the method comprising executing on a processor the steps of:
receiving a message and an unwanted target for the message from a source user of the OSN;
storing the message and the unwanted target on one or more computer readable media in operable communication with the processor;
obtaining a friend/follower list associated with the source user on the OSN;
constructing, from the friend/follower list and the unwanted target, a maximum circle of trust (MCT), the MCT comprising a largest set of trusted users of the OSN, wherein the MCT minimizes a probability that the message will be propagated to the unwanted target via the trusted users; and
rendering the message on the OSN, wherein the message is visible on the OSN only to the trusted users indicated by the MCT,
wherein constructing the MCT comprises executing on the processor the following steps:
representing the source user's network as a directed graph with a tuple of probability <a si , p si >, where a si is a sharing probability from the source user s to a friend user i, T={t 1 , . . . t k } is the set of k=|T| unwanted targets, and the source user s has |N(s)\T|=S n neighbors;
for a threshold
β
=
min
{
⌈
k
ɛ
⌉
-
(
k
-
1
)
,
N
(
s
)
\
T
}
with k unwanted targets:
(1) when the number of visible neighbors of s is less than β, performing an enumeration to provide a feasible solution π that induces a maximum visibility; and
(2) starting with the feasible solution as a current optimal solution, checking each combination of size β, wherein for each combination Ω:
obtaining a bounded solution π Ω in terms of a neighbor set N(s)′={i|a i ≦min i∈Q} and c j′ =c j −Σ i∈Ω w ij by using
max
∑
i
∈
N
(
s
)
\
T
a
i
x
i
s
.
t
.
∑
i
∈
N
(
s
)
\
T
w
ij
x
i
≤
c
j
,
∀
j
∈
T
x
i
≥
0
where w ij =−log(1−a si p it j ) and c j =−log(1−τ j );
and updating the current optimal solution if Σ i∈Ω a i +π Ω >π.
3. A computer-implemented method of controlling propagation of information posted on an online social network (OSN), the method comprising executing on a processor the steps of:
receiving a message and an unwanted target for the message from a source user of the OSN;
storing the message and the unwanted target on one or more computer readable media in operable communication with the processor;
obtaining a friend/follower list associated with the source user on the OSN;
constructing, from the friend/follower list and the unwanted target, a maximum circle of trust (MCT), the MCT comprising a largest set of trusted users of the OSN, wherein the MCT minimizes a probability that the message will be propagated to the unwanted target via the trusted users; and
rendering the message on the OSN, wherein the message is visible on the OSN only to the trusted users indicated by the MCT,
wherein constructing the MCT comprises executing on the processor the following steps:
representing the source user's network as a directed graph with a tuple of probability <a si , p si >, where a si is a sharing probability from the source user s to a friend user i, T={t 1 , . . . . , t k } is the set of k=|T| unwanted targets, and the source user s has |N(s)\T|=S n neighbors;
given
β
←
min
{
⌈
k
ɛ
⌉
-
(
k
+
1
)
,
N
(
s
)
\
T
}
;
w
ij
←
-
log
(
1
-
p
si
p
it
j
)
;
c
j
←
-
log
(
1
-
τ
j
)
;
performing a first phase comprising:
foreach Λ ⊂ N (s) \ T such that |Λ| < β do
|
if Σ i∈Λ w ij ≦ c j for all j ∈ T then
|
|
if Σ i∈Λ a i > π ε then
|
|
|
C ← Λ;
|
|
end
|
end
end
; and
performing a second phase comprising:
foreach Ω ⊂ N (s) \ T such that |Ω| = β do
|
if Σ i∈Ω w ij ≦ c j then
|
|
Obtain the solution C Ω k of the subproblem with
|
|
N(s)′ = {j|c j ≦ min{c i |i ∈ Ω}} \ Ω and
|
|
c j ′ = Σ i∈Ω w ij using Algorithm 3 ;
|
|
if Σ i∈Ω∪C Ω k a i > π ε then
|
|
|
C ← Ω ∪ C Ω k ;
|
|
end
|
end
end
return C;
where τ j is a leakage probability for each t j ∈T, and the circle of trust C is the MCT, wherein using the Algorithm 3 comprises:
obtaining an optimal basic solution x LP by solving LP (2) with |{i|0<x i LP <1}|≦k, where I←{i|x i LP =1} and F←{i|0<x i LP <1}, and
if Σ i∈I a i > max{a j |j ∈ F} then
|
C I ← I;
end
else
|
C I ← {j};
end
return C I ;
where C 1 is an intermediate circle of trust,
wherein LP (2) is:
max
∑
i
∈
N
(
s
)
\
T
a
i
x
i
s
.
t
.
∑
i
∈
N
(
s
)
\
T
w
ij
x
i
≤
c
j
,
∀
j
∈
T
x
i
≥
0
where
w
ij
=
-
log
(
1
-
a
si
p
it
j
)
and
c
j
=
-
log
(
1
-
τ
j
)
.
4. A computer-implemented method of controlling propagation of information posted on an online social network (OSN), the method comprising executing on a processor the steps of:
receiving a message and an unwanted target for the message from a source user of the OSN;
storing the message and the unwanted target on one or more computer readable media in operable communication with the processor;
obtaining a friend/follower list associated with the source user on the OSN;
constructing, from the friend/follower list and the unwanted target, a maximum circle of trust (MCT), the MCT comprising a largest set of trusted users of the OSN, wherein the MCT minimizes a probability that the message will be propagated to the unwanted target via the trusted users; and
rendering the message on the OSN, wherein the message is visible on the OSN only to the trusted users indicated by the MCT,
wherein constructing the MCT comprises executing on the processor the following steps:
representing the source user's network as a directed graph with a tuple of probability <a si , p si >, where a si is a sharing probability from the source user s to a friend user i, T={t 1 , . . . , t k } is the set of k=|T| unwanted targets, τ j is a leakage probability for each t j ∈T and the source user s has |N(s)\T|=S n neighbors;
obtaining a solution x L of LP(2), wherein LP(2) is
max
∑
i
∈
N
(
s
)
\
T
a
si
x
i
s
.
t
.
∑
i
∈
N
(
s
)
\
T
w
ij
x
i
≤
c
j
,
∀
j
∈
T
x
i
≥
0
where w ij =−log(1−a si p it j ) and c j =−log(1−τ j ), and
rounding each x I to 1 with a probability μx L with μ=α(π* LP /k) 1/(δ-1) where α<½ and π* LP is an optimal fractional solution of LP(2), and
c
^
=
min
j
log
(
1
-
τ
j
)
max
i
log
(
1
-
a
si
p
it
j
)
,
wherein the MCT is {i|x i I =1}.
5. A computer-implemented method of controlling propagation of information posted on an online social network (OSN), the method comprising executing on a processor the steps of:
receiving a message and an unwanted target for the message from a source user of the OSN;
storing the message and the unwanted target on one or more computer readable media in operable communication with the processor;
obtaining a friend/follower list associated with the source user on the OSN;
constructing, from the friend/follower list and the unwanted target, a maximum circle of trust (MCT), the MCT comprising a largest set of trusted users of the OSN, wherein the MCT minimizes a probability that the message will be propagated to the unwanted target via the trusted users; and
rendering the message on the OSN, wherein the message is visible on the OSN only to the trusted users indicated by the MCT,
wherein constructing the MCT comprises executing on the processor the following steps:
iteratively adding one of the user's neighbors into the circle of trust until no further neighbors can be added without causing a leakage probability to exceed a threshold
where in each iteration, the set of candidate neighbors L, those whose addition to CT still guarantees that the leakage levels at each unwanted targets t j does not exceed the threshold τ j is updated, wherein a l j (C) is the probability that the message will be leaked to t j , and v is a candidate if l j (C+{v})≦τ j ∀j=1 . . . k, where ƒ(v) is used to evaluate the fitness of user v
f
(
v
)
=
a
sv
max
t
j
∈
T
l
j
(
v
)
(
∑
u
∈
L
l
j
u
-
l
j
(
v
)
)
1
-
l
j
(
v
)
where l j (v) =l j (C+{v})/τ j is the normalized leakage level at t j after adding v to the CT and 1−l j (v) is the remaining leakage tolerance at the unwanted target t j ; Σu ∈L l j u −l j (v) reflects the future potential leakage to target t j when adding user v to CT.
6. A computer-implemented method of controlling propagation of information posted on an online social network (OSN), the method comprising executing on a processor the steps of:
receiving a message and an unwanted target for the message from a source user of the OSN;
storing the message and the unwanted target on one or more computer readable media in operable communication with the processor;
obtaining a friend/follower list associated with the source user on the OSN;
constructing, from the friend/follower list and the unwanted target, a maximum circle of trust (MCT), the MCT comprising a largest set of trusted users of the OSN, wherein the MCT minimizes a probability that the message will be propagated to the unwanted target via the trusted users; and
rendering the message on the OSN, wherein the message is visible on the OSN only to the trusted users indicated by the MCT,
wherein constructing the MCT comprises executing on the processor the following steps:
representing the source user's network as a directed graph G=(V,E) with propagation probabilities p(u,v) for (u,v)∈E, where T={t 1 , . . . , t k } is the set of k=|T| unwanted targets in V, where τ j is a leakage probability for each t j ∈T and the source user s has |N(s)\T|=S n neighbors;
initiating a circle of trust C as 0 and a Layer L as N(s)\T;
removing all unwanted targets T with no risk of leakage by performing:
foreach t j ∈ T do
|
if τ j (L) < τ i then
|
|
T ← T \ {t j };
|
end
end
;
while ∀l j (C) < τ j , update the set of candidate users by performing:
|
foreach v ∈ L do
|
|
if ∃j : l j (C + {v}) > τ j then
|
|
|
L ← L \ {v};
|
|
end
|
end
|
Find v ∈ L that maximized f(v);
|
C ← C ∪ {v};
end
return C
;
wherein C provides the MCT.
7. The method according to claim 6 , wherein estimate leakage τ j (C) is obtained using a non-sampling method comprising:
foreach v ∈ V do
|
Compute d(s, v) and d(v, t) the hop
|
distance from s to v and from v to t,
|
respectively;
end
Let d 0 = d(s, t);
for i = 1 to d 0 do do
|
C i ← {(u, v) | d s (u) = i d s (u) + d t (v) ≦
|
δ − 1}
end
return 1 − II i=1 δ (1 − II e∈C i )
,
where layers of vertices are constructed using a Breadth-First Search algorithm such that layer L i consists of vertices at distance i from the source in term of hops, wherein cutset C i is constructed by including all edges (u,v) with u∈L i and v∈L i+1 but only if d s (u)+d t (v)≦δ−1, where δ is number of hops.
8. The method according to claim 7 , wherein the estimate leakage τ j (C) is further obtained by, after performing the non-sampling method,
sorting the neighbors that are not included in the CT in non-decreasing order of their visibilities;
following the non-decreasing order, including each neighbor into the CT and checking if the leakage is below a threshold using a Sampling algorithm; and
if the leakage is below the threshold adding the neighbor to the CT; else not adding the neighbor to the CT.
9. A system for controlling propagation of information posted on an online social network (OSN), the system comprising:
one or more computer readable media;
a processor in operable communication with the one or more computer readable media;
computer-executable instructions stored on the one or more computer readable media that, when executed by the processor, direct the processor to:
render, to a source user of the OSN, a user interface for indicating an unwanted target for a message on the OSN;
receive an indication of the unwanted target for the message on the OSN;
store the message and the unwanted target on the one or more computer readable media;
obtain, from the OSN, a friend/follower list associated with the source user on the OSN;
construct, from the friend/follower list and the unwanted target, a maximum circle of trust (MCT), the MCT comprising a largest set of trusted recipients of the message on the OSN, wherein the MCT minimizes a probability that the message will be propagated to the unwanted target via the trusted recipients; and
transmit the message on the OSN only to the trusted recipients indicated by the MCT.
10. The system according to claim 9 , wherein constructing the MCT further comprises computer-executable instructions stored on the one or more computer readable media that, when executed by the processor, direct the processor to:
represent the source user's network as a directed graph with a tuple of probability <a si , p si ), where a si is a sharing probability from the source user s to a friend user i and each a si is defined as
a
si
=
an
si
Ad
/
ad
si
Ad
,
where an si represents a numerator of a si , ad si represents a denominator of a si , and Ad is the least common multiple of all denominators ad si ;
perform phase 1 scaling by scaling a si by a factor A to provide a scaled sharing probability
a
si
′
=
⌊
an
si
A
⌋
,
where
A
=
ɛ
max
{
an
si
Ad
ad
si
|
a
si
p
it
≤
τ
}
S
n
,
ε>0, τ is a leakage probability to the unwanted user t, and S n is the number of friends i of the source user s; and
perform phase 2 dynamic programming by performing a recursion function L i (a) for a=1 to S n ,
L
i
(
a
)
=
{
L
i
-
1
(
a
)
,
if
a
<
a
i
min
{
L
i
-
1
(
a
)
,
L
i
-
1
(
a
-
a
si
′
)
+
w
i
}
,
if
a
≥
a
i
where L i (a) is the minimum leakage probability of a subset of s's first i friends with a circle of trust Ca having size equal to a and w i =−log(1−a si p it ) corresponding to the neighbor i of s; and
wherein the MCT is arg max 1≦a≦S n {C a |L(a)≦τ}.