28-03-2012, 03:30 PM
Propagation of Trust and Distrust
Propagation of Trust and Distrust.pdf (Size: 189.24 KB / Downloads: 37)
ABSTRACT
A (directed) network of people connected by ratings or trust
scores, and a model for propagating those trust scores, is a
fundamental building block in many of today’s most successful
e-commerce and recommendation systems. We develop a
framework of trust propagation schemes, each of which may
be appropriate in certain circumstances, and evaluate the
schemes on a large trust network consisting of 800K trust
scores expressed among 130K people. We show that a small
number of expressed trusts/distrust per individual allows us
to predict trust between any two people in the system with
high accuracy. Our work appears to be the first to incorporate
distrust in a computational trust propagation setting.
Categories and Subject Descriptors
H.3.3 [Information Storage and Retrieval]: Information
Search and Retrieval; H.3.5 [Information Storage and
Retrieval]: Online Information Services—Web based services;
G.1 [Numerical Analysis]: Numerical Linear Algebra;
G.2 [Discrete Mathematics]: Graph Theory—Graph
algorithms
General Terms
Algorithms, Experimentation, Measurement
Keywords
Trust propagation, web of trust, distrust
1. INTRODUCTION
The web increasingly impacts the processes used by individuals
to express as well as discern preferences among
items. A user may turn to the web for information on
purchases such as digital cameras, songs, or movie tickets;
or for information on much higher impact acquisitions
such as houses, jobs, or even mates. As these decisions
and the underlying financial processes themselves migrate
Copyright is held by the author/owner(s).
WWW2004, May 17–22, 2004, New York, New York, USA.
ACM 158113844X/
04/0005.
to the web, there is growing economic motivation to spread
information—and sometimes disinformation—through the
web. Open standards and a low barrier to publication demand
novel mechanisms for validating information. Thus,
we see unscrupulous exploitations of the holes in the social
fabric of the web: successful manipulation of stocks
by teenagers posting on investment boards under assumed
personas; posts by product marketers pretending to be customers
extolling the virtues of their product; online relationships
that turn sour when one partner uncovers dramatic
misinformation with respect to age or gender; link spamming
of search engines to simulate popularity; and so forth.
One commonly proposed solution to this problem is to
build and maintain a web of trust either in microcosm (as
for an individual web site) or in macrocosm (across the whole
web) that would allow users to express trust of other users,
and in return would apply the entire web of relationships and
trusts to help a user assess the likely quality of information
before acting on it. Through such a web of trust, a user can
develop an opinion of another user without prior interaction.
The goal of this paper is to propose and analyze algorithms
for implementing such a web of trust.
Such a network is a fundamental building block in many
of today’s most successful e-commerce and recommendation
systems. On eBay (ebay.com), for instance, a model of trust
has significant influence on the price an item may command.
While on Epinions (epinions.com), conclusions drawn from
the web of trust are linked to many behaviors of the system,
including decisions on items to which each user is exposed.
1.1 Approaches to trust propagation
A natural approach to estimate the quality of a piece of
information is to aggregate the opinions of many users. But
this approach suffers from the same concerns around disinformation
as the web at large: it is easy for a user or
coalition of users to adopt many personas and together express
a large number of biased opinions. Instead, we wish to
ground our conclusions in trust relationships that have been
built and maintained over time, much as individuals do in
the real world. A user is much more likely to believe statements
from a trusted acquaintance than from a stranger.
403
And recursively, since a trusted acquaintance will also trust
the beliefs of her friends, trusts may propagate (with appropriate
discounting) through the relationship network.
An approach centered on relationships of trust provides
two primary benefits. First, a user wishing to assess a large
number of reviews, judgments, or other pieces of information
on the web will benefit from the ability of a web of trust to
present a view of the data tailored to the individual user,
and mediated through the sources trusted by the user. And
second, users who are globally well-trusted may command
greater influence and higher prices for goods and services.
Such a system encourages individuals to act in a trustworthy
manner [4], placing positive pressure on the evolving social
constructs of the web. Indeed, social network theory and
economics have considered a variety of facets of this general
subject [1, 2, 3, 6, 25].
1.2 Introducing distrust
Recent works [14, 21] give a mathematical approach to
the propagation of trust, but do not extend to the case in
which users may also express distrust. However, experience
with real-world implemented trust systems such as Epinions
and eBay suggests that distrust is at least as important as
trust. In the absence of treatment of distrust in prior work,
it is unclear how to model and propagate distrust. For instance:
does a trust score of 0 translate to distrust or to ‘no
opinion’? Merely shifting all trust scores so that no negative
values remain (and then using a trust propagation method
such as [14]) will not address this fundamental issue; such a
“shift” would be sensitive to outliers and additionally distort
the semantics of a zero score.
Modeling distrust as negative trust raises a number of
challenges—both algorithmic and philosophical. For instance,
the principal eigenvector of the matrix of trust values need
no longer be real. This is a barrier to approaches in which
the trust matrix is turned into a Markov chain (what do
negative probabilities mean?) and the principal eigenvector
is interpreted as an absolute measure of trust for each
node. In fact, our goal is not an absolute measure of trust
for each node—rather, we wish to determine a measure of
trust from any node to any other. Another challenge: what
does it mean to combine distrusts through successive people
in a chain? One of the main contributions of our paper is to
address this situation. We try to develop an understanding
of appropriate models for the propagation of distrust (Section
3.2.1 and Section 3.3). One of our findings is that even
a small amount of information about distrust (rather than
information about trust alone) can provide tangibly better
judgments about how much user i should trust user j.
1.3 Summary of results
Typical webs of trust tend to be relatively “sparse”: virtually
every user has expressed trust values for only a handful
other users. A fundamental problem is using such webs is
that of determining trust values for the majority of user pairs
for whom we have not explicitly received a trust rating.
Mechanisms for addressing this problem have been studied
in economics, computer science and marketing, albeit
typically without a computational component. We present a
broad taxonomy of schemes for propagation of trust through
a network of relationships, and evaluate 81 combinations of
trust and distrust propagation against a large collections of
expressed trusts provided by Epinions. To our knowledge,
this is the first empirical study on a large, real, deployed
web of trust.
We rank different propagation mechanisms mostly from
the perspective of predictive accuracy, in the following sense:
our experiments involve masking a portion of the known
trust ratings and predicting these from the remainder —
a leave-one-out cross-validation. The hope is that a better
understanding of what is correct will lead to better approximations
to accuracy.
The remainder of the paper proceeds as follows. Section 2
covers related work. Section 3 then describes our algorithms,
and the taxonomy of mechanisms that ties them together.
Section 4 covers the web of trust we analyze. In Section 5
we provide experimental results comparing the algorithms
and draw conclusions about the effectiveness of trust propagation
on real-world data.
2. RELATEDWORK
A number of disciplines have looked at various issues related
to trust, including the incremental value assigned by
people to transacting with a trusted party and how trust
affects people’s beliefs and decision making.
Kahneman et al. [13] were among the first to study these
phenomena in the context of decision making. There is also a
substantial body of work on understanding trust in the field
of political science [9, 18, 23]. One could draw a number
of useful lessons from these fields, especially in assigning
semantics to trust statements; unfortunately, that work is
not computational in nature.
There has been considerable work on trust in computer
science, most of it focused in the area of security. Formal
logical models [8, 10] have been used to in the context of
cryptography and authentication. PGP [24] was one of first
popular systems to explicitly use the term “Web of Trust”,
though it was not in the context of search or information
flow. We believe that the same kind of trust relations between
agents can be used for a much wider range of applications
than just for belief in statements about identity.
Gladwell’s popular book “The Tipping Point” [11] studies
the way information flows are mediated by the networks of
people and their associated trust relations.
There has been substantial work in the business management
community on the value of trust. Ackerlof’s classic [1]
showed the importance of information regarding the quality
of a product (or service). Ackerlof showed how information,
i.e., knowledge about the trustworthiness of a seller, is vital
for the functioning of a market. Trust is an important aspect
of on-line communities. Armstrong and Hagel [2] posit the
importance of trust and community for on-line commerce.
Recently, due to the emergence of e-commerce, there has
been work in the area of developing computational models of
trust. Ba,Whinston, and Zhang [5] provide a game theoretic
approach of trust and conclude that in the presence of an
authenticating third party, the most utilitarian course of
action for a (market) user is to behave honestly. There have
been a number of proposed models and empirical studies of
the eBay trust model [12, 16, 17, 19, 20, 22]. However, that
line of work has not considered models of propagating trust.
In the last few years, a number of researchers have started
looking at the problem of propagating trust through networks.
Yu and Singh [25] propose a framework which, in
contrast to our work, assumes symmetry and arbitrary transitivity.
Kamvar, Schlosser, and Garcia-Molina [14] consider
404
trust propagation in a peer-to-peer environment and provide
an approach that is close to one of our techniques, without
the incorporation of distrust. Further, their goal is to assign
to each node an universal measure of trust (analogous to the
Pagerank measure for web pages), rather on a pairwise basis
as we seek to. In general, most of the work on trust propagation
has been inhibited by the lack of empirical data. Very
recently, Richardson, Agrawal, and Domingos [21] develop
a “path-algebra” model of trust propagation which is the
closest to ours; moreover, like us, they use data from Epinions
to validate their algorithms. To our knowledge, these
are the only attempts at a comparative analysis of different
propagation algorithms based on a real, large, data set.
Moreover, none of the above algorithms attempts to model
distrust in any manner.
3. ALGORITHMS
In this section we describe a framework for trust prediction
and develop algorithms in this framework. In Section 5
we compare a number of these algorithms, including most
popular propagation schemes.
We assume a universe of n users, each of which may optionally
express some level of trust and distrust for any other
user. These values can be viewed as a real-valued matrix;
however, to keep our development clean, we will in fact partition
its entries into two matrices, one for trust and the
other for distrust. We take T to be the matrix of trusts; tij
is the trust that user i holds for user j. The values tij are
assumed to lie between 0 and 1. Similarly, we take D to be
the matrix of distrusts, in which dij again lies between 0 and
1. This formulation is slightly redundant: it allows a user
to express both trust and distrust with respect to another
user.1 The main goal of our work is to predict an unknown
trust/distrust value between any two users, using the entries
available in the trust and distrust matrices.
We will use matrix B to represent a set of beliefs that we
hold about the world. In different contexts, Bij might be
i’s trust of j, or a combination of i’s trust and distrust of
j. We can then define a generic operation on B that can
be applied to trusts alone (T), or to trusts combined with
distrusts (typically, T − D).
We now give an intuitive description of a single trust propagation
step, to be formalized in Section 3.1. Say we already
know that i trusts j, and we wish to apply the knowledge
that j trusts k. In one propagation step, we might be able
to guess that i trusts k. We refer to this operation as an
atomic propagation since the conclusion is reached based on
a single argument, rather than a possibly lengthy chain of
arguments. As a more complex example of an atomic propagation,
say that once again i trusts j. This time, we wish to
apply the knowledge that k trusts both j and `. Since i and
k both trust j, they might share a common worldview; thus,
since k trusts `, perhaps i should also trust `. We will show
how to encode these and other propagations as a single matrix
operator. Multiplying a belief matrix by this operator
will correspond to applying the single step of propagation.
Next, in Section 3.2, we will describe how to apply a series
of k atomic propagations in sequence. For a positive integer
k, we will refer to P(k) as the operator for this sequence of k
propagations. Finally, we will describe how to produce our
1In our experiments, all entries are drawn from {0, 1}, but
our algorithms do not require this.
Name Meaning
T Trust matrix—Tij is i’s trust of j.
D Distrust matrix—Dij is i’s distrust of j.
B Beliefs—B is generically either T or T − D.
CB, Combined atomic propagation matrix.
P(k) k-step Propagation matrix.
F Final beliefs—Fij is i’s trust of j.
Table 1: Glossary of all matrix names used throughout
the text.
final set of beliefs F in terms of these intermediate forms. Fij
will then represent the final trust that i should hold for j. As
the number of named matrices is somewhat overwhelming,
Table 1 gives all the descriptions.
3.1 Atomic propagation
We now formalize the notion of atomic propagation described
above. Consider a “basis set” of techniques by which
the system may infer that one user should trust or distrust
another. Each element of the basis set extends a conclusion
(such as the conclusion that i trusts j) by a constant-length
sequence of forward and backward steps in the graph of expressed
trusts. We require that any inference regarding trust
should be expressible as a combination of elements of this
basis set.2
For example, if Bij = 1 indicating that i trusts j, and
Bjk = 1 indicating that j trusts k, then an atomic propagation
would allow us to infer that i trusts k; we refer
to this particular atomic propagation as direct propagation
since the trust propagates directly along an edge. We will
present such propagations as operators that can be applied
to the initial belief matrix B to yield conclusions that can
be supported in a single step; we will then chain these operators
together. We begin by expressing direct propagation
as a matrix M such that all conclusions expressible by direct
propagation can be read from the matrix B·M. We observe
that the appropriate matrix M to encode direct propagation
is simply B itself: in this case B ·M = B2, which is the
matrix of all length-2 paths in our initial belief graph—for
instance, the i ! j ! k path we used in our example in
Figure 1. Thus, B itself is the operator matrix that encodes
the direct propagation basis element.
Another candidate basis element described above is cocitation.
For example, suppose i1 trusts j1 and j2, and
i2 trusts j2. Under co-citation, we would conclude that i2
should also trust j1. The operator M for this atomic propagation
is BTB. A little checking will verify that B · M,
which yields BBTB, will, in fact, capture all beliefs that
are inferable through a single co-citation, as shown in the
bottom of Figure 1. The sequence BTB can be viewed as a
backward-forward step propagating i2’s trust of j2 backward
to i1, then forward to j1.
We also consider transpose trust, in which i’s trust of j
causes j to develop some level of trust towards i. And finally,
2Generally, the basis elements may be any family of matrix
operations using B. We restrict ourselves to sequences of
forward and backward steps following non-zero entries of B
since these capture a general and natural set of propagations.
405
Figure 1: Example of basis elements: Direct propagation
and co-citation. The dotted lines indicate
trust propagation.
trust coupling, in which i’s trust of j propagates to k because
j and k trust people in common. These atomic propagations
are summarized in Table 2.
Atomic Propagation Operator Description
Direct propagation B See top of Figure 1.
Co-citation BTB See bottom of Figure
1.
Transpose trust BT If a trusts b then
trusting b should imply
trusting a.
Trust coupling BBT a, b trust c, so trusting
a should imply
trusting b.
Table 2: Atomic propagations.
Let = (1, 2, 3, 4) be a vector representing weights
for combining our four atomic propagation schemes. Then
we can capture all the atomic propagations into a single
combined matrix CB, based on a belief matrix B and a
weight vector as follows:
CB, = 1B + 2BTB + 3BT + 4BBT .
We now explore how those atomic propagations may be
chained together.
3.2 Propagation of trust and distrust
Our end goal is to produce a final matrix F from which
we can read off the computed trust or distrust of any two
users. In the remainder of this section, we first propose two
techniques for computing F from CB,. Next, we complete
the specification of how the original trust T and distrust D
matrices can be combined to give B. We then describe some
details of how the iteration itself is performed to capture two
distinct views of how distrust should propagate. Finally, we
describe some alternatives regarding how the final results
should be interpreted.
3.2.1 Propagation of distrust
As described above, let CB, be a matrix whose ij-th
entry describes how beliefs should flow from i to j via an
atomic propagation step; if the entry is 0, then nothing can
be concluded in an atomic step about i’s views on j. Let k
be a positive integer and let P(k) be a matrix whose ij-th
entry represents the propagation from i to j after k atomic
propagations. In other words, beginning with a belief matrix
B, we will arrive at a new belief matrix after k steps. Thus,
the repeated propagation of trust is expressed as a matrix
powering operation.
We give three models to define B (the belief matrix) and
P(k) for the propagation of trust and distrust, given initial
trust and distrust matrices T and D respectively:
(1) Trust only: In this case, we ignore distrust completely,
and simply propagate trust scores. The defining
matrices then become
B = T, P(k) = CkB
,.
(2) One-step distrust: Assume that when a user distrusts
somebody, they also discount all judgments made by
that person; thus, distrust propagates only a single step,
while trust may propagate repeatedly. In this case, we have
B = T, P(k) = CkB
, · (T − D).
(3) Propagated distrust: Assume that trust and distrust
both propagate together, and that they can be treated
as two ends of a continuum. In this case, we take
B = T − D, P(k) = CkB
,.
3.2.2 Iterative propagation
We can now compute new beliefs based on k steps of
atomic propagations. We now wish to define F, the final
matrix representing the conclusions any user should draw
about any other user. But the matrix P(k) for smaller values
of k may be more reliable, since there have been fewer propagation
steps; while larger values of k may bring in more
outside information. We consider two natural approaches
to inferring final trust scores from our sequences of propagations.
(1) Eigenvalue propagation (EIG): Let K be a suitably
chosen (discussed later) integer. Then, in this model,
the final matrix F is given by
F = P(K).
(2) Weighted linear combinations (WLC): Let
be
a constant (that is smaller than the largest eigenvalue of
CB,) and let K be a suitably chosen integer. (
is a discount
factor to penalize lengthy propagation steps.) Under
this model, F is given by
F =
XK
k=1
k · P(k).
3.2.3 Rounding
Finally, the result values of F must be interpreted as
either trust or distrust. While continuous-valued (rather
than discrete-valued) trusts are mathematically clean [21],
we work on the assumption that from the standpoint of usability
most real-world systems will in fact use discrete values
at which one user can rate another. While our mathematical
development (like previous work) has been in the
continuous domain, we now consider the “rounding” problem
of converting continuous belief values from an arbitrary
range into discrete ones (such as ±1). This corresponds to
406
+ + + - - + + + + + ? + + - + - - - - - - -
j
Figure 2: Prediction of j based on the majority of
labels of neighbors of i (+ means trust and - means
distrust) sorted by the trust scores. Here, the prediction
would be +.
applications that demand a Boolean yes/no judgment to the
question “Should i trust j?” (Such Boolean rounding is also
necessary for our cross-validation experiments in Section 5.)
This is tantamount to rounding the entries in matrix F to
either trust or distrust. We discuss three ways this rounding
can be accomplished.
(1) Global rounding: This rounding tries to align the
ratio of trust to distrust values in F to that in the input
M. Consider the row vector Fi. We judge that i trusts j if
and only if Fij is within the top fraction of entries of the
vector Fi, under the standard < ordering. The threshold
is chosen based on the overall relative fractions of trust and
distrust in the (sparse) input.
(2) Local rounding: Here, we take into account the
trust/distrust behavior of i. As before, we judge that i trusts
j if and only if Fij is within the top fraction of entries of
the vector Fi, under the standard < ordering. The threshold
is chosen based on the relative fraction of trust vs. distrust
judgments made by i.
(3) Majority rounding: The motivation behind this
rounding is to capture the local structure of the original
trust and distrust matrix. Consider the set J of users on
whom i has expressed either trust or distrust. Think of J
as a set of labeled examples using which we are to predict
the label of a user j, j /2 J. We order J along with j according
to the entries Fij0 where j0 2 J [{j}. At the end of
this, we have an ordered sequence of trust and distrust labels
with the unknown label for j embedded in the sequence
at a unique location (see Figure 2). We now predict label
of j to be that of the majority of the labels in the smallest
local neighborhood surrounding it where the majority is
well-defined.
More sophisticated notions of rounding are possible. Notice
above that local rounding and majority rounding are “icentric”.
A j-centric definition is possible in a similar manner.
Also note that our notion of majority rounding tries
to exploit clustering properties. It is possible to derive improved
rounding algorithms by using better one-dimensional
clustering algorithms.
Our results show that the rounding algorithm is of significant
importance in the predictiveness of the system.
3.3 On the transitivity of distrust
It seems clear that if i trusts j, and j trusts k, then i
should have a somewhat more positive view of k based on
this knowledge. In the realm of distrust, however, this transitivity
might not hold. Assume i distrusts j, who distrusts
k. Perhaps i is expressing the view that j’s entire value
model is so misaligned with i’s that anyone j distrusts is
more likely to be trusted by i (“the enemy of your enemy is
your friend”). Alternately, however, perhaps i has concluded
that j’s judgments are simply inferior to i’s own, and j has
concluded the same about k—in this case, i should strongly
distrust k (“don’t respect someone not respected by someone
you don’t respect”). We call the former notion multiplicative
and the latter additive distrust propagation.
Multiplicative trust propagation has some unexpected sideeffects:
a directed cycle around which the trust/distrust
values have a negative product imply that iterated propagation
will lead a user to distrust himself! Moreover, such
iterated propagation will over time generate a final belief
that negates and overwhelms the user’s explicitly expressed
belief. Nevertheless, we cannot ignore multiplicative trust
propagation because it has some philosophical defensibility.
This problem results because trust and distrust are complex
measures representing people’s multi-dimensional utility
functions, and we seek here to represent them as a single
value. Rather than propose that one answer is more likely
to be correct, one can define two corresponding algebraic
notions of distrust propagation that may be appropriate for
different applications. Notice that by virtue of matrix multiplication,
all our earlier definitions implement the multiplicative
notion, if we use the trust/distrust values per se.
One way to implement the additive distrust notion in our
framework is by transforming the matrix M to M0 before
applying the iteration, as follows: