=Paper=
{{Paper
|id=Vol-202/paper-11
|storemode=property
|title=The Measurable Belief of Trust in Social Networks
|pdfUrl=https://ceur-ws.org/Vol-202/SEMDESK2006_0036.pdf
|volume=Vol-202
|dblpUrl=https://dblp.org/rec/conf/semweb/Noh06
}}
==The Measurable Belief of Trust in Social Networks==
https://ceur-ws.org/Vol-202/SEMDESK2006_0036.pdf
The Measurable Belief of Trust in Social Networks ∗
Sanguk Noh
School of Computer Science and Information Engineering,
The Catholic University of Korea, Bucheon, Korea
sunoh@catholic.ac.kr
Abstract. As Web-based online communities are rapidly growing, the agents in
social groups need to know their measurable belief of trust for safe and success-
ful interactions. In this paper, we propose a formal model of reputation result-
ing from available feedbacks in online communities. The notion of trust can be
defined as an aggregation of consensus given a set of reputations. The expected
trust of an agent further represents the center of gravity of the distribution of its
trustworthiness and untrustworthiness. And then, we precisely describe the rela-
tionship between reputation, trust, and expected trust through a concrete exam-
ple of their computations. We apply our trust model to online Internet settings
in order to show how the trust is involved in a rational decision-making of the
agents.
Keywords: Trust within social networks, consensus aggregation, Dempster-
Shafer, adaptive multi-agent systems
1 Introduction
Traditional notion of trust [3] refers to an agent’s belief that other agents towards
itself intend to be honest and positive, and can be usually built up through direct
interactions in person. As online communities on the Internet are rapidly growing, the
agents have exposed to virtual interactions as well as face-to-face interactions. The
agents in online social networks communicate anonymously and have only limited
inspections. These features have made the agents hard to decide whether or not other
agents may be positive or benevolent to them. Thus, it is essential that they could
have a tangible model of trust for safe and successful interactions, even in the case
that they don’t have prior and direct interactions. This paper addresses how to assess
trust in social networks, particularly applicable to the online community. We build up
the computational model of trust as a measurable concept.
Our approach to the computational model of trust starts with the lesson from “Tit
for Tat” strategy in game theory for the iterated Prisoner’s Dilemma [1], which en-
courages social cooperation among agents. As a result of mutual behaviors in online
multi-agent settings, agents will get more positive feedbacks from other agents if the
∗ This work has been supported by the Catholic University of Korea research fund, and de-
partment specialization fund, respectively, granted in the program year of 2006.
agents are willing to cooperate with others and, otherwise, they will receive more
negative feedbacks from others. We translate the feedbacks resulting from social
activities into the agent’s reputation as a quantitative concept. The next steps for our
trust model are to apply aggregation rules to given reputation values to reach a con-
sensus, and calculate the expected trust interpreted as the center of gravity of the
distributions of trustworthiness and untrustworthiness. The notion of trust in our
framework then represents positive expectations about others’ future behaviors.
In the following section of this paper, we briefly compare our approach to related
research. Section 3 is devoted to our trust model that defines reputation, trust, and
expected trust. We precisely describe the relationship among them through a concrete
example of their computations. In Section 4, we apply our trust model to online Inter-
net transactions showing how trust affects a rational decision-making of buyers and
sellers. In the concluding Section 5, we summarize our work and mention further
research issues.
2 Related Work
Our work builds on efforts by several other researchers who have made the social
concept of trust computable in a society of multi-agents. In the field of multi-agent
community, there have been several approaches to support a computational model of
trust. Marsh [10] introduces a simple, computational model of trust, which is a sub-
jective real number ranging from -1 to 1. His model has trouble with handling nega-
tive values of trust and their propagation. Mui et al. [11] describe trust in a pseudo-
mathematical expression and represent it as posteriors using expected utility notation.
Their scheme only counts the number of cooperations (or positive events). In a dis-
tributed reputation system [8], they use aging factor, distance factor, and new experi-
ence to update trust. However, the assumption of these components of trust is not
likely to be realistic. As they pointed out, their scheme does not correctly handle
negative experiences. Our model of trust represents an aggregation of consensus
without any problem of fusion, and effectively deals with the agent’s trustworthiness
and untrustworthiness in the range of 0 and 1, respectively, which are based on actual
positive and negative feedbacks in social networks.
Other rigorous efforts have also focused on the formulation of measurable belief
representing trust. One of them is to use a subjective probability [4, 7] that quantifies
trust as a social belief. In the subjective logic, an agent’s opinion is presented by
degrees of belief, disbelief, and uncertainty. Handling uncertainty in various opera-
tions is too intuitive to be clear. And further, the subjective logic provides not a cer-
tain value of trust but a probability certainty density function. However, our trust
model provides a specific trust value as an expected trust considering agent’s trust-
worthiness and untrustworthiness together. In another approach, a simple e-Bay feed-
back system [13] uses a feedback summary, which is computed as arithmetically
subtracting the number of negative feedbacks from the number of positive feedbacks.
The contribution of our work is to precisely define the notion of trust as a measurable
social belief, and to clearly describe the relationship between reputation, trust, and
expected trust in social multi-agent settings.
3 A Computational Model of Trust
We propose a formal model of reputation resulting from feedbacks in social networks.
The notion of trust then can be defined as an aggregation of consensus given a set of
reputations. The calculation of expected trust, further, results in a precise trust value
as a metric. In this section, we describe the relationship between reputation, trust, and
expected trust through a concrete example of their computations.
3.1 Modeling Reputation
Feedbacks in social networks [6, 13] represent reputation associated with the society
of multiple agents. The cumulative positive and negative events or feedbacks for an
agent, thus, constitute the agent’s reputation [8, 11]. The reputation can be described
by a binary proposition 1 p, for example, “A seller deals with only qualified products
and delivers them on time.” in the field of online Internet transactions. Given a binary
proposition p and an agent-group i judging an agent in p, the reputation of the agent
in p, ωi , can be defined as follows:
p
(1)
ωip = {Ti , U i }
where
• Ti = PFi/Ni and 0≤Ti≤1;
• PFi is the number of positive feedbacks for p within an agent-group i;
• Ui = NFi/Ni and 0≤Ui≤1;
• NFi is the number of negative feedbacks for p within an agent-group i;
• ZFi is the number of neutral feedbacks for p within an agent-group i;
• Ni is the total number of feedbacks for p within an agent-group i and Ni =
PFi+NFi+ZFi.
In the definition of reputation, as described in (1), we assume that the feedbacks
given by agents within an agent-group evaluating p are independent, and further, the
opinions supporting p can be only loosely related to the possible opinions supporting
¬p, since there could be neutral feedbacks from the agent-group. The notion of repu-
tation, thus, is based on independent opinions and the sum of Ti and Ui is not neces-
sarily being 1.
The cumulative positive feedbacks in social networks result from cooperativeness,
i.e., trusting interactions, and establish trustworthiness of an agent in p, while the
possible number of negative feedbacks from the society affects untrustworthiness of
the agent. The trustworthiness and untrustworthiness together constitute a reputation
function as a quantitative concept. The reputation of an agent varies with time and
size of society, and clearly influences its trust. Given a set of reputations, which is
1 Any reputation in the form of proposition can be expressed according to the contexts as fol-
lows: “A buyer has an intention and capability to pay,” “The network system could be safe
from any intrusions,” “A car could be reliable for ten years,” and so on.
collected at different times and from various interactions made by other agent-groups,
the trust as a representative reputation will be derived.
3.2 Calculating Trust Using Aggregation Rules
We define trust as a consensus from an aggregation of reputations. The trust 2 ω
p
for
an agent in a proposition p is defined as
(2)
ω p = ωip ⊗ ω jp = {T , U }
where
• ωip and ω jp represent reputations accumulated from an agent-group i and
an agent-group j, respectively;
• T is the trustworthiness of the agent in a proposition p and 0≤T≤1;
• U is the untrustworthiness of the agent in a proposition p and 0≤U≤1.
The trust, as described in (2), consists of trustworthiness and untrustworthiness.
These two components are determined by a set of reputations, as previously defined
in (1). To formulate the agent’s trust from reputations, expressed in degrees of trust-
worthiness and untrustworthiness which may or may not have the mathematical prop-
erties of probabilities, therefore, we propose a set of aggregation rules [9]. Given
reputations of ωi and ω j , the aggregation operators, ⊗ = {Ψ1 ,..., Ψn } , in the
p p
paper, are as follows:
1. Minimum (Ψ1): T = min(Ti , T j ), U = min(U i , U j ) ;
2. Maximum (Ψ2): T = max(Ti , T j ), U = max(U i , U j ) ;
3. Average (Ψ3): T = (Ti + T j ) / 2, U = (U i + U j ) / 2 ;
4. Product (Ψ4): T = TiT j , U = U iU j ;
5. Dempster-Shafer theory [5, 14, 15] (Ψ5):
TiT j U iU j
T = , U = .
1 − (TiU j + T jU i ) 1 − (TiU j + T jU i )
The trust representing the degrees of belief on agent’s truthfulness can be obtained
by applying aggregation rules to a set of reputations. The goal of aggregation is to
combine reputations when each of them estimates the probability of trustworthiness
2 For the sake of simplicity, we explain our trust model in a much simpler case of two agent-
groups i and j. Our model of trust can be simply extended in more complicated settings in-
volving multiple agent-groups without loss of generality.
and untrustworthiness for an agent, and to produce a single probability distribution
that summarizes the various reputations.
The minimum and maximum aggregation rules provide a single minimum and
maximum value for T and U, respectively. The average aggregation operator simply
extends a statistic summary and provides an average of Tk’s and Uk’s coming from
different agent-groups. The product rule summarizes the probabilities that coincide in
T and U, respectively, given a set of reputations. Dempster’s rule 3 for combining
degrees of belief produces a new belief distribution that represents the consensus of
the original opinions [15]. Using Dempster’s rule, the resulting values of T and U
indicate the degrees of agreement on trustworthiness and untrustworthiness of origi-
nal reputations, respectively, but completely exclude the degrees of disagreement or
conflict. The advantage of using the Dempster’s rule in the context of trust is that no
priors and conditionals are needed.
Among the possible outputs of trust, we denote the trust as the consensus output
using a specific aggregator, which is defined as
ˆ (t , u ) = Ψ ( Ψ (t , u ),..., Ψ (t , u )) (3)
Ψ 1 n
where
• Ψ is a function determining a specific aggregation rule;
• ˆ (t , u ) is the aggregation rule selected with the inputs of t∈Tk and u∈Uk.
Ψ
Example 1. Let ω1 = {0.80, 0.10}, ω2 = {0.70, 0.20}. This is interpreted that
p p
there are two agent-groups evaluating p and, in each group, the resulting number of
positive feedbacks is much greater than that of negative feedbacks, respectively.
Given reputations, aggregation rules can be applied to get trust, as defined in (2),
denoting a consensus out of agent-groups’ opinions. The possible outputs of trust
using the aggregation rules are summarized in Table 1.
Table 1. The example computation of trust using five aggregation rules.
ω1p = {0.80, 0.10}, ω2p = {0.70, 0.20}
Aggregation rules
Trust ω
p
Minimum (Ψ1) {0.70, 0.10}
Maximum (Ψ2) {0.80, 0.20}
Average (Ψ3) {0.75, 0.15}
Product (Ψ4) {0.56, 0.02}
Dempster-Shafer theory (Ψ5) {0.73, 0.03}
For example, when we use Ψ5 as an aggregation rule, the trust given reputations is
calculated as follows:
3 In this paper, a set of original reputations embedded in social networks are assumed to be
consistent in measuring them. This assumption avoids the counterintuitive results obtained
using Dempter’s rule in the presence of significantly conflicting evidence, which was origi-
nally pointed out by Lotfi Zadeh [15].
(0.8)(0.7 )
T = = 0.73;
1 − [(0.8)(0.2) + (0.7 )(0.1)]
(0.1)(0.2)
U = = 0.03.
1 − [(0.8)(0.2) + (0.7)(0.1)]
Among possible outputs of trust, the trust can be denoted as ω ={0.70, 0.10}, when
p
ˆ (t , u ) =Ψ1. When minimum, maximum, and average aggregators are used, the
Ψ
resulting distribution of the trust similarly reflects the distributions of the reputation.
In cases of product and Dempster-Shafer theory, however, the T’s (0.56 and 0.73) of
the trusts are much bigger than their U values (0.02 and 0.03), compared with the
original distributions of the reputation. The resulting T value in Ψ5 is interpreted that
there is a 0.73 chance that the agent in p has the trustworthiness, while the resulting U
value indicates that there is only a 0.03 chance that the agent is negatively estimated.
As we mentioned above, thus, normalizing the original values of trustworthiness and
untrustworthiness, which is corresponding to the denominator in the above equation,
makes the opinions associated with conflict being away from the trust as a consensus.
To show how the aggregation rules could be adapted to various distributions of
reputation, we consider additional set of reputations. The possible outputs of trust
with two different set of reputations are displayed in the second and the third column
of Table 2, respectively.
Table 2. The possible outputs of trust with two different set of reputations.
ω1pp = {0.20, 0.80}, ω1pp = {0.30, 0.30},
Aggregation rules ω2 = {0.30,p0.70} ω2 = {0.50,p0.50}
Trust ω Trust ω
Minimum (Ψ1) {0.20, 0.70} {0.30, 0.30}
Maximum (Ψ2) {0.30, 0.80} {0.50, 0.50}
Average (Ψ3) {0.25, 0.75} {0.40, 0.40}
Product (Ψ4) {0.06, 0.56} {0.15, 0.15}
Dempster-Shafer theory (Ψ5) {0.10, 0.90} {0.21, 0.21}
The example of second column shows the case that the number of positive feedbacks
is much less than that of negative feedbacks, and the third column is an example that
the number of both feedbacks is identical. Note that the resulting distributions of
trustworthiness and untrustworthiness, as displayed in Table 2, mirror their distribu-
tions in the original set of reputations.
Since the available feedbacks from multiple agent-groups in social networks are
classified into positive, negative, and neutral ones, the positive and negative feed-
backs among them are adopted for the components of our trust model. However,
these two values contradicting each other are still not enough to represent the trust
itself as degrees of belief on agent’s truthfulness. From practical perspective, the trust
is required to be a precise value as a metric.
3.3 Expected Trust
We define expected trust as the center of gravity of the distribution of beliefs, i.e., the
degrees of trustworthiness and untrustworthiness for an agent. The expected trust ω̂
p
is given as
T (4)
ω̂ p =
T +U
taking into account both trustworthiness and untrustworthiness of an agent. The ex-
pected trust, thus, represents the average beliefs on agent’s truthfulness or coopera-
tiveness, and translates the agent’s trust into a specific value where 0 ≤ ωˆ ≤ 1 . In
p
the notion of expected trust, the higher the expected trust level for the agent, the more
the expectation that the agent will be truthful or cooperative in future interactions.
The calculation of expected trust using equation (4) gives social insight on the agent’s
trust.
Example 1 (cont’d). Given a set of reputations in the three agent-groups above, the
expected trusts are shown in Table 3.
Table 3. The expected trust values in three example sets of reputation.
ω1pp = {0.80, 0.10}, ω1pp = {0.20, 0.80}, ω1pp = {0.30, 0.30},
Aggregation ω2 = {0.70, 0.20} ω2 = {0.30, 0.70}p ω2 = {0.50, 0.50}
rules Expected trust ω̂
Minimum (Ψ1) 0.88 0.22 0.50
Maximum (Ψ2) 0.80 0.27 0.50
Average (Ψ3) 0.83 0.25 0.50
Product (Ψ4) 0.97 0.10 0.50
Dempster-Shafer 0.96 0.10 0.50
theory (Ψ5)
This example illustrates that the expected trust provides a metric for the agent’s
overall truthfulness, which consists of trustworthiness and untrustworthiness. The
simple aggregation rules, i.e., minimum, maximum, average, and product, give a
pretty representative trust value considering both trustworthiness and untrustworthi-
ness, even though it is not clear which one is good for a particular setting. This may
be the reason that these simple but surprisingly well applicable rules keep on being
popular in any contexts [9]. The product rule and Dempster-Shafer theory highly rate
the agent’s expected trust than the other simple rules. We attribute this sharp contrast
between trustworthiness (refer to 0.97 and 0.96 in Table 3) and untrustworthiness
(0.10 and 0.10, respectively, in Table 3) to their purely conjunctive operation with
completely ignoring the degrees of disagreement or conflict.
4 Applying Trust Model to Online Internet Transactions
We apply our trust model to online Internet transactions. Given the actual feedbacks
of agent-groups in online multi-agent settings, we can convert the feedbacks into the
agent’s reputation, denote its trust as an aggregation of reputations, and compute the
expected trust for a measurable belief on the agent’s truthfulness. In this section, we
pursue how the trust is involved in a rational decision-making of buyers and sellers.
Suppose that there are sellers and buyers in online Internet settings. Let R be a
contract price, s be the quantitative size of the contract, V(s) be the buyer’s benefit (or
value) function, which reflects his/her satisfaction acquired by purchasing a number
of commodities, and C(s) be the seller’s cost function, which indicates the cost to
produce the amount of the commodities. Given the expected trust of the buyer ω̂ ,
M
the expected utility of the buyer is given by 4
(5)
EU M ( s ) = V ( s ) − ωˆ M R.
Given the expected trust of the seller ω̂ , and also, the expected utility of the seller
N
is defined as
(6)
EU N ( s ) = ωˆ N R − C ( s ).
In equations (5) and (6), the expected trust is interpreted as the average beliefs on the
buyer’s and the seller’s truthfulness or cooperativeness, respectively. The Nash equi-
librium [2, 12] in online transactions, then, provides a solution concept when the
buyer and the seller have no incentives in case of choosing other alternatives. The
Nash bargaining solution is
(7)
arg max R (V ( s) − ωˆ M R)(ωˆ N R − C ( s ))
so that the buyer and the seller are beneficial to each other if they agree on their bar-
gaining behavior. Note that equation (7) has a unique Nash equilibrium, since an R
can be determined given expected trusts of the buyer and the seller, V(s), and C(s).
Example 2. To derive R given the Nash bargaining solution, as defined in (7), let us
take the first derivative of equation (7) as follows:
4 Our notation follows [2].
d
(V ( s ) − ωˆ R )(ωˆ R − C ( s )) = 0;
M N
dR
ωˆ V ( s ) + ωˆ C ( s )
N M
∴R = .
2ωˆ ωˆ
M N
Thus, the contract price R that they agree on can be determined in a Nash equilibrium.
Substituting the above into (5) and rearranging terms, we get
ωˆ N V ( s ) − ωˆ M C ( s )
EU M ( s ) = .
2ωˆ N
In similar way, the expected utility of the seller is
ωˆ N V ( s ) − ωˆ M C ( s )
EU N ( s ) = .
2ωˆ M
Suppose that the buyer’s benefit function V(s) is 24ln(2s) and the seller’s cost func-
tion C(s) is s2-2s+3 as usual. 5 When ωˆ = ωˆ = 0.8 , the quantitative size of the
M N
contract s can be determined by
d d
(ωˆ V ( s ) − ωˆ C ( s )) = (0.8 × 24 ln(2 s ) − 0.8 × ( s − 2 s + 3)) = 0.
N M 2
ds ds
That is, they both maximize their expected utilities and, once the buyer’s benefit
function and the seller’s cost function are decided, the quantitative size of the contract
is computed as the above. Thus, s=4. The expected utilities of the buyer and the seller
also can be calculated, and, in this case, those are 19.45. Consider now that the
seller’s expected trust is low, say, ωˆ = 0.2 . Then, s=2.31, and their expected utili-
N
ties are EU M ( s ) = 10.94 and EU N ( s ) = 2.73 . Calculated above, both the overall
quantitative size of contract and the expected utilities of the buyer and the seller are
larger, when the expected trust values of the agents are higher.
5 We assume that the buyer’s benefit does not necessarily increase in proportion to the quanti-
tative size of commodities while the seller’s cost proportionally increases to produce a cer-
tain amount of commodities.
5 Conclusion
The model of trust in social networks has been continuously studied for safe and
successful interactions. Our work contributes to a computational model of trust as an
aggregation of consensus associated with multiple agent-groups. We formulated repu-
tation based on available feedbacks resulting from social interactions, calculated trust
among a set of reputations using aggregation rules, and represented expected trust as
a metric for the agent’s truthfulness or cooperativeness. We have shown how our trust
model can be calculated in a detailed example. To show how the trust is involved in a
rational decision-making of interactive agents, our trust model has been applied to
online Internet transactions. We believe the trust model should be applicable to real
societies of multi-agent environments.
As part of our ongoing work, we are applying our trust model to online Internet
transactions. Given the actual feedbacks of customers in online multi-agent settings,
for example, e-Bay and Auction, we will convert the feedbacks into the agent’s repu-
tation, denote its trust as an aggregation of reputations, and pursue how trust affects a
rational decision-making of buyers and sellers. Toward this end, we will benchmark
the amount of interactions between the buyers and the sellers, when they have higher
trust values and/or they have lower trust values. The experiments that we are per-
forming will also measure the global profits in a set of agent-groups employed with
different trust values.
References
1. R. Axelrod, The Evolution of Cooperation, Basic Books, New York (1984)
2. S. Braynov and T. Sandholm, Contracting with Uncertain Level of Trust, Computational
Intelligence, Vol. 18, No. 4 (2002) 501 - 514
3. J. Coleman, Foundations of Social Theory, Harvard University Press, Cambridge, MA
(1990)
4. A. Daskalopulu, T. Dimitrakos, and T. Maibaum, Evidence-Based Electronic Contract
Performance Monitoring, INFORMS Journal of Group Decision and Negotiation, Vol. 11
(2002) 469-485
5. A.P. Dempster, A Generalization of Bayesian Inference, Journal of the Royal Statistical
Society, Series B, Vol. 30 (1968) 205-247
6. J. Golbeck, Generating Predictive Movie Recommendations from Trust in Social Networks,
Proceedings of the Fourth International Conference on Trust Management, Pisa, Italy
(2006)
7. A. Josang and S.J. Knapskog, A Metric for Trusted Systems, Proceedings of the 21st Na-
tional Information Systems Security Conference, Virginia, USA (1998)
8. M. Kinateder and K. Rothermel, Architecture and Algorithms for a Distributed Reputation
System, LNCS Vol. 2692, Springer-Verlag (2003) 1-16
9. L.I. Kuncheva, J.C. Bezdek, and R. Duin, Decision Templates for Multiple Classifier Fu-
sion: An Experimental Comparison, Pattern Recognition, Vol. 34 (2001) 299-314
10. S. Marsh, Formalizing Trust as a Computational Concept, Ph.D. thesis, University of Stir-
ling, UK (1994)
11. L. Mui, M. Mohtashemi, and A. Halberstadt, A Computational Model of Trust and Reputa-
tion, Proceedings of the 35th Hawaii International Conference on System Sciences (2002)
12. J. Nash, The Bargaining Problem, Econometrica, Vol. 28 (1950) pp 155-162
13. P. Resnick and R. Zeckhauser, Trust Among Strangers in Internet Transactions: Empirical
Analysis of eBay's Reputation System, The Economics of the Internet and E-Commerce,
Vol. 11, Advances in Applied Microeconomics, Elsevier (2002)
14. G. Shafer, Perspectives on the Theory and Practice of Belief Functions, International Jour-
nal of Approximate Reasoning, Vol. 3 (1990) 1-40
15. G. Shafer and J. Pearl, eds., Readings in Uncertain Reasoning, Chapter 3 Decision Making,
Chapter 7 Belief Functions, Morgan Kaufmann Publishers (1990)
16. L.A. Zadeh, Review of Books: A Mathematical Theory of Evidence, AI Magazine, Vol. 5,
No. 3 (1984) 81-83