Georgios Pitsilis
email: pitsilis@q2s.ntnu.no

Pern Hui Chia
email: chia@q2s.ntnu.no

Does Trust Matter for User Preferences? A study on Epinions ratings

Keywords: Trust, Epinions, Recommender system

Recommender systems have evolved during the last few years into useful online tools for assisting the daily e-commerce activities. The majority of recommender systems predict user preferences relating users with similar taste. Prior research has shown that trust networks improve the performance of recommender systems, predominantly using algorithms devised by individual researchers. In this work, omitting any specific trust inference algorithm, we investigate how useful it might be if explicit trust relationships (expressed by users for others) are used to select the best neighbours (or predictors), for the provision of accurate recommendations. We conducted our experiments using data from Epinions.com 1 , a popular recommender system. Our analysis indicates that trust information can be helpful to provide a slight performance gain in a few cases especially when it comes to the less active users.

Introduction

Reputation systems compute global scores about products (people, companies, etc) based on opinions that users hold about them and assist prospective users in deciding whether to buy these products. Different from reputation systems that provide global scores, recommender systems provide personalized (local) recommendations based on correlations of ratings (browsing history, search keywords or other actions) made by likeminded users. Recommendations are generated automatically to assist users to choose from multiple options available on the Internet. Amazon.com and Youtube.com, for example, correlate the users' browsing history to determine the similarity between users. In order to learn from similar users, recommender systems employ filtering techniques such as Collaborative filtering to identify influential users with similar behaviour and label them as "neighbours" or "predictors".

Although involving more predictors (users whose ratings are taken into account in predictions) may help in improving the prediction accuracy, the number of predictors should be kept low to avoid expensive computation. Herlocker et.al. reported that having too many predictors will conversely reduce the accuracy of predicted recommendation [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF]. Rather than trying to guess the magical number of predictors, we believe that much focus could be placed in determining (a small set of) the most suitable predictors.

In classic recommender systems the criteria used for selecting suitable neighbours regard only users' past behaviour and liking (ratings) towards products that are common with other users to compute a similarity value for each user-pair. There are then several strategies to pick the most suitable predictors. These include clustering, correlation thresholding and best-k-neighbours. Clustering organizes the whole user population into groups of similar tastes but in general it is done statically in such a way that predictions are always made using the same set of predictors (or neighbourhood). Correlation thresholding considers only neighbours that are correlated with a particular user over a certain threshold. Meanwhile, the best-kneighbours technique selects some k best (most similar) neighbours to be considered in the prediction algorithm. The best-k-neighbours technique is also widely known as the k-Nearest Neighbourhood (kNN) approach, and it has been found that kNN outperforms the correlation thresholding approach (in both accuracy and coverage) with reasonable k values [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF]. Various kNN-based algorithms have been proposed for selecting the best predictors [START_REF] Kwon | Improving Top-N Recommendation Techniques Using Rating Variance[END_REF] [START_REF] Kim | Using Attributes to Improve Prediction Quality in Collaborative Filtering[END_REF].

In real life, users consult opinions of people whom they trust for forming their own decisions. Such trust relationship is being collected by advanced recommender services. The network of explicitly formed trust relationships is known as web-oftrust [START_REF] Boyd | Social network sites: Definition, History, and Scholarship[END_REF]. A trust-based recommender system incorporates the web-of-trust into its recommendation algorithm, mimicking the way that people get good advices from trusted sources in real life. A trivial case is to consider only reviews and ratings from sources that have been explicitly indicated as 'trusted' by individual users. Explicittrust is hence binary. On the other hand, sophisticated systems propagate trust relationship across the user network in order to infer (non-binary) trust values. Several approaches have been proposed to compute implicit-trust values, including Advogato [START_REF] Levien | Advogato's trust metric[END_REF], Mole-trust [START_REF] Massa | Controversial Users demand Local Trust Metrics: an Experimental Study on Epinions.com Community[END_REF] and Subjective logic [START_REF] Jøsang | A Logic for Uncertain probabilities[END_REF]. Implicit-trust values are particularly helpful when explicit trust information is scarce. For example, if there is a consistent trend that user a could provide user b with good advices, even though user a has not explicitly indicated that she trusts user b, it is likely that user b's suggestion would be useful in the future (or considered with a higher weight) and should be implicitly trusted.

Our intuition is that explicit trust information can be exploited to improve the traditional recommender systems in the selection of the most suitable predictors needed in the collaborative filtering. In this work, we investigate whether it is beneficial in the form of improved prediction accuracy when (a small set of) the most suitable predictors are selected with and without explicit trust. If trust helps to select better predictors, combining the classical collaborative filtering with users' personal assessments (i.e. trust) towards the usefulness of others' recommendations might be of much benefit to improve prediction quality. To enhance comparison, we also present a trust-experience-selection strategy with the intuition that users will be more likely to take into account opinions from trusted users that are more experienced, in real life.

The research contribution and purpose of this work is two fold. First, we investigate the potential benefits of using trust in selecting better predictors with the objective to improve the collaborative filtering scheme in classical recommender system. Second, we investigate the possibility of using usage experience along with trust as a criterion to help selecting suitable predictors.

The rest of the paper is organized as follows. In section 2 we discuss the related work in the field of recommender systems, social networks and trust. Next in section 3, we elaborate on how explicit trust and usage experience could be incorporated to potentially improve the selection of suitable predictors. We describe our experimental setting in section 4 and present the evaluation results in section 5. Finally, in section 6 we discuss our findings before concluding.

Related Work

Research related to the Epinions dataset includes that of conducted by Massa et. al. [START_REF] Massa | Controversial Users demand Local Trust Metrics: an Experimental Study on Epinions.com Community[END_REF] that reports interesting findings on "controversial" users who are simultaneously trusted and distrusted by many. They argue that personalized trust metrics are needed given the fact that the controversial users take up to a fraction of 20%. The same authors in [START_REF] Massa | Trust-aware recommender systems[END_REF] address the problem of information overload by exploiting the trust information that users provide explicitly. Even though their concept of making use of the trust graph is quite similar with ours, in their work they used different mechanism/formulae for working out predictions for user items. In our approach we tested various strategies for deciding the best-k neighbours while keeping the similarity-based methodology.

Liu et.al. [START_REF] Liu | Predicting Trusts among Users of Online Communities: An epinions case study[END_REF] propose a classification approach for predicting the trust between users from reputation in the absence of first-hand knowledge. Their solution addresses the problem of sparse webs-of-trust by using pre-trained classifiers, but some minimum information, such as user attributes, is required to exist. There is also much research done concerning the topological properties of social networks. We mention that of Wilson et.al. [START_REF] Wilson | User interactions in Social Networks and their Implications[END_REF] as one of the most recent and complete piece of work.

As for approaches that cluster users into groups of similar tastes, there is a wealth of literature that essentially focused on overcoming the poor prediction quality (e.g. in [START_REF] Truong | Improving the Accuracy of Recommender System by Item Clustering[END_REF]). Geng et.al. [START_REF] Geng | A new Clustering Algorithm using Message Passing and its applications in Analyzing Microarray Data[END_REF] explores the idea of clustering users by imitating the way that people of common interests can be grouped together. Other clustering-based proposals include that by Truong et.al. [START_REF] Truong | Improving the Accuracy of Recommender System by Item Clustering[END_REF] which uses the common knowledge that exists about the rating behaviour of people for allocating them into clusters of interests. Kwon [START_REF] Kwon | Improving Top-N Recommendation Techniques Using Rating Variance[END_REF] proposes a technique for selecting the best neighbours as improvement to the k-nearest neighbour approach. As opposed to our approach he uses the variance of predictions in a user-specific metric that describes the deviation of the examined user. Other work related to finding best neighbours is that of Lathia et.al. [START_REF] Lathia | Trust-Based Collaborative Filtering[END_REF] in which a policy based on trustworthiness is proposed. Contrary to our approach they use implicit trust for finding the best k-trusted neighbours to forming groups of collaborative users. In their idea the trust for some user is derived from the knowledge about her particular ratings. The work in [START_REF] Melville | Content-Boosted Collaborative Filtering for Improved Recommendations[END_REF] introduced a hybrid Collaborative Filtering System which differs from the standard similarity-based approaches by using weighted similarities computed from the number of common experiences with the predictor.

Sparsity is also recognized as a problem that affects the quality of predictions, and in the past it has been investigated from two different directions. Latent factor analysis, known as Dimensionality Reduction, has shown very promising results [START_REF] Sarwar | Application of Dimensionality Reduction in Recommender Systems-a case study[END_REF]. However, the simplicity and intuitiveness of Neighbourhood-based methods have made themselves more applicable and suitable for social-networking-based models. Trust has also been the subject of investigation by many researchers in the past as a solution for alleviating issues concerning sparsity and security of recommender systems. O'Donovan and Smyth [START_REF] O'donovan | Trust No One: Evaluating Trust-based Filtering for Recommenders[END_REF] proposed to use implicit trust derived from the reliability of partners as another factor to influence predictions in conjunction with similarity.

To our knowledge, the concepts to use both users' usage experience and explicit trust for building dynamic clusters of suitable predictors have not been explored adequately so far. In the existing solutions no emphasis has been given on the phenomenon of social connectivity in online communities neither on how this could benefit the provision of electronic recommendation services.

Neighbourhood Selection Schemes

Conventional Similarity-based Neighbourhood (S)

Central to most recommender systems that employ collaborative filtering is the computation of similarity between users. Pearson's similarity is the best known formula for user-based recommender systems. It measures the proximity between two users and is computed along the rows (or columns) in the Users by Items matrix. Formula (1) computes the Pearson's similarity b a w , between users a and b using the set of common items between the two users. The outcome is in the range of Pearson's similarity is then used in conjunction with Resnick's formula to work out the predicted recommendation [START_REF] Melville | Content-Boosted Collaborative Filtering for Improved Recommendations[END_REF]. Formula (2) computes the predicted rating  i a p , of item i for user a using the set of existing ratings r j,i given to this item i by predictor j.

[-1,1].         k b k b k a k a k b k b a k a b a r r r r r r r r w 2 , 2 , , , , ) ( ) ( ) )( ( (1)
       j j a j j i j j a a i a w r r w r p , , , , )} ( { (2)
Resnick's formula (as it is highly sensitive to the number of predictors) does not provide accurate prediction in sparse datasets [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF]. The selection of the most suitable predictors is hence of major significance when it comes to the performance of collaborative filtering [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF]. Previous research [START_REF] Shardanand | Social Information Filtering: Algorithms for automating "word of mouth[END_REF] highlighted the importance of selecting the most suitable predictors (for achieving good prediction accuracy) and suggested that only those who are most similar in terms of product ratings should be chosen. We refer this selection scheme as Similarity-based neighbourhood (S), as shown in Figure 1a.

We provide a formal description of the Similarity-based neighbourhood. Let U be the set of all users and I is the set of all items that have been rated in the system. Let   i r a denote that user a has given a rating for an item i (i.e. not null), the set of ratings I I a  given by a user a can then be written as:

        i r I i I a a : (3)
We require that only those who have similar rating behaviour with some user a and have experienced the item i (that user a is interested in) be considered. The set of these similar neighbours can be expressed as:

           ) ( | | : , i r q I I a b U b S b a b i a (4)
with q denoting the minimum number of common items that have been rated by both user a and her neighbour. Setting such as minimum count is necessary as correlation coefficient (Pearson's similarity value) would not be computable (or not meaningful) unless both users have rated at least some common set of items. From equation ( 4), one can realize that the top-k neighbourhood is not static, depending also on the item of interest.

In addition, to require that Pearson's similarity to be computable, we introduce two neighbourhood formation schemes with additional criteria based on explicit trust and rating experience. We elaborate on these schemes in subsections 3.2 and 3.3.

Trust-based Neighbourhood (T)

In our first extension to the neighbourhood selection scheme, we consider only neighbours who have been explicitly indicated as trusted by a user, on top of the requirement that Pearson's similarity value is computable. Note that we only consider binary explicit trust; we do not infer or compute implicit trust values between users. Let 1 ) , (  b a t denotes the existence of an explicit directional trust relationship from user a to user b, the set of neighbours fulfilling the criterion of being trusted and have also rated item i (that user a is interested in) can be expressed as:

             ) ( 1 ) , ( | | : , i r b a t q I I a b U b T b a b i a (5)
These neighbours are then ordered by their respective trustworthiness index, which is simply the count of in-degree trust links. Finally, the top-k neighbours (predictors) are selected to predict recommendations for this user using the Resnick's formula. We refer this selection scheme as Trust-based neighbourhood (T), as shown in Figure 1b.

Trust-Experience-based Neighbourhood (T-E)

We further explore if user experience could be taken into account to help selecting better predictors. The intuition is that users are more likely to seek advice from people who are more (or equally) experienced than those who are less experienced. For that reason our objective is to examine whether users who have given more product ratings should be considered better candidates. Considering this as an opinion flow, we impose that the direction is from the more experienced to the less experienced ones.

The experience level of a user (can also be thought as the amount of knowledge) is quantified according to number of recommendations that have been submitted by the user. We order users according to rating count such that:

U b a   , if | | | | b a I I  then b a e e 
where a e denotes the experience level of user a and | | a I is the number of items that have been rated by user a. In this work, we categorize all users U into five experience levels, each consisting of | | 5 1 U users. In this way, the set of neighbours that have rated some item i (that user a is interested in) and have a higher (or equal) experience level than user a, can be expressed as:

          ) ( : , i r e e a b U b E b a b i a (6)
Combining the computable similarity, trust and experience criteria in (4), ( 5) and ( 6), the set of neighbours that can potentially become the top-k predictors can be expressed as:

               ) ( 1 ) , ( | | : , i r e e b a t q I I a b U b TE b a b a b i a (7)
We refer to this selection scheme as Trust-Experience-based neighbourhood (T-E), as depicted in Figure 1c. When selecting the top-k neighbours, the trustworthiness index has a higher priority over the experience.

Experimental Setting

To evaluate our central question of whether trust helps to select better predictors we performed a series of simulations and compared the performance of the neighbourhood selection schemes as described in section 3.

Data

We used data from a popular recommender system, Epinions.com for the reason that it contains both product ratings and trust information we needed for our experiments. Epinions.com allows member users to write reviews about products consisting of a text and a quantitative rating from 1 to 5 stars. Epinions.com allows also users to build their web-of-trust by indicating other users whom they find have given consistently valuable reviews as trusted. In the current form of the system assistance is limited to the provision of textual and rating information from trusted users about the products of interest; input from trusted sources have to be digested by users manually.

The dataset was collected by Paolo Massa [START_REF]A cooperative environment for the scientific research of trust metrics on social networks[END_REF] by crawling the Epinions.com website during Nov-Dec 2003. In total, there are over 664K ratings given by 49K users on 139K products. Also included are 487K outward trust statements from users. Shown in Figure 2, both the distribution of rates and trust relationship in Epinions.com seem to follow power-law distribution, which is a feature of most social networks [START_REF] Wilson | User interactions in Social Networks and their Implications[END_REF]. The figures are plotted in log scale showing the number of outward trust links per user (Fig. 2a) and the number of ratings given by individual users (Fig. 2b). The number of outward trust links and products rating count per user decrease sharply going from the very active users to the non-actives ones. This further suggests that the ratings on common products and the trust towards same users are sparsely distributed. As such, we used only a subset of Paolo Massa's dataset consisting of 1500 active users selected on the basis of number of ratings given by each user (no matter how many inward or outward trust links they have). This was also done to ensure that the Pearson's similarity value between users is computable with an adequate number of commonly rated products. There are 664K item ratings in total.

The 1500 users were then divided into three communities referred to as "most active", "medium active" and "least active" of 500 users each (again based on the number of ratings that have been given by each user). Table 1 shows the average outward trust links and average number of ratings of the different communities.

Evaluation Metrics

We considered both Predictive and Classification accuracy as being equally important to be measured. The former is demonstrative of the efficiency of the system in making accurate predictions for users. The latter as suggested by many researchers in Information Retrieval [START_REF] Mcnee | Accurate is not always good. How Accuracy Metrics have hurt. Recommender Systems[END_REF][10] is useful for measuring the frequency at which the system decides correctly or incorrectly about if an item is potentially liking for a particular user. Its usefulness in recommender systems is found in the creation of lists of products that are of high interest to users.

Predictive accuracy means the ability of the algorithm in producing accurate predictions for individual products. To demonstrate this we used the metrics Mean Average Error (MAE) and Root Mean Square Error (RMSE). The latter is especially useful for identifying undesirably large errors. MAE and RMSE are both computed by comparing the real ratings (given by users) and the predicted ones. In our experiment the predicted values were rounded to the closest integer. We also applied correction on any predicted values that were out of range. Specifically, predicted values lower than 1 or higher than 5 were corrected to 1 and 5 respectively.

For evaluating the Classification accuracy we used the rating of 4 as the threshold for indicating a product that is of user's interest, meaning that a predicted value of 4 or 5 would be considered successful. Recall (R) is a metric to express the relative success in retrieving items of interest (either highly rated or lowly rated) in relation to the number of all items claimed to be of interest. Precision (P) is the relative success in retrieving items that are of user's interest. Both metrics can then be combined to express the effectiveness of retrieval with respect to the cost of retrieval to give the F-Score. F-Score is also known as Harmonic Mean [START_REF] Herlocker | Evaluating Collaborative Filtering Recommender Systems[END_REF] and it describes the trade-off between true positive (TP) and false positive (FP). Precision (P) and Recall (R) and F-score can be computed as follows:

R P PR F FN TP TP R FP TP TP P       2
We used Precision (P) to measure the improvement in the relative success that the T and T-E schemes can possibly provide for identifying products that are of user's interest. We called a hit (or True Positive) for the case where some product that is of user's interest (i.e. has been rated as 4 or 5 by the user) and at the same time, using the algorithm, a high rating (4 or 5) has been predicted for it. We did not measure Recall (R) as is often impractical to do so in a recommender system [START_REF] Herlocker | Evaluating Collaborative Filtering Recommender Systems[END_REF]. The true positive (TP), false positive (FP) and false negative (FN) instances for our analysis are as defined in the confusion matrix in Table 2. Since the application of filters (selection criteria) has implications to the number of items that can be actually predicted it is necessary that the level of this is also captured as well for every testing scenario. Coverage is a suitable metric for capturing this implication. It is defined as the ratio of recommendations for products that are of interest to the querying user and which the selected top-k neighbours can recommend, divided by the total number of items (that the querying user is interested in). The coverage of some particular user a can be computed using formula [START_REF] Kim | Using Attributes to Improve Prediction Quality in Collaborative Filtering[END_REF] where K denotes the set of top-k neighbours of user a, I being the set of all items in the system and a I is the set of items that have been rated by user a .

           K b b a a a I I I C | | 1 (8)

Test Scenarios

The Similarity-based (S), Trust-based (T) and Trust-Experience-based (T-E) neighbourhood selection schemes formed the three main testing scenarios in our experiments. For each of the neighbourhood schemes, we studied the impact of the number of predictors on the performance by repeating kNN computation for different k values ranging from 3 to 13. When comparing the performance of neighbourhood schemes (e.g. T against S), we considered only predicted recommendations where the exact number of predictors (k) could be found. As the ratings of common products and trust relationship are sparsely distributed, our experiments involved only a subset of 1500 active users from Paolo Massa's dataset. The 1500 users were divided into three communities referred to as "most active", "medium active" and "least active" (each with 500 users). We ran our experiments starting with the "most active" community.

When running a test scenario on a community of particular activity-level (i.e. most active, medium active and least active), we used the five-fold cross-validation method to further divide the community (500 users) into five fifths from where one fifth would be regarded as test set while the other four were used as training sets. This was repeated five times with a different fifth being used as the test set each time and the results were finally averaged.

Results -Discussion

We report the most interesting results from our experiments. First, in Table 3, we present the effects of trust criteria (both T and T-E schemes) on prediction accuracy for the "most-active" community with k denoting the number of predictors used in each experiment. Due to the use of sparse dataset not all predictions can be made with the T and T-E neighbourhood schemes. When comparing the predictive accuracy (MAE, RMSE), we considered only user items that could be both predicted using the S neighbourhood scheme and the alternative scheme (T or T-E), in a pairwise manner. Thus, Table 3 andTable 4 show, for each of the experiment (using T or T-E scheme), the corresponding MAE and RMSE values measured using the S neighbourhood. From the results it can be seen that trust does not help in choosing better neighbours to improve prediction accuracy as both the MAE and RMSE are lower for similarity-based selection scheme (compared to T and T-E schemes) for all k number of predictors. This suggests using explicit trust for selecting better predictors does not help to improve predictive accuracy for the "most active" community. Experienced users may be characterized by having stronger personal opinions; they may not rely on or be influenced easily by even those whom they trust.

Using the MovieLens dataset, Herlocker et.al. [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF] show that an increasing neighbourhood size (using the S scheme) will improve the predictive accuracy until a certain threshold (about 15) where performance starts to deteriorate with more neighbours. Our results show a similar trend using the Epinions dataset; predictive accuracy improves following an increasing number of predictors, for all neighbourhood schemes (S, T, and T-E). However, due to the sparse distribution of commonly rated products and trust links with the Epinions dataset, we did not investigate further on larger neighbourhood; we stopped with 13 predictors.

As for classification accuracy, the performance of Precision (P) for the "most active" community improves in the T-E scheme, when a sufficiently large number of trusted and more experienced predictors are employed. This is shown in Figure 3 and can be interpreted as: user intuition, in choosing neighbours (by indicating explicit trust, when assisted by the system to filter out the less experienced ones), can work better than a system-determined similarity-based neighbourhood. Another observation is the increasing trend of P in both the T and T-E schemes, which starts low but catches up with (or overtakes) the S scheme with an increasing number of predictors . This suggests that user intuitions on trusting others to give good recommendations may not be individually reliable but can be helpful when aggregated.

Finally we observed serious implications on coverage value for all test cases when involving large numbers of predictors. Trust-based filters (T and T-E) affect the coverage even worse. The results are shown in Table 3. So far, with the only exception of Precision, the use of explicit trust to select predictors has not been found very helpful. Coverage is strongly affected due to the limited trust information. Deriving trust from existing relationships (e.g. inferred from propagated trust) might be helpful for, at least, overcoming the coverage problem.

We should note that in other research works the use of propagative trust has been found quite successful for improving the predictive accuracy in user communities (e.g. in [START_REF] Massa | Trust-aware recommender systems[END_REF]). However, the distinctive difference here is that we examine the suitability of using explicit trust to select better predictors. Trying propagation trust frameworks (e.g. in [START_REF] Jøsang | A Logic for Uncertain probabilities[END_REF]) to infer implicit trust values is outside the scope of this paper; we have deferred this to future investigation.

For the reason that trust is known to improve the predictive accuracy for cold-start users [START_REF] Massa | Controversial Users demand Local Trust Metrics: an Experimental Study on Epinions.com Community[END_REF] we continued our experiments with the "medium active" and "least active" communities. Cold-start users are those who have not provided a sufficiently large number of ratings; as a consequence they often receive poor recommendations. The MAE and RMSE values for these communities are shown in Table 4a and4b. Diff denotes the improvement of T or T-E scheme over the baseline S scheme. We show only results for some small k predictors as the trust links within the "medium active" and "least active" communities are scarce, causing it infeasible to investigate further.

In Table 4b, it can be seen that with k=3,4 predictors, contrary to the "most active" community, predictive accuracy is better with both the T and T-E criteria compared to the baseline S scheme. This suggests that in the "least active" community, as users are less experienced, opinions from explicitly trusted sources can be very useful. The average MAE Diff values (i.e. average improvement over the baseline S scheme) for the "most active" community are -2.22 and -2.72, for T and T-E schemes respectively. The corresponding value pairs for the "medium active" community and "least active" community are (-1.92, -1.72) and (4.61, 4.54) respectively. These average Diff values follow an increasing trend going from "most active" to "medium active" and to the "least active" communities. In other words, using trust to select better predictors can be more helpful to the less experienced users than the more experienced ones. Similar result, but more generalized as far as the number of predictors k, has also been found by Massa et.al. in [21].

We could not read much into the trend of predictive accuracy for the "medium active" and "least active" communities as the number of predictors available using the T and T-E schemes is very limited.

Table 5 presents the classification accuracy for the "medium active" community. Precision performs better in the T and T-E schemes for the "medium active" community even with small neighbourhood size. This conforms to the result on better predictive accuracy (as shown in Table 4a) as trust information is helpful for less experienced users. However, the combined trust-experience (T-E) criterion does not help as much as than the trust (T) criterion alone, different from the case with the "most active" community. On average, the Precision value has an improvement of 2.6% for T and just over 0.22% for T-E, compared to S. In short, trust is more helpful for the less active users. Nevertheless that requires that users have provided adequate trust inferences for people they can rely on, which is not always the case. When new users have little incentive or have not indicated their trusted counterparts, a recommender system could consider inferring the implicit trust values based on product ratings.

Further Analysis -Discussion

We further investigated the performance based on individual ratings. As we have found that trust is more useful for less active users, we excluded the "most active" community from the analysis. The accuracy gain against the Similarity-based neighbourhood selection (S) for the "medium active" community is shown in Figure 4a. As can be seen, the application of trust-based criteria has helped to improve the predictive accuracy for items that users have given a real rating of 3 or 4. Note that also the combination of trust and experience (T-E) gives, for both cases when users have rated with 3 or 4, better predictive accuracy over using trust criterion alone. We further investigated whether the better predictive accuracy in rating 3 and 4 is related to rating distribution itself. Figure 4b showed that the (uneven) rating distribution is characterized with an increasing frequency going from rating 1 to 5. However, unlike those with a rating of 3 or 4, trust criteria do not help for items that have been rated with 5. This allows us to believe that there are other factors in effect (not due to rating distribution).

An attempt to explain the observation is that it is more likely that (Epinions) users would believe in non-extreme ratings (compared to ratings of 1 and 5) and therefore indicate their trust on these reviewers. When there are more non-extreme reviewers being trusted, it is likely that the predictive accuracy for non-extreme ratings will work out better. It would be interesting to further explore this matter from the perspectives of behavioral and cognitive sciences in the future.

We have performed a series of experiments in the context of recommender systems with the purpose to investigate our central question of whether explicit trust information can be useful in predicting user preferences. We presented two neighbourhood selection schemes involving trust criteria (Trust-based and Trust-Experience-based schemes) and compared their performances relative to the conventional Similarity-based kNN approach.

Our results show that trust criteria can help to improve the performance of recommender systems in a few cases. Specifically, trust information helps to improve the Precision in our classification test to provide good recommendations on items that are of users' interest.

Trust criteria are shown to be more helpful to the less experienced users judging from the increasing trend of better predictive accuracy (compared to the similaritybased scheme) going from the "most active" to the "least active" communities. Although trust-based schemes do not seem to help for active users in this work, we believe there might be other prediction algorithms where trust information can contribute. An interesting future work would be to explore if 'distrust' can be helpful for these active users.

Meanwhile, other than the Precision value for the "most active" community, the combined trust and experience criteria does not perform better than trust criterion alone. Although it is intuitive to filter out neighbours that are less experienced, strict selection criteria proves not to be very helpful in the Epinions dataset, where trust links and commonly rated products are scarce.

Using only explicit trust (without inference of implicit trust values) as what we have done for the purpose of our experimental setup incurs a heavy loss in terms of coverage. The performance is also restricted to the lack of trust information especially when it comes to the less active users. For these reasons, we render our support to the ongoing research in the computation of implicit trust values and building more sophisticated trust-aware recommender systems. There are also much to learn from other related disciplines including psychology and behavioural science.

a r and b r are the

  average of all ratings by user a and b while r a,k and r b,k. are the ratings given by users a and b respectively for item k.

Fig. 1 .

 1 Fig. 1. Neighbourhood selection schemes

Fig. 2a .

 2a Fig. 2a. Outward trust links vs. trustors. There are 487K outward trust links in total.

Fig. 2b .

 2b Fig. 2b. Individual rating count vs. raters.There are 664K item ratings in total.

Fig. 3 .

 3 Fig. 3. Classification accuracy (Precision) for the "most active" community with different neighbourhood selection schemes.

Fig. 4a .

 4a Fig. 4a. Improvement in prediction accuracyfor individual ratings.

Fig. 4b .

 4b Fig. 4b. The Ratings distributionfor different communities.

Table 1 .

 1 Trust links and average rating count of different communities

	Community	Average outward	Average number
		trust links	of ratings
	Most active	40.33	260.91
	Medium active	9.02	114.09
	Least active	4.32	83.02

Table 2 .

 2 The confusion matrix for classification test

		Predicted Value ≥ 4 Predicted Value < 4
	Actual Rating ≥ 4	TP	FN
	Actual Rating < 4	FP	TN

Table 3 .

 3 Predictive accuracy and Coverage for the "most active" community

		MAE (%)			RMSE				Coverage (%)
	k	S	T	S	T-E	S	T	S	T-E S	T	T-E
	3	12.40	14.68	12.28	14.84	0.91	1.05	0.90	1.06	37.58	8.07	5.94
	4	12.01	14.29	11.86	14.56	0.88	1.02	0.87	1.03	32.22	5.02	3.42
	5	12.11	14.19	11.78	14.67	0.88	0.99	0.86	1.03	28.20	3.28	2.00
	6	12.04	13.93	11.61	14.32	0.87	0.98	0.86	1.01	25.04	2.20	1.22
	7	12.22	13.97	11.58	14.14	0.88	0.98	0.86	1.00	22.57	1.53	0.78
	8	11.93	13.90	11.81	14.29	0.85	0.97	0.87	1.02	20.36	1.11	0.49
	9	11.79	13.75	11.44	14.14	0.84	0.96	0.87	1.03	18.65	0.82	0.35
	10 11.55	13.82	10.30	13.33	0.84	0.97	0.82	0.97	17.10	0.59	0.23
	11 11.75	13.89	10.70	12.30	0.85	0.97	0.81	0.94	15.76	0.44	0.16
	12 11.82	13.95	10.29	12.90	0.86	0.98	0.79	0.99	14.61	0.33	0.10
	13 11.50	13.65	10.89	12.27	0.84	0.96	0.81	0.93	13.58	0.25	0.07

Table 4a .

 4a Predictive accuracy for the "medium active" community.

		MAE (%)					RMSE
	k	S	T	Diff	S	T-E	Diff	S	T	Diff	S	T-E Diff
	3	12.26	14.54	-2.29	13.44	15.87	-2.43	0.94	1.09	-0.15	1.00	1.17	-0.17
	4	13.10	14.71	-1.61	15.34	15.34	0.00	0.97	1.07	-0.10	1.05	1.12	-0.07
	5	13.72	15.58	-1.86	15.68	18.38	-2.70	0.96	1.08	-0.12	1.05	1.29	-0.24
	avg			-1.92			-1.72			-0.12			-0.16

Table 4b .

 4b Predictive accuracy for the "least active" community.

		MAE (%)					RMSE
	k	S	T	Diff S	T-E	Diff	S	T	Diff S	T-E Diff
	3	13.44	12.79	0.66	17.27	12.72	4.54	1.00	0.97	0.03	1.11	0.90	0.20
	4	16.92	07.69	9.23	-	-	-	1.14	0.62	0.52	1.00	1.00	0.00
	avg			4.61			4.54			0.19			0.10
						(-denotes absence of data due to scarcity of trust links)

Table 5 .

 5 Classification accuracy for the "medium active" community.

		Precision		F-score
	k	S	T	T-E	S	T	T-E
	3	0.880	0.901 0.867	0.863 0.864 0.835
	4	0.884	0.919 0.894	0.864 0.850 0.849
	5	0.887	0.898 0.895	0.867 0.822 0.756
	avg	0.883	0.906 0.885	0.865 0.845 0.813

† The first author carried out this work during the tenure of an ERCIM "Alain Bensoussan" Fellowship program. of Excellence, appointed by The Research Council of Norway, is funded by the Research Council, Norwegian University of Science and Technology (NTNU) and UNINETT. http://www.q2s.ntnu.no


Mark Hoogendoorn

S Waqar Jaffry
email: swjaffry@few.vu.nl

Jan Treur
email: treur@few.vu.nl

Incorporating Interdependency of Trust Values in Existing Trust Models for Trust Dynamics

Keywords: Trust modeling, interdependence, trust dynamics

Many models of trust consider the trust an agent has in another agent (the trustee) as the result of experiences with that specific agent in combination with certain personality attributes. For the case of multiple trustees, there might however be dependencies between the trust levels in different trustees. In this paper, two alternatives are described to model such dependencies: (1) development of a new trust model which incorporates dependencies explicitly, and (2) an extension of existing trust models that is able to express these interdependencies using a translation mechanism from objective experiences to subjective ones. For the latter, placing the interdependencies in the experiences enables the reuse of existing trust models that typically are based upon certain experiences over time as input. Simulation runs are performed using the two approaches, showing that both are able to generate realistic patterns of interdependent trust values.

Introduction

Within multi-agent systems, the concept of trust is often a key element in the relationship between agents. For example, an agent's trust in other agents might influence the selection process for task delegation. As a result, a variety of models related to trust have been proposed, see e.g. [START_REF] Falcone | Trust dynamics: How trust is influenced by direct experiences and by trust itself[END_REF], [START_REF] Hoogendoorn | Modeling Dynamics of Relative Trust of Competitive Information Agents[END_REF], [START_REF] Jonker | Formal Analysis of Models for the Dynamics of Trust based on Experiences[END_REF]. In most of these trust models, the trust an agent has in another agent is seen as the result of experiences the agent has with that other agent, and certain personality attributes (see e.g. [START_REF] Hoogendoorn | Modeling Dynamics of Relative Trust of Competitive Information Agents[END_REF], [START_REF] Jonker | Formal Analysis of Models for the Dynamics of Trust based on Experiences[END_REF]), and is independent of trust in other agents. More complex trust models also address a more advanced interpretation of the experiences, for example using a cognitive attribution process (see e.g. [START_REF] Falcone | Trust dynamics: How trust is influenced by direct experiences and by trust itself[END_REF]).

Merely considering experiences the agent has with a single other agent is however not always sufficient nor realistic. Sometimes experiences with an agent or the trust value in an agent can influence the trust in another agent. Imagine the following scenario: somebody wants to buy a new television. He currently has experience with two websites that sell televisions (referred to as w 1 and w 2 ). Given these experiences, he has a high trust in w 1 and a low trust in w 2 . As a result, he decides to buy the television at w 1 . Unfortunately, he gets a negative experience as the television is delivered with a broken screen and they do not accept the liability. Of course, this negative experience brings down the trust the person has in w 1 , however it might also result in an update of the trust in w 2 . Essentially, there are three options for this dependency: (1) a positive trust dependency, whereby negative experiences with one trustee have a negative influence upon the trust level of another trustee as well, and a negative experience has a negative influence upon the trust level of other trustee; (2) a negative trust dependency, whereby a negative experience with one trustee has a positive influence upon the trust of another trustee and a positive experience a negative influence, and (3) no trust dependency, meaning that there is no influence because the agent does not perceive a relationship. For the example, a negative trust dependency between w 1 and w 2 could be the case if the human perceives them as substitutable competitors (given the experience with w 1 , w 2 was actually not that bad) and a positive trust dependency in case the human sees the trustees as representatives from the same group (all Internet stores cannot be trusted).

In order to address these dependencies, a possibility is to incorporate such relationships in the trust model explicitly. This approach is for instance taken in [START_REF] Hoogendoorn | Modeling Dynamics of Relative Trust of Competitive Information Agents[END_REF], and has been refined in this paper. A disadvantage of such an approach is however that this does not allow the reuse of the currently existing trust models, each having their own specific pros and cons. Another option which is therefore investigated in this paper is to model a process which transforms the objective experiences into subjective experiences for each of the agents, thereby considering the dependencies as expressed before. This does allow for the reuse of existing trust models. Hereby, first a model to translate objective into subjective experiences is created with a number of parameters that can be set to tune the precise relationship between the experiences with each of the trustees. Simulation runs have been performed using both approaches to investigate whether the models are able to generate the desired behavior.

This paper is organized as follows. First, a trust model which incorporates interdependency directly is presented in Section 2, followed by the model to translate objective into subjective experiences and feed this into an existing trust model in Section 3. Section 4 presents compatible existing trust models and simulations results using all variants are presented in Section 5. Section 6 presents related work, and finally, Section 7 concludes the paper and gives directions for future work.

Relative Trust Model

This section describes a dedicated trust model of human trust on interdependent trustees incorporating the interdependence in the trust model itself. Note that this model has been inspired on [START_REF] Hoogendoorn | Modeling Dynamics of Relative Trust of Competitive Information Agents[END_REF] but has been slightly simplified to obtain higher transparency. In this model trust values have some degree of interdependency (competition, neutral, cooperation) where the human trust on a trustee depends on the relative trust in the trustee in comparison to the trust on other trustees. This model includes human personality characteristics like trust decay, flexibility and the degree of interdependency among trustees. Figure 1 shows the dynamic relationships in the model. Here, the trust value of one trustee is directly dependent on the trust values on other trustees. In the model described in Figure 1 it is assumed that trustees {S 1 , S 2 , . . . S n } provide experiences (E i (t)) to human at each time step continuously, these experiences have value from the continuous interval [-1, 1]. Here, -1 indicates the most negative experience whereas 1 is the most positive. The human updates the trust value on a trustee by keeping trust values on other trustees under consideration along with the interdependency relation of the trustees ( η ). Furthermore, human personality attributes like trust flexibility, expressing how much an experience counts (β) and autonomous trust decay (γ), indicating how fast trust goes back to a neutral value when there are no new experiences also play a role in this process. On receiving an experience E i (t) from a trustee S i at time point t, the human trust on S i at the next time point (t+1) is the sum of the human trust on S i (T i (t)) and the experience E i (t) minus the autonomous decay in trust, this is expressed as follows

) ( * ) ( * ) ( * ) 1 ( ) 1 ( t T t E t T t T i i i i         In differential form   ) ( * ) ( ) ( * t T t T t E dt dT i i i i     
To introduce the notion of trustees interdependence in this model, the relative trust of the human is defined. The relative trust of the human on S i at time point t (τ i (t)) is the difference between the human's projected trust on S i (T ' i (t)) and the average of the human's projected trust on all trustees times the degree of trustees interdependency η. The human projected trust on S i at time point t is the human trust on S i projected from the range [-1, 1] to [0, 1] as follows:

  2 1 ) ( ) ( '   t T t T i i
The human's relative trust on trustee S i at time point t can be calculated as follows

      n j j i i n T t T t 1 ' ' ) ( * ) (   T1 T2 T3 E1 E2

E2 γ=autonomous decay β=trust flexibility η=trust dependency

Where η is the degree of trustees interdependency in the range [-1, 1]. A negative value of η denotes cooperation while a positive value represents competition among the trustees and n is the number of trustees. The human relative trust is designed to fulfill the requirements for different interdependencies among trustees as shown in Table 1.

Table 1. Value of Relative Trust with different interdependencies

This relative trust is introduced as a bias in the above trust equation with experience and trust values as follows  

) ( * ) ( ) ( ) ( * t T t t T t E dt dT i i i i i       

Subjective Experience Based Trust Model

This section describes a model of human trust on interdependent trust values using experience transformation, thereby allowing for the reuse of existing trust models. In this model the trust values for different trustees have some degree of interdependency among themselves (competition, neutral, cooperation), similar to the model presented in Section 2. In this case, the human trust on a trustee depends on the relative experiences with the trustee in comparison to the experiences it has obtained from the other trustees. This model includes human personality characteristics like trust decay, flexibility, trust bias on experience, and degree of interdependency among trustees. Figure 2 shows the dynamic relationships in the model used.

The model expressed in Figure 2 is composed of two models: one for transforming an objective experience with a trustee into a subjective experience (on the left), and another model for updating the human trust value based on this subjective experience (on the right). In this case, it is assumed that the trustee continuously provides the human with objective experiences (E i (t)) which are transformed into subjective experiences (E ' i (t)) also on the interval [-1, 1]. This transformation depends on the human trust bias on experience (α) and the degree of interdependency among trustees (η). Thereafter this experience is passed on to the trust model (which can in principle be any compatible existing trust model). The computational models for Figure 2 are described in the following sections.

Transforming Objective into Subjective Experience Using Trust Interdependency

This section explains the design of the mathematical model for transforming an objective experience provided by the trustee into a subjective experience using trust interdependency. The human's subjective experience at any time point t is based on a combination of two parts: the trust biased part, and the trustee's interdependency part.

For the latter part an important indicator is the human's relative experience of trustee S i (E i (t)) at time point t (denoted by τ i (t)): the difference of the human's experience of S i to the average human's experience from all trustees at time point t times the degree of trustees interdependency η. This is calculated as follows:

      n j j i i n t E t E t 1 ' ' ) ( ) ( * ) (  
Here it should be noted that E ' i (t) is the objective experience from trustee S i at time point t projected from the interval [-1, 1] onto the interval [0, 1]. The trust interdependency parameter (η) can take values from the continuous interval [-1, 1], where negative and positive values of η denote cooperation and competition respectively similar to the model presented in Section 2. The human's relative experience is designed to fulfill the requirements as expressed in Table 2 for different interdependencies among trustees. To calculate the experience when taking the interdependency into account, the relative experience at time point t is added to the objective experience E i (t) from trustee S i at time point t:

) ( ) ( t t E i i  
In addition, a trust bias is included when transforming the objective experience into a subjective experience at time point t. Hereby the factor α (trust bias on experiences) is used to take α percent of the value of the trust a human has in a trustee i at time point t (T i (t)) and (1 -α) percent of the trustees experience in combination with the interdependency relation:

    ) ( ) ( * 1 ) ( * t t E t T V i i i i       
For further smoothing of this transformation (following approaches often found in neurological modeling), a threshold function th(β 1 , β 2 , V i ) is used with threshold β 1 and steepness β 2 , defined as follows:

      1 2 1 1 ) , , ( 2 1 
       i V i e V th
As the value of this threshold function resides on the interval [0, 1], this value is projected onto the interval [-1,1] according to the following formula:

1 ) , , ( * 2 ) ( 2 1   i si V th t E  

A Sample Trust Model

In order to illustrate how this experience can be used in a trust model, a very basic trust model is explained here. This model is an extension of a model present in the literature [START_REF] Jonker | Formal Analysis of Models for the Dynamics of Trust based on Experiences[END_REF], which accumulates experiences over time and updates trust accordingly.

Other trust models that are also suitable and have been found in existing literature are expressed in Section 4. In the trust model presented below, the trust is based on experiences in combination with two personality characteristics trust flexibility β and autonomous trust decay γ (defined similarly as in Section 2). In this model, it is assumed that the human trust on a trustee S i at time point t is T i (t) (a value from the interval [-1,1]). On receiving a subjective experience E si (t) from trustee S i trust of human on the trustee at time point t + ∆t adapts as follows:

  t t T t E t T t t T i si t i       * ) ( * ) ( * ) ( ) (   in differential form:   ) ( * ) ( * t T t E dt dT i si i    
Here it could be noted that trust would be in equilibrium if

   ) ( ) ( t E t T si t 4
Experience-Based Trust Models from Literature

This section describes two other experience based models taken from literature, and it will be shown that they also can be combined with the subjective experience model as proposed in Section 3. In [START_REF] Jonker | A temporal-interactivist perspective on the dynamics of mental states[END_REF] a simple trust model is proposed which accumulates experiences over time without temporal discounting of experiences. The model is defined by the following equation:

  t t T t E dt dT i i i ) ( ) ( *   
In the equation, β is the trust flexibility (i.e., how much an experience counts) while E i (t) is the experience with trustee i (in this case, the subjective experience if it is integrated with the proposed model). Similarly, another trust model described in [START_REF] Jonker | A temporal-interactivist perspective on the dynamics of mental states[END_REF] also accommodates experiences from the environment (but this time in discounted form), and the trust values are then updated as follows (with the same parameters):

      1 * ) ( ) ( * * *    t t i i i e e t T t E dt dT  



Here it can be noted that the exponential part in this model supports temporal discounting of experiences over time. Other, more complex trust models that are based upon exist as well, see Section 6 for more details.

Simulation Results

The models described in Section 2, 3 and 4 have been used to conduct a number of simulation experiments to see what patterns emerge using the different models, and how the different models compare. Here, first the experimental configurations of the simulations are described briefly followed by some of the simulation results.

The experimental configurations for the simulations are shown in Table 3. During the experiments, the initial trust value of the human on all trustees is considered neutral (zero) and the effect of the degree of trust interdependency has been observed using three different values [-1, 0, 1] of η for cooperation, neutral and competition. The models were analyzed against several experience sequences. An experience sequence is the series of experience values received by human from different trustees over time. The experience sequences used in the graphs presented in this section are shown in Figure 3. Here, three trustees are assumed namely S 1 , S 2 and S 3 , giving experiences E 1 , E 2 and E 3 respectively, where S 2 and S 3 give positive (1) and negative (-1) experience values respectively for the whole experiment (2000 time steps) while S 1 gives negative (-1) and positive (l) alternating periodically in a period of 500 time steps each (see Figure 3a). Moreover, in Figure 3b, S 1 gives positive (1) and neutral (0) experiences and S 2 gives negative (-1) and positive (1) alternating periodically in a period of 500 time steps each, while S 3 gives neutral (0) experiences for the whole experiment. This approach of using a shift in experience after a certain number of positive and negatives experiences is inspired on different empirical validations techniques of experience based trust models presented in literature (see e.g. [START_REF] Jonker | Human Experiments in Trust Dynamics[END_REF]). The presented experience sequences in this paper are selected to show adaptation of different trust models over sudden shifts in the behavior of the trustees.

Fig. 3. Experience Sequence used for Simulations

Experiment 1: Relative trust model

In this experiment the experience sequence of Figure 3a is used for the relative trust model as explained in Section 2. The results are shown in Figure 4. In Figure 4a, 4b and 4c the trust values T 1 , T 2 and T 3 of the trustee S 1 , S 2 and S 3 are shown on the yaxis for competitive, neutral and cooperative trust interdependency, respectively, while time is on the x-axis. In Figure 4a the interdependency is competition, so it can be observed that when S 1 gives positive experiences, the trust values of the other two trustees become lower and vice-versa. In Figure 4b, η is set to zero that means the trust values of trustees are mutually independent which shows in the graphs as well.

In Figure 4c cooperation is introduced by setting η = -1. Hence in Figure 4c it can be seen that when S 1 gives positive experiences it also effects the trust values of the other two trustees positively and vice-versa. Furthermore in the competitive case (Figure 4a) the maximum and minimum values of trust attained is higher than the neutral and cooperative cases. This is because competition gives an additional increase to the positive and negative trust values towards extremes while cooperation brings them closer to each other.

Experiment 1: Subjective experience based in combination with simple trust model

In this experiment the experience sequence of Figure 3a was used for the subjective experience based model described in Section 3 in combination with the simple trust model shown in Section 3.2. In Figure 5a, 5c and 5e the values of the subjective experiences for trustee S 1 , S 2 and S 3 are shown on the y-axis for competitive, neutral and cooperative trust interdependency respectively and in Figure 5b, 5d and 5f the respective trust values are shown. The patterns shown resemble the ones shown for the model presented in Section 2. In Figure 5b it can be noted that when trustee S 1 gives negative objective experiences, due to the competition values the subjective experiences of S 2 and S 3 become slightly higher and vice-versa. In Figure 5c as the interdependency value η is 0, no mutual effect of the subjective experiences on each other could be observed. The curves shown in Figure 5c also show the effect of the threshold function used in the model. In Figure 5e where η = -1, representing cooperation, it can be seen that an increase in objective experience of S 1 gives a positive boost to the subjective values of S 2 and S 3 and vice-versa. Furthermore, in the competitive case (Figure 5a) the maximum and minimum values of the subjective experiences are higher than for the neutral and cooperative cases. This is due to that fact that competition gives an additional increase to the positive and negative subjective experience values towards extremes while cooperation brings them closer to each other. Similarly these subjective experiences have a direct effect on the trust values of the trustees in each case (see Figure 5b,5d,5e).

Experiment 1: Subjective experience based in combination with trust model from literature

In this experiment the experience sequence of Figure 3a was used for the subjective experience for trust model from literature described in Section 4. One of the two models described in this literature is not accounting temporal discounting of experiences while the second does. In Figure 5a, 5c and 5e simulation results for the model without temporal discounting of experience are shown. In this case it can be observed that this simple model does not show the type of results as expected and generated by the other models. In Figures 6b,6d, and 6f the simulation results for model incorporating temporal discounting of experiences are shown. In Figure 6b it can be noted that when trustee S 1 gives negative objective experiences, due to the competition values the trust of S 2 and S 3 become slightly higher and vice-versa. In Figure 6d as the interdependency value η is 0, no mutual effect of the trust values on each other could be observed. In Figure 6f where η = -1, representing cooperation, it can be seen that an increase in objective experience of S 1 gives a positive boost to the subjective values of S 2 and S 3 and vice-versa. Furthermore, in the competitive case (Figure 6a, 6b) the maximum and minimum values of the trust are higher than for the neutral and cooperative cases. This is due to that fact that competition gives an additional increase to the positive and negative trust values towards extremes while cooperation brings them closer to each other (see Figure 6c,d,e,f).

Experiment 2: Relative trust and Subjective experience based trust models

In this experiment the second experience sequence was used where trustee S 1 gives positive (1) and neutral (0) and S 2 gives negative (-1) and positive (1) experience values alternating periodically every 500 time steps, while S 3 gives neutral (0) experiences for the whole experiment (see figure 3b). In Figure 7a (relative trust model) and 7b (subjective experience based trust model) it is shown that when trustee S 2 gives negative experiences, and there is a competitive interdependency the trust values of S 1 become slightly higher than the trust values of S 1 in Figure 7c and7d (where there is a neutral interdependency). In Figure 7c and7d as the interdependency value η is 0, no mutual effect of trust values on each other can be observed. In Figure 7e and 7f where η = -1 representing cooperation among trust values of trustees, it can be seen again that an increase in trust of S 2 due to positive experience gives a positive boost to S 1 and S 3 and vice-versa. Furthermore, in the competitive case (Figure 7a and 7b), the maximum and minimum values of trust attained for the trustees is higher than for the neutral and cooperative cases. This is due to that fact that competition gives an additional increase to the positive and negative trust values towards extremes while cooperation brings them closer to each other. Also here as S 3 is giving neutral experience in Figure 7c and7d, there is no change in trust value of S 3 because initial value of the trust is neutral as well. But the effect of competition and cooperation on S 3 can clearly be seen in Figure 7a, 7b and 7e, 7f.

Related Work

A variety of computational models have been proposed for trust. Falcone and Castelfranchi [START_REF] Falcone | Trust dynamics: How trust is influenced by direct experiences and by trust itself[END_REF] for example, present an approach which includes a cognitive attribution process to update the trust of an agent. This process has been incorporated into their trust model because they claim that the simple idea that positive experiences increase the trust is not always valid, and therefore a more complex process is needed. They do however not directly take interdependencies of trust levels into account.

Although in this paper simpler trust models have been used, the model as proposed by Flacone and Castelfranchi is certainly compatible with the subjective experience model as presented in this paper. Jonker and Treur [START_REF] Jonker | Formal Analysis of Models for the Dynamics of Trust based on Experiences[END_REF] present a formal framework for the analysis and specification of models for trust evolution and trust update. Here, both quantitative and qualitative examples are shown of trust functions. In this paper, the quantitative example model has been used to exemplify that the subjective experience approach is compatible with an existing trust function. The qualitative example could in principle also be used in combination with the proposed function for subjective experiences, however a mapping would be needed from the qualitative to the quantitative values and vice versa. [START_REF] Kluwer | Relative Trustworthiness[END_REF] incorporates the notion of relativeness as an extension of the trust model presented by [START_REF] Jones | On the concept of trust[END_REF]. In [START_REF] Kluwer | Relative Trustworthiness[END_REF] for determining trust, as a basis trust values determined by the model presented in [START_REF] Jones | On the concept of trust[END_REF] are taken and then these values are used in order to make statements about different trust values for different agents which does not incorporate the experiences with other agents that can perform similar tasks. In [START_REF] Hoogendoorn | Modeling Dynamics of Relative Trust of Competitive Information Agents[END_REF] a computational model of trust which does represent interdependencies between trust levels is presented. In the current paper refined version of this model has been used as a comparison with the presented alternative that allows the reuse of existing trust models, thereby showing that similar patterns can be generated. For a more extensive overview of existing computation trust models, see [START_REF] Sabater | Review on Computational Trust and Reputation Models[END_REF] and [START_REF] Ramchurn | Trust in Multi-Agent Systems[END_REF].

Besides formalised computational models for trust, also informal trust models have been proposed in other fields, for example, in the field of management sciences. An interesting example is the model proposed in [START_REF] Mokhtar | Collaborative Trust in Multi-agent System[END_REF] which specifically addresses trust in collaborative environments. However, the focus is not so much on how trust values are influenced due to interdependencies, but more on the requirements of trust values different agents have in each other in order to make cooperation successful.

Next to trust models, the notion of reputation is also frequently modeled. Hereby, reputation can be defined as the opinion or view of someone about something (cf. [START_REF] Sabater | Review on Computational Trust and Reputation Models[END_REF]) and according to [START_REF] Ramchurn | Trust in Multi-Agent Systems[END_REF] can mainly be derived from the aggregation of opinions of members of a community about one of them. In this paper, the main focus has been on the sole experiences of one agent, and the community view has not been addressed. Nevertheless, it would be an interesting part of future work to investigate how trust interdependencies affect the overall reputation of agents in a society. For an overview of computational models for reputation, see [START_REF] Sabater | Review on Computational Trust and Reputation Models[END_REF], and [START_REF] Ramchurn | Trust in Multi-Agent Systems[END_REF].

7

Conclusions and Future Work

In this paper, the notion of interdependent trust has been addressed. Hereby, two approaches have been taken: (1) to use a dedicated trust model which incorporates interdependent trust (which is a refinement of the model presented in [START_REF] Hoogendoorn | Modeling Dynamics of Relative Trust of Competitive Information Agents[END_REF]), and ( 2) to develop a model that transforms objective experiences into subjective experiences that can be fed into an existing trust model. In order to evaluate the two approaches, simulation runs have been performed to investigate to which extent comparable patterns come out of the approaches. In the simulations of the subjective experience variant three trust models have been used to generate such patterns (of which two were taken from literature). The patterns that appeared in accordance with the expectations.

For future work, a validation of the model based upon experiments with humans is planned. Furthermore, the integration of the subjective experiences with more complex models such as for instance the model of Falcone and Castelfranchi [START_REF] Falcone | Trust dynamics: How trust is influenced by direct experiences and by trust itself[END_REF] is also planned.

Fig. 1 .

 1 Fig. 1. Dynamic relationships in relative trust model

Fig. 4 .

 4 Fig. 4. Dynamics of relative trust model a) η=1, b) η=0 c) η=-1.

Fig. 5 .

 5 Fig. 5. Dynamics of subjective experience based trust model a) subjective experience for η=1 b) Trust for η=1, c) subjective experience for η=0, d) Trust for η=0 e) subjective experience for η=-1, f) Trust for η=-1.

Fig. 6 .

 6 Fig. 6. Dynamics of subjective experience based on trust models from literature a) without temporal discounting and η=1 b) with temporal discounting and η=1, c) without temporal discounting and η=0, d) with temporal discounting and η=0 e) without temporal discounting and η=-1, f) with temporal discounting and η=-1.

Fig. 7 .

 7 Fig. 7. Dynamics of relative and subjective experience based trust model for experiment 2 a) relative trust model for η=1, b) subjective experience based model for η=1, c) relative trust model for η=0, d) subjective experience based model for η=0 e) relative trust model for η=-1, f) subjective experience based model for η=-1.

Table 2 .

 2 Change in objective experience with interdependencies

	α=trust bias	η=dependency
	E1	E'1	T1
	E2	E'2	T2
	E3	E'3	T3

Table 3 .

 3 Model configurations used for simulation experiments

	a)	b)


Gen Kitagata

Debasish Chakraborty

Satoshi Ogawa

Atushi Takeda

Kazuo Hashimoto

Norio Shiratori

Visitor Access Control Scheme utilizing Social Relationship in the Real World

Keywords: access control, socialware, symbiotic computing, collaborative work

Access control to resources is one of the most important technologies for supporting human activities in the digital space. To realize the control two schemes were proposed: RBAC (Role-Based Access Control) and TRBAC (Temporal Role-Based Access Control) by adding time constraints and role dependencies to RBAC. However, these methods are not effective for temporal activities such as visitor access because of maintenance costs and inadequacy in safeness. In this paper, we focus on a visitor access control in the real world, by utilizing relationship with users and situations, and propose a novel access control scheme which is effective for temporal activities.

Introduction

Growth of ubiquitous computing technology make people's activities in digital space more popular than ever. Digital space is a kind of societies where people participate and interacts. Same as in real space, people in digital space should recognize society, and be able to take actions without anxiety and discomfort. Socialware [START_REF] Kinoshita | Symbiotic System: Co-existence and Mutual Respect of Human, Society, Environment, and Information System, Forward: Socialware[END_REF] is a software technology to support people's activities in digital space by enhancing social reality. Socialware has two goals: to apply existing rules and knowledge used in real space to activities in digital space, and to create new and knowledge specific rules to digital space. In social knowledge, where knowledge involved with social activities, is an important information source to enhance people's social reality in digital space. In this paper, focusing on access control to resources in digital space, which is indispensable for activities in digital space, we propose a novel access control scheme based on the concept of Socialware.

RBAC (Role-Based Access Control) [START_REF] Sandhu | Role-Based Access Control Model[END_REF] is one of the existing access control schemes, where users are assigned with roles, and roles with access rights. This scheme has an advantage of management cost because roles are, in general, likely to be associated with positions in an organization. However, this scheme requires static configuration of acceptable roles in ACL (Access Control List). So to add, change, and delete users and roles, it has to be done manually. Therefore, this scheme is effective where roles are semi-static. But some users accesses should be enabled temporarily. This is because, in the latter case, administrator will be burdened by frequent manual management of ACL, and also there might be an issue of safety if administrator forgot to disable temporal access rights afterwards. TRBAC (Temporal Role-Based Access Control) [START_REF] Bertino | TRBAC: A Temporal Role-Based Access Control Model[END_REF] is an access control scheme for dynamic and temporal changes to access rights assigned to roles. TRBAC is effective for activities with clear action times, such as a task starting from a fixed time. However, TRBAC can not deal with occasional meetings and unexpected activities caused due to emergency situation. Therefore, it is necessary to dynamically control access rights for activities with no clear action time.

In this paper, we propose automated visitor access control scheme to control third person's access right by utilizing social relationship. Our scheme flexibly gives access rights in response to situation of workplace and social relationship. This realizes temporal grant of access to resources for irregular activities that do not have explicit action times such as occasional meeting. It is to be noted that 'right' and 'authentication' has been used to represent the same meaning throughout this paper if not otherwise mentioned.

The remainder of this paper is organized as follows. In Section II, we introduce related works on access control and issues. The proposed scheme and its model are described in Section III. Section IV presents a collaborative work support system with the proposed scheme, and Section V presents experiments and discussion with the system. In Section VI, we compare our scheme with existing access control scheme utilizing social relationship. We conclude our work in Section VII.

Related Works

TRBAC (Temporal Role-Based Access Control) [START_REF] Bertino | TRBAC: A Temporal Role-Based Access Control Model[END_REF] introduces time constraint and role dependencies to its scheme, to deal with temporal roles. For example, assume that a part-time staff works with some company from 9 a.m. to 1 p.m., and a role 'parttime-staff' is assigned to the staff. In this case, an administrator can activate the role 'part-time-staff' from 9 a.m. to 1 p.m. in order to give the staff an access right to the company's system with some time constraint. In addition, validity of a certain role can be controlled in response to the condition of other role, which is called role dependencies. For example, a role 'nurse' can be active only if a role 'doctor' is active. With time constraint and role dependencies, TRBAC effectively deal with regular activities. However, administrator has to make changes to roles for temporal or emergency activities, and higher the frequency of such activities, heavier the workload. Therefore, it is necessary to realize temporal access grant for temporal and emergency activities.

3 Access control proposal based on real space social interactions

Access control in real space

This paper introduces the notion of temporary access control based on irregular time stamps. This concept is difficult to apply in the existing TRBAC. In real world, there is a need to grant temporary access control during undetermined time stamps, as shown 1(a), due to the fact that U ser A is not in the laboratory, U ser B and U ser C are unable to identify U ser D. Therefore, U ser D will not be allowed inside. Since U ser A is not present, L infers that there is no cooperative project in development and so U ser D would not receive the permission to enter the laboratory. On the other hand, as shown in picture Fig. 1(b), when U ser A is in the laboratory, it creates an environment in which U ser D is authenticated as socially related with U ser A. Therefore, U ser D is allowed inside the room. In this way, rooms that normally would be out of reach for an outsider, can be accessed due to the social relationship.

While inside the laboratory, person U ser A becomes responsible of U ser D's behavior. For that reason, U ser D can have same or less access privileges than U ser A. In this similar way we introduce the term of social relationship based access control authority delegation.

Proposal

As we presented in the previous chapter, we introduce the notion of automatic temporary access control based on irregular time stamps. This concept is difficult to implement by using only TRBAC. We intend to implement in the digital space the same concept regarding access control permissions as in the real world. The spectrum of our access control permissions greatly depends on the existence of a guarantor at the location where a certain job or task is being undertaken.

Therefore, we consider the following two conditions as important:

-T1 -selection of the socially related user from inside the working place (L) -T2 -delegation of rights based on social relationship

Based on the previous two conditions, we propose the following:

-S1 -Implementation of the workplace.

-S2 -Social relationship based access control filter and delegation of rights.

We will explain in detail about S1 and S2 in the next chapters.

The introduction of a work place In real space, depending on the existence of a guarantor, in other words if there is no social relationship, our access to certain resources in a certain environment are limited or completely restricted. In order to introduce this concept into the digital world, we have to explicitly state the existence of a working place. So far, this was not considered by the existing access control models. Because of the existence of the working place we can now define the relationship between the users that activate within its boundaries. The working place in this case is what we defined in Section III(A) as L. Inside the working place, there are several resources like printer, projector etc., which can be accessed by outsiders only with the explicit permission of an insider with the right permissions and the right social relationship.

Delegation of access control based on social relationship A couple of events occur when U ser A, the user that delegates the access rights transfers its rights to U ser D, the user that receives the delegated rights.

-The delegation of rights occurs in conformity with the social relationship between the two. -The person that receives the rights cannot have more rights that the person that delegates the rights.

In order to meet the previous two requirements, we propose an authentication filter whose role is to delegate only the necessary rights from U ser A to U ser D . The access rights of U ser D will be the intersection between the set of rights of U ser A and set of rights accepted by the filter. The control knowledge (access control rules) is given by the pair of social relationship and permission filter. As shown in Fig. 2 If the permission delegation does not occur in a hierarchical manner, from the security point of view we do not have a trustworthy environment. Therefore, we introduce the concept of allowing rights which enables the user with access permissions to delegate his rights to others. To fulfill this we employ two types of filters: 1. Filter A -which will give right to delegate even to the outsiders if they are trustworthy. 2. Filter B -which will give only specific rights to outsiders, but not the right to delegate.

The concept in detail

Factors (components) and models In this proposal we introduced seven components of the access control model: resources, users (visitor and member), access (authority) rights, (permission) rights filter, social relationship, work place and access control knowledge. Fig. 3 shows our access control model. We will explain them in detail as follows.

-Resource I: computing resources or secret information which fall into the authority of access control. -Outsider O: a visitor who wants to use resources but not having permission regularly. -Member M: a member of organization who has regular permission for resource usage. -Access authority (permission, rights) P: the set of rules against the resources utilized by users. -Permission filter F: the set of access that can be delegated.

-Social relationship R: the link between users (e.g. if there is a cooperative project under development, the participating members are bound by social links). -Workplace W: the place where resources are located.

-Access control knowledge K: this knowledge is used to choose authority filter which is used for authority transferring utilizing social relationships among users.

Workplace (attribute value; property value) In our proposal, considering the importance to retrieve information about the status of a user, we define the workplace as follows:

w = u list , i list u list = u 0 , u 1 , ..., u n i list = i 0 , i i , ..., i m w W, u n R, i m I
In this case, the u list , and i list are set of users and resources in a certain workplace. In other words, our workplace is formed of users and existing resources. The user's status with regard to the workplace might change. Therefore w changes with time. User u is defined as: In this case, d u represents the user's data and ru list represents the set of social relationships of the user. For example, in case of cooperative project, we can identify it as social relationship between the coworkers. Delegation of access control We propose a system in which a user u u wishing to utilize a workplace w is looking for a user u a with whom u u has a social relationship r and it is being identified by the latter. The permission filter is based on the access control knowledge and the social relationship. As a result, the permission p a , held by the user u p intersected with the permission filter set f , produces the set of permissions p u of user u u . The process of granting access permission p to user u u is shown in Fig. 4. The algorithm starts with the selection of the socially related user (decideDelegater) which can delegate permissions. In order to do that, the delegateP ermissions function is applying the getP ermissionF ilter and returns the proper access control rights. In Fig. 5 we show how the access knowledge works.

u = d u , ru list , p list ru list = ru 0 , ru 1 , • • • , ru n ru k = r k , u k p list = p 0 , p 1 , • • • , p n r k ∈ R, u k ∈ U,

The process of granting access permission

We explain the process of granting access permission with Fig. 6. In this example we portray user UserD who is not a part of the laboratory L but has the intent of activating for a while there. The users UserA and UserB are members of laboratory L. UserD and UserA are socially linked through a common (cooperative) project and the former has rwa (read, write, allow) rights for the resource 1. Socially linked users as co-researchers are empowered by the access control knowledge with rw rights for resource 1. We present the process of granting permissions to UserD as follows:

1. UserD asks for access permission from the workplace -in this case the laboratory L. 2. The users that have any social link with UserD reply to it. 4. Based on the rules, UserA becomes the guarantor of UserD . 5. If the authentication process is successful, UserA requests access permissions from the resource administrator. 6. The resource administrator checks all the resource access knowledges, passes them through permission filter and intersects them with the set of UserA 's permissions resulting in UserD 's permissions.

In this way, utilizing our concept, even if UserD does not have permissions to access resources, due to the social link with UserA , the former will be granted temporary access rights to the resources that make the object of the common goal.

Cooperative Work Support System 4.1 Summary of the System

To confirm effectiveness of our proposal, we design a cooperative work support system. This system realizes access control for resources owned by organizations, and also the system can be applied for temporal activities of users by utilizing social relationships. Fig. 7 shows summary of the system. In Fig. 7, there are two organization X and Y. These organizations proceed cooperative project. Social relationship such as "cooperative project member" are constructed among users who are joined the project. Due to this social relationship, users belonging to organization Y and are joined the project can use resource in organization X. By contrast, users belonging to organization Y but are not joined the project and has no relationship with member of organization X cannot use the resource in organization X. Also a visitor who does not belong to both organization X and Y, and has no relationship with member of organization X cannot use the resource in organization X.

Agent composition

We design the system based on agent-oriented computing and introduce the following three agents:

1. User Agent: This agent is a delegate of a user in digital space. This agent uses resources instead of real user according to the user's request. 2. Resource Agent: This agent agentificates resources and has access control knowledge and an authority filter. For instance, we designed a printer agent (printerAg) and a projector agent (projectorAg). 3. Workplace Agent: This agent administrates user agents and resource agents in workplace. It delegate access authority to a user according to social relationships by referring access control knowledge held in resource agent.

Fig. 8 shows agent composition of our system. userAg1 to userAg3 represents user agents; printerAg and projectorAg are resource agents. And workplaceAg is a workplace agent. And workplace in Fig. 8 represents the space where user works. The field is administrated by workplaceAg. Here, presence of a user is expressed as presence of a user agent in workplace. For example, when a user sends a request for authority delegation but no response is returned by any user agents, it implies that there are no member who has social relationship with the user, and as a result access for requested resource is denied.

Environment of Implementation

We implemented the system by using DASH [START_REF] Fujita | Agent-based design model of adaptive distributed systems[END_REF] system which is rule-based agent framework, and IDEA [START_REF] Uchiya | Interactive Design Environment for Agent-Based System[END_REF] which is an integrated design environment for DASH. We used Java language to implement base processes controlled by DASH agents.

Experiment and Evaluation

To evaluate our proposal, we conducted experiments with some scenarios under certain conditions depicted in Fig. 9 authorities of U ser A and U ser B are not same. This is because they are delegated authorities by different user. Also in some scenarios, we found cases when authority is not delegated. In these scenarios, because a member who has social relationship with the visitor, user A or U ser B, is absent and the system cannot verify identity of the visitor, and no authority is delegated. In other words, absent of U ser C means that cooperative work of U ser A and U ser C are not proceeded. Therefore U ser A cannot get authority while U ser C is absent. By the above results, we confirmed that our system is useful to delegate authority for temporal activities by utilizing social relationship of users presented in field of activity.

Discussion

Visitor access control schemes utilizing social relationship was proposed in previous works [START_REF] Nagao | A Secure Distributed Database System with Time-series Data and Social-Relation Based Information Access Control[END_REF]. In this access control scheme, access rights are statically configured based on social relationship. Because of static configuration, administrator has to configure multiple access rules for each social relationships. For example, necessary rules for a relationship of 'co-researcher' are professor, associate professor, student and so on. In contrast, the proposed scheme gives an access right to a user by applying authentication filter to the right of who offer the user's personal reference. Therefore, administrator only needs to configure authentication filter and access control rules for each relationship. For example, one set of them for the 'co-researcher' relationship. In addition, existing scheme uses social relationship of all users regardless of existence of them. This can realize temporal access grant with time constraint for regular activities, but unable to deal with irregular ones. In contrast, proposed scheme can effectively control access rights even if temporal grant of access is necessary.

Conclusion

In this paper, we proposed a novel access control scheme to automatically grant accesses for irregular activities such as resource usage of visitor which TRBAC cannot deal with. This scheme achieves to control access rights in digital space as in real space.

Fig. 1 .

 1 Fig. 1. Access control in real-space

Fig. 2 .

 2 Fig. 2. Delegation of access authorization

Fig. 3 .

 3 Fig. 3. Access control model of our scheme.

Fig. 4 .

 4 Fig. 4. Algorithm for access delegation

Fig. 5 .

 5 Fig. 5. Access control knowledge for a laboratory

Fig. 6 .

 6 Fig. 6. Flow of access authorization

3 .Fig. 7 .

 37 Fig. 7. Cooperative work support system

Fig. 8 .

 8 Fig. 8. Agent composition

Fig. 9 .

 9 Fig. 9. Precondition of operation scenario

Fig. 10 .

 10 Fig. 10. Evaluation results

  , in order to delegate access control rights based on social relationships, we need to setup the access

	AuthUser: n social relationship between users existing technique according to social empowerment relationship P auth AuthUser: n social relationship between users empowerment according to social relationship existing technique P auth access control knowledge Pfilter Relation: r access control knowledge Pfilter Relation: r	AuthUser: registered and existing users(transferring users) Outsider: external users (transferred person) Relation: social relationship Pauth: AuthUser's authority Pfilter: authority filter Poutsider : Outsider's authority
	Outsider: o Outsider: o	P outsider = P auth ∧ P filter P outsider = P auth ∧ P filter	traditional technique proposed technique

  So there are social relationships according to these cooperative researches. In addition, U ser C is a student and U ser D is a staff, so U ser D has much authority than U ser C. We assume situations that a visitor, U ser A and U ser B, comes to laboratory's workplace to proceed cooperative research. Here, we conducted 4 experiments as following scenarios: (1) no one is in the laboratory, (2) only U ser C is present, (3) only user D is present, (4) both U ser C and U ser D are present.Fig.10shows experimental results. We confirmed that both U ser A and U ser B got access authority by social relationship as "cooperative research member", but the

	(1) None (1) None (Users in Workplace Cases scenario	User A requests access rights X User A requests access rights X	User B requests access rights X User B requests access rights X
	(2) User C (2) User C	p1, p2 p1, p2	X X
	(3) User D (3) User D	X X	p1, p2, p3 p1, p2, p3
	(4) User C & D (4) User C & D	p1, p2, p3 p1, p2, p3	p1, p2, p3 p1, p2, p3
	X: no access right is granted due to lack of personal reference

. U ser C and U ser D are member of laboratory, and U ser A and U ser B are visitors. U ser C proceeds a cooperative research with U ser A. U ser D also does another cooperative research with U ser B.

Acknowledgement

This work is partially supported by the Research and Development of Dynamic Network Technology program of NiCT.