Database Reference
In-Depth Information
could not be returned by other users in
u
's U-Net. In other words, it is defined
as follows:
usefulness
(
v
j
|v
j
+1
, ..., v
n
)=
P
(
Q
v
j
)
− P
(
Q
v
j
∩
(
Q
v
j
+1
∪ ... ∪ Q
v
n
))
(4)
Formula 4 shows that the usefulness score should consider relevance
P
(
Q
v
j
)
and take into account
P
(
Q
v
j
∩
(
Q
v
j
+1
∪ ... ∪ Q
v
n
)) which corresponds to the
redundancy of user profile
v
j
with respect to the other user profiles
v
j
+1
, ..., v
n
.
In the following, we show that
usefulness
(
v
j
|v
j
+1
, ..., v
n
) can be expressed into
a known probabilistic diversification model [8, 9]. In Formula 5 we first integrate
usefulness (the right hand side of Formula 4) into a conditional probability.
P
(
Q
v
j
)
− P
(
Q
v
j
∩
(
Q
v
j
+1
∪ ... ∪ Q
v
n
)) =
P
(
Q
v
j
)
×
(1
− P
(
Q
v
j
+1
∪ ... ∪ Q
v
n
|Q
v
j
))
=
P
(
Q
v
j
)
× P
(
Q
v
j
+1
∩ ... ∩
Q
v
n
|Q
v
j
)
(5)
Similar to [8, 9, 13], we assume that the redundancy of a user profile
v
1
with
another user profile
v
2
is independent of its redundancy with other users and we
derive Formula 6.
P
(
Q
v
j
)
× P
(
Q
v
j
+1
∩ ... ∩
Q
v
n
|Q
v
j
)=
P
(
Q
v
j
)
×
(1
− P
(
Q
v
i
|Q
v
j
))
(6)
i∈j
+1
,...,n
Finally, we observe that the usefulness of a user profile is clearly similar to the
probabilistic diversification problem used in [8, 9] and presented in Formula 7.
usefulness
(
v
j
|v
j
+1
, ..., v
n
)=
rel
(
v
j
)
×
(1
− red
(
v
j
,v
i
))
(7)
i∈j
+1
,...,n
where
rel
(
v
j
)=
P
(
Q
v
j
) is the relevance of user profile
v
j
and
red
(
v
j
,v
i
)=
P
(
Q
v
i
|Q
v
j
) is the redundancy of user profile
v
j
with respect to the other user
profile
v
i
.
3.2 Useful U-Net Clustering
We now present in details our clustering algorithm that maintains a useful
U-Net
over a random gossip overlay using the usefulness score.
Given the set of users in the random view, the goal of the clustering algorithm
is to compute the usefulness of each user found in the view, with respect to
those that were previously added to the
U-Net
, taking into account relevance
and diversity, as defined in Equation 7, and to update the
U-Net
as consequence.
Based on random gossiping [5], each user
u
maintains a set of random view en-
tries corresponding to the users profile
u
is aware of. Periodically, users gossip,
and exchange a random subset of their views entries. After the random gossip
merging phase, the clustering algorithm, which corresponds to the
Useful U-Net
Algorithm depicted in Algorithm 1, is triggered. In fact, taking into account the
previous gossip exchange, the algorithm selects the most useful users from the
random view considering the useful users previously selected (
i.e.
from the pre-
vious gossip rounds) in the
U-Net
. The algorithm uses three main data structures:
random view,
U-Net
, and the candidate list. The random view and the
U-Net
are
initialized when
u
joins the network, and continuously updated as a result of ran-
dom gossip. The candidates list contains the user profiles that will potentially be
Search WWH ::
Custom Search