Social networks in which users or agents are connected to other agents and sources by trust relations are an important part of many web applications where information may come from multiple sources. Trust recommendations derived from these social networks are supposed to help agents develop their own opinions about how much they may trust other agents and sources. Despite the recent developments in the area, most of the trust models and metrics proposed so far tend to lose trust-related knowledge. We propose a new model in which trust values are derived from a bilattice that preserves valuable trust provenance information including partial trust, partial distrust, ignorance and inconsistency. We outline the problems that need to be addressed to construct a corresponding trust learning mechanism. We present initial results on the first learning step, namely trust propagation through trusted third parties (TTPs).
As intelligent agents in the semantic web take over more and more human tasks, they require an automated way of trusting each other. One of the key problems in establishing this, is related to the dynamicity of trust: to grasp how trust
The University of Texas at El Paso
Dept. of Computer Science
El Paso, TX 79968, USA
emerges and vanishes. Once an understanding is reached,
a new problem arises: how can the cyberinfrastructure be
used to manage trust among users? To this aim, it is very
important to find techniques that capture the human notions
of trust as precisely as possible. Quoting [
If people can use their everyday trust building methods for the cyberinfrastructure and through it reach out to fellow human beings in far-away places, then that would be the dawn of the real Information Society for all.
In the near future, more and more applications and
systems will need solid trust mechanisms. In fact, effective trust
models already play an important role in many intelligent
web applications, such as peer-to-peer (P2P) networks [
Existing trust models can be classified in several ways, among which probabilistic vs. gradual approaches as well as representations of trust vs. representations of both trust and distrust. This classification is shown in Table 1, along with some representative references for each class.
Many models deal with trust in a binary way — an agent
(or source) can either be trusted or not — and compute the
probability or belief that the agent can be trusted [
Apart from complete trust or no trust at all, however, in
real life we also encounter partial trust. For instance, we
ofprobabilistic
gradual
ten say “I trust this person very much”, or “My trust in this
person is rather low”. More recent models like [
Large agent networks without a central authority typically
face ignorance as well as inconsistency problems. Indeed, it
is likely that not all agents know each other, and different
agents might provide contradictory information. Both
ignorance and inconsistency can have an important impact on
the trust score computation. Models that only take into
account trust (e.g. [
Recent publications [
SL is an example of a probabilistic approach, whereas in
this paper we will outline a trust model that uses a
gradual approach, meaning that agents can be trusted to some
degree. Furthermore, to preserve provenance information,
our model deals with distrust in addition to trust.
Consequently, we can represent partial trust and partial distrust.
Our intended approach is situated in the bottom right
corner of Table 1. As far as we know, besides our own earlier
work [
Our long term goal is to develop a model of trust that
preserves trust provenance as much as possible. A previous
model we introduced in [
First of all, in Section 2, we point out the importance of a provenance-preserving trust model by means of some examples. In Section 3, we introduce the bilattice-based concept of a trust score space, i.e. a set of trust scores equipped with both a trust ordering and a knowledge ordering, and we provide a definition for a trust network. In developing a trust learning mechanism that is able to compute trust scores we will need to solve many challenging problems, such as how to propagate, aggregate, and update trust scores. In Section 4, we reflect upon our initial tinkering on candidate operators for trust score propagation through trusted third parties (TTPs). As these trust propagation operators are currently shaped according to our own intuitions, we will set up an experiment in the near future to gather the necessary data that provides insight in the propagation of trust scores through TTPs. We briefly comment on this in Section 5. Finally, subsequent problems that need to be addressed are sketched. 2.
The main aim in using trust networks is to allow users or agents to form trust opinions on unknown agents or sources by asking for a trust recommendation from a TTP who, in turn, might consult its own TTP etc. This process is called trust propagation. In large networks, it often happens that an agent does not ask one TTP’s opinion, but several. Combining trust information received from more than one TTP is called aggregation (see fig. 1). Existing trust network models usually apply suitable trust propagation and aggregation operators to compute a resulting trust value. In passing on this trust value to the inquiring agent, valuable information on how this value has been obtained is lost.
User opinions, however, may be affected by provenance information exposing how trust values have been computed. For example, a trust recommendation in a source from a fully informed TTP is quite different from a trust recommendation from a TTP who does not know the source too well but has no evidence to distrust it. Unfortunately, in current models, users cannot really exercise their right to interpret how trust is computed since most models do not preserve trust provenance.
Trust networks are typically challenged by two important problems influencing trust recommendations. Firstly, in large networks it is likely that many agents do not know each other, hence there is an abundance of ignorance. Secondly, because of the lack of a central authority, different agents might provide different and even contradictory information, hence inconsistency may occur. Below we illustrate how ignorance and inconsistency may affect trust recommendations.
example 1 (Ignorance). Agent a needs to establish
an opinion about agent c in order to complete an important
bank transaction. Agent a may ask agent b for a
recommendation of c because agent a does not know anything about c.
Agent b, in this case, is a recommender that knows how to
compute a trust value of c from a web of trust. Assume that
b has evidence for both trusting and distrusting c. For
instance, let us say that b trusts c 0.5 in the range [
In this scenario, by getting the trust value 0.5 from b,
a is losing valuable information indicating that b has some
evidence to distrust c too. A similar problem occurs using
the approach of Guha et al. [
example 2 (Ignorance). Agent a needs to establish an opinion about both agents c and d in order to find an efficient web service. To this end, agent a calls upon agent b for trust recommendations on agents c and d. Agent b completely distrusts agent c, hence agent b trusts agent c to degree 0. On the other hand agent b does not know agent d, hence agent b trusts agent d to degree 0. As a result, agent b returns the same trust recommendation to agent a for both agents c and d, namely 0, but the meaning of this value is clearly different in both cases. With agent c, the lack of trust is caused by a presence of distrust, while with agent d, the absence of trust is caused by a lack of knowledge. This provenance information is vital for agent a to make a well informed decision. For example, if agent a has a high trust in TTP b, agent a will not consider agent c anymore, but agent a might ask for other opinions on agent d.
example 3 (Contradictory Information). One of your friends tells you to trust a dentist, and another one of your friends tells you to distrust that same dentist. In this case, there are two TTPs, they are equally trusted, and they tell you the exact opposite thing. In other words, you have to deal with inconsistent information. What would be your aggregated trust score in the dentist? Models that work with only one scale can not represent this: taking e.g. 0.5 as trust score (i.e. the average) is not a solution, because then we can not differentiate from a situation in which both of your friends trust the dentist to the extent 0.5.
Furthermore, what would you answer if someone asks you if the dentist can be trusted? A possible answer is: “I don’t really know, because I have contradictory information about this dentist”. Note that this is fundamentally different from “I don’t know, because I have no information about him”. In other words, a trust score of 0 is not a suitable option either, as it could imply both inconsistency and ignorance.
The examples above indicate the need for a model that preserves information on whether a “trust problem” is caused by presence of distrust or rather by lack of knowledge, as well as whether a “knowledge problem” is caused by having too little or rather too much, i.e. contradictory, information. 3.
We need a model that, on one hand, is able to represent the trust an agent may have in another agent in a given domain, and on the other hand, can evaluate the contribution of each aspect of trust to the overall trust score. As a result, such a model will be able to distinguish between different cases of trust provenance. To this end, we introduce a new structure, called trust score space BL .
Definition 1 space
(Trust Score Space). The trust score
BL = ([
The negation ¬ serves to impose a relationship between the
lattices ([
Figure 2 shows the bilattice BL , along with some
examples of trust scores. The first lattice ([
The trust score space allows our model to preserve trust
provenance by simultaneously representing partial trust,
partial distrust, partial ignorance and partial inconsistency, and
treating them as different, related concepts. Moreover, by
using a bilattice model the aforementioned problems
disappear:
1. By using trust scores we can now distinguish full
distrust (0,1) from ignorance (0,0) and analogously, full
trust (1,0) from inconsistency (1,1). This is an
improvement of e.g. [
The available trust information is modeled as a trust network that associates with each couple of agents a score drawn from the trust score space.
Definition 2 (Trust Network). A trust network is a couple (A, R) such that A is a set of agents and R is a A × A → BL mapping. For every a and b in A, we write
R(a, b) = R+(a, b), R−(a, b) • R(a, b) is called the trust score of a in b. • R+(a, b) is called the trust degree of a in b.
• R−(a, b) is called the distrust degree of a in b. R should be thought of as a snapshot taken at a certain moment, since the trust learning mechanism involves recalculating trust scores, for instance through trust propagation as discussed next.
We often encounter situations in which we need trust information about an unknown person. For instance, if you are in search of a new dentist, you can ask your friends’ opinion about dentist Evans. If they do not know Evans personally, they can ask a friend of theirs, and so on. In virtual trust networks, propagation operators are used to handle this problem. The simplest case (atomic propagation) can informally be described as (fig. 3): if the trust score of agent a in agent b is p, and the trust score of b in agent c is q, what information can be derived about the trust score of a in c? When propagating only trust, the most commonly used operator is multiplication. When taking into account also distrust, the picture gets more complicated, as the following example illustrates.
example 4. Suppose agent a trusts agent b and agent b distrusts agent c. It is reasonable to assume that based on this, agent a will also distrust agent c, i.e. R(a, c) = (0, 1). Now, switch the couples. If a distrusts b and b trusts c, there are several options for the trust score of a in c: a possible reaction for a is to do the exact opposite of what b recommends, in other words to distrust c, R(a, c) = (0, 1). But another interpretation is to ignore everything b says, hence the result of the propagation is ignorance, R(a, c) = (0, 0).
As this example indicates, there are likely multiple possible propagation operators for trust scores. We expect that the choice for a particular BL × BL → BL mapping to model the trust score propagation will depend on the application and the context but might also differ from person to person. Thus, the need for provenance-preserving trust models becomes more evident.
To study some possible propagation schemes, let us first consider the bivalent case, i.e. when trust and distrust degrees assume only the values 0 or 1. For agents a and b, we use R+(a, b), R−(a, b), and ∼R−(a, b) as shorthands for respectively R+(a, b) = 1, R−(a, b) = 1 and R−(a, b) = 0. We consider the following three, different propagation schemes (a, b and c are agents): 1. R+(a, c) ≡ R+(a, b) ∧ R+(b, c)
R−(a, c) ≡ R+(a, b) ∧ R−(b, c) 2. R+(a, c) ≡ R+(a, b) ∧ R+(b, c)
R−(a, c) ≡ ∼R−(a, b) ∧ R−(b, c) 3. R+(a, c) ≡ (R+(a, b) ∧ R+(b, c)) ∨ (R−(a, b) ∧ R−(b, c))
R−(a, c) ≡ (R+(a, b) ∧ R−(b, c)) ∨ (R−(a, b) ∧ R+(b, c)) In scheme (1) agent a only listens to whom he trusts, and ignores everyone else. Scheme (2) is similar but in addition agent a takes over distrust information from a not distrusted (hence possibly unknown) third party. Scheme (3) corresponds to an interpretation in which the enemy of an enemy is considered to be a friend, and the friend of an enemy is considered to be an enemy.
In our model, besides 0 and 1, we also allow partial trust and distrust. Hence we need suitable extensions of the logical operators that are used in (1), (2) and (3). For conjunction, disjunction and negation, we use respectively a t-norm T , a t-conorm S and a negator N . They represent large classes of logic connectives, from which specific operators, each with their own behaviour, can be chosen, according to the application or context.
T and S are increasing, commutative and associative [
Generalizing the logical operators in scheme (1), (2), and (3) accordingly, we obtain the propagation operators of Table 2. Each one can be used for modeling a specific behaviour. Starting from a trust score (t1, d1) of agent a in agent b, and a trust score (t2, d2) of agent b in agent c, each propagation operator computes a trust score for agent a in agent c. Since the resulting value is again an element of the trust score space, trust provenance is preserved.
The remainder of this section is devoted to the investigation of some potentially useful properties of these propagation operators. In doing so, we keep the logical operators as generic as possible, in order to get a clear view on their general behaviour. First of all, if one of the arguments of a propagation operator can be replaced by a higher trust score w.r.t. to the knowledge ordering without decreasing the resulting trust score, we call the propagation operator knowledge monotonic.
Definition 3 (Knowledge Monotonicity). A propagation operator f on BL is said to be knowledge monotonic iff for all x, y, z, and u in BL ,
x ≤k y and z ≤k u implies f (x, z) ≤k f (y, u)
Knowledge monotonicity reflects that the better you know how well you should trust or distrust user b who is recommending user c, the better you know how well to trust or distrust user c. Although this behaviour seems natural, not all operators of Table 2 abide by it.
Proposition 1. Prop1 and Prop3 are knowledge monotonic. Prop2 is not knowledge monotonic.
Proof. The knowledge monotonicity of Prop1 and Prop3 follows from the monotonicity of T and S. To see that Prop2 is not knowledge monotonic, consider
Prop2((0.2, 0.7), (0, 1)) = (0, 0.3)
Prop2((0.2, 0.8), (0, 1)) = (0, 0.2), with Ns as negator. We have that (0.2, 0.7) ≤k (0.2, 0.8) and (0, 1) ≤k (0, 1) but (0, 0.3) k (0, 0.2).
The intuitive explanation behind the non knowledge monotonic behaviour of Prop2 is that, using this propagation operator, agent a takes over distrust from a stranger b, hence giving b the benefit of the doubt, but when a starts to distrust b (thus knowing b better), a will adopt b’s opinion to a lesser extent (in other words: a derives less knowledge).
Knowledge montonicity is not only useful to provide more insight in the propagation operators but it can also be used to establish a lower or upper bound for the actual propagated trust score without immediate recalculation. This might be useful in a situtation where one of the agents has updated its trust score in another agent and there is not enough time to recalculate the whole propagation chain.
Besides atomic propagation, we need to be able to consider longer propagation chains, so TTPs can in turn consult their own TTPs and so on. Prop1 turns out to be associative, which means that we can extend it for more scores without ambiguity.
Proposition 2. (Associativity): Prop1 is associative, i.e. for all x, y, and z in BL it holds that:
Prop1(Prop1(x, y), z) = Prop1(x,Prop1(y, z)) Prop2 and Prop3 are not associative.
Proof. The associativity of Prop1 can be proved by taking into account the associativity of the t-norm. Examples can be constructed to show that the other two propagation operators are not associative. Take for example N (x) = 1 − x and T (x, y) = x · y, then Prop2((0.3, 0.6),Prop2((0.1, 0.2), (0.8, 0.1))) = (0.024, 0.032) while on the other hand Prop2(Prop2((0.3, 0.6), (0.1, 0.2)), (0.8, 0.1)) = (0.024, 0.092)
With an associative propagation operator, the overall trust score computed from a longer propagation chain is independent of the choice of which two subsequent trust scores to combine first. When dealing with a non associative operator however, it should be specified which pieces of the propagation chain to calculate first.
Finally, it is interesting to note that in some cases the overall trust score in a longer propagation chain can be determined by looking at only one agent. For instance, if we use Prop1 or Prop3, and there occurs a missing link (0, 0) anywhere in the propagation chain, the result will contain no useful information (in other words, the final trust score is (0, 0)). Hence as soon as one of the agents is ignorant, we can dismiss the entire chain. Notice that this also holds for Prop3, despite the fact that it is not an associative operator. Using Prop1, the same conclusion (0, 0) can be drawn if at any position in the chain, except the last one, there occurs complete distrust (0, 1). 5.
We have introduced a new model that can simultaneously handle partial trust and distrust. We showed that our bilattice-based model alleviates some of the existing problems of trust models, more specifically concerning trust provenance. In addition, this new model can handle incomplete and excessive information, which occurs frequently in virtual communities, such as the WWW in general and trust networks in particular. Therefore, this new provenancepreserving trust model can lead to an improvement of many existing web applications, such as P2P networks, question answering systems and recommender systems.
A first step in our future research involves the further development and the choice of trust score propagation operators. Of course, the trust behaviour of users depends on the situation and the application, and is in most cases relative to a goal or a task. A friend e.g. can be trusted for answering questions about movies, but not necessarily about doctors. Therefore, we are preparing some specific scenario’s in which trust is needed to make a certain decision (e.g. which doctor to visit, which movie to see). According to these scenario’s, we will prepare questionnaires, in which we aim to determine how propagation of trust scores takes place. Gathering such data, we hope to get a clear view on trust score propagation in real life, and how to model it in applications. We do not expect to find one particular propagation schema, but rather several, depending on a persons nature. When we obtain the results of the questionnaire, we will also be able to verify the three propagation operators we proposed in this paper. Furthermore, we would like to investigate the behaviour of the operators when using particular t-norms, t-conorms and negators, and examine whether it is possible to use other classes of operators that do not use t-(co)norms.
A second problem which needs to be addressed, is
aggregation. In our domain of interest, namely a gradual
approach to both trust and distrust, there are no aggregation
operators yet. We will start by investigating whether it is
possible to extend existing aggregation operators, like e.g.
the ordered weighted averaging aggregation operator [
Finally, trust and distrust are not static, they can change after a bad (or good) experience. Therefore, it is also necessary to search for appropriate updating techniques.
Our final goal is the creation of a framework that can represent partial trust, distrust, inconsistency and ignorance, that contains appropriate operators (propagation, aggregation, update) to work with those trust scores, and that can serve as a starting point to improve the quality of many web applications. In particular, as we are aware that trust is experienced in different ways, according to the application and context, we aim at a further development of our model for one specific application.
Patricia Victor would like to thank the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen) for funding her research. Chris Cornelis would like to thank the Research Foundation-Flanders for funding his research.