Evolution of trust networks in social web applications using supervised learning_大学生考试网
当前位置： >>
Evolution of trust networks in social web applications using supervised learning
Procedia Computer Science 3 (9Procedia Computer Science 00 (0Procedia Computer /locate/procedia Science/locate/procediaWCIT-2010Evolution of trust networks in social web applications using supervised learningKiyana Zolfaghar a *, Abdollah Aghaieb,b a Post graduate student, IT Group - Faculty of Industrial Engineering K. N. Toosi University of Technology, Tehran, Iran Associate professor, IT Group - Faculty of Industrial Engineering K. N. Toosi University of Technology, Tehran, IranAbstract Trust as a major part of human interactions plays an important role in addressing information overload, and helping users collect reliable information in SocialWeb applications. Although many researchers have already conducted comprehensive studies on the trust related online applications, the understanding of trust evolution is still unclear to the researchers. In this study, we move toward time-aware trust prediction in evolving online trust networks. Achieving this, we investigate the impact of considering the temporal evolution of trust networks explicitly in trust prediction tasks by using a supervised learning method. We incorporate the history information available on the trust relations (or links) of the current trust network state in prediction process. Our results unequivocally show that timestamps of past trust relations significantly improve the prediction accuracy of future trust relations. c ? 2010 Published by Elsevier Ltd. Selection and/or peer-review under responsibility of the Guest Editor.Keywords:NTSocial WS1. Introduction Studying the social phenomena within computer science and web environment, demands more attention in recent years. In this regard, trust is a crucial basis for social interactions among users in online environment specifically SocialWeb applications in which user participation is the primary driver of value. Social web is one of the incarnation of web2.0 which focuses on an online social transformation that has put more interactivity and control of content into the hands of regular users instead of just big site owners [1]. Web-based social networks, online social media sites, and large-scale information sharing communities are prominent examples of SocialWeb applications which rely heavily on the opinions, contributions or actions of communities of online users. With so much userinteractions and user-generated content in online environment, the needs for establishing trust mechanisms online become apparent. To be assured of the reliability of these user generated contents, users need to know if the source of this information is trustworthy or not. In other words, the trustworthiness of the user providing the information is as important as the reliability of information they provide. If trust can be estimated accurately, the user can then use this trust estimation to make decisions on the reliability of information. Trust relations between online users in these application can be manage in a graph structure, called trust network, in which nodes indicating users and edges indicating trust relations between them. Trust networks are dynamic since new edges and vertices are added to the graph over the time. Understanding the dynamics that drives the evolution* Kiyana Zolfaghar. Tel.: +98-21-; fax: +98-21-. E-mail address: kzolfaghar@sina.kntu.ac.ir.c
? 2010 Published by Elsevier Ltd. doi:10.1016/j.procs.834K. Zolfaghar, A. Aghaie / Procedia Computer Science 3 (9Kiyana Zolfaghar / Procedia Computer Science 00 (0of trust network is a problem that will be addressed in this paper. In the recent years, there is significant interest in methods that use only the graph structure to make trust predictions. However, all of them consider a single snapshot of the network as the input, neglecting an important aspect of these trust networks viz., their evolution over time [2, 3]. Our main objective is to predict the likelihood of future trust relations between users. To predict prospective links in trust network, we will map our problem to a formal link prediction problem and then adopt a supervised learning approach to solve it. We conducted an empirical evaluation of our techniques
which is a well-known and very large collection of data dealing with trust computation. Our experiments show that incorporating time-based weights significantly improves the prediction performance of future trust relations. The rest of the paper is organized as follows: Section 2 provides a background on concepts used throughout the paper. Section 3 which forms a key contribution of this paper, describes in detail how to incorporate temporal features of an evolving trust network for prediction of future trust relations. Section 4 describes the experiments we run and discusses their results. We finally draw conclusions in Section 5. 2. Background 2.1. Trust in social web application Consistent with growing of social ecosystems across the web, trust is becoming an important factor for many online systems in web domain that seek to use social factors to improve functionality and performance. In a virtual environment where participants are usually anonymous and do not engage in direct face-to-face communication, trust can be a significant issue. In this regard, trust is a prerequisite of social behaviour, especially on the subject of important decisions. In the context of social web, trust in a person is defined as a commitment to an action based on a belief that the future actions of that person will lead to a good outcome [4]. To better predict trust in the context of social web, it is necessary to identify factors that influence trust formation process. According to the literature, we decided to employ 5 critical aspects of social trust consisting of reputation, knowledge, similarity, relationship and personality-based trust which are usually considered important in the social trust formation mechanism on the web [5]. These qualitative factors can be mapped into some measurable feature values that can be used to predict future trust relations. A brief description of these factors is shown in Table 1.Table 1. Social trust factors in online environment. Trust Factor Knowledge Factor Relationship Factor Reputation Factor Definition Refers to the trust building mechanism where individuals get to know each other through interactions and then predict others behaviors based on the information they obtain from this interactive process. Refers to the trust building mechanism which relies on qualitative assessments based on connections found in social networks and online communities Refers to the trust building mechanism in which trustee behavior in the whole system affect the amount of his trustworthiness. Refers to a trust building mechanism which implies that trust is established based on social similarities such as common characteristics the trustor perceives of the trustee including interests, values, and demographic traits which can lead to establish a new trust relationship between two sufficiently similar users. Refers to users’ individual traits that lead to expectations about the ones’ trustworthiness.Similarity Factor Personality Factor2.2. Supervised learning Supervised learning is the machine learning task which focuses on learning a target function that can be used to predict the values of a discrete class attribute. There is a plethora of classification algorithms for supervised Learning. In this research, we used MLP neural networks with the back-propagation learning algorithm as the baseline prediction model. MLP is represent the most prominent and well researched class of ANNs in classification. It is generally composed of an input layer, an output layer and one or more hidden layers. The input nodes pass values to the first hidden layer, its nodes to the second and so on till producing outputs. In this architecture, the input nodes are the feature values of an instance, and the output nodes (usually lying in the range [0, 1]) represents the class of the instance. Learning occurs in the perception by changing connection weights after each piece of data is processed, based on the amount of error in the output compared to the expected result[6]. For exploiting MLP neural network, a well known machine learning library, WEKA will be used.K. Zolfaghar, A. Aghaie / Procedia Computer Science 3 (9Kiyana Zolfaghar / Procedia Computer Science 00 (08353. Evolution of Trust network Trust relationships can be described as a directed graph G = (V, E) where V represents a set of unique users and E represents direct trust relations between them. Trust networks are highly dynamic objects as they grow and change quickly over time through the addition of new edges. Understanding the mechanisms by which they evolve is a fundamental question that is still not well understood, and it forms the motivation for our work in this paper. To investigate this evolution and predict prospective trust relations in trust network, we map it to a temporal link prediction problem in which a snapshot of the set of links at time t is given and the goal is to predict the links at time t + 1 [7]. After mapping trust network evolution into link prediction problem, we study link prediction as a supervised learning task. Achieving this, we should build link predictors by extracting feature vectors from network structure or contextual data available in the social web application and then train predictors on extracted feature vectors using supervised learning algorithms. For building link predictors, we adopted two approaches: static and dynamic (Fig. 1). In the former, we use a static snapshot of a trust network at time tn. This is a common approach for temporal link prediction. in the latter, we adopted a new approach which is more dynamic and consider the time domain in building link predictors in a way that we capture a sequence of snapshots from the trust network based on the time periods before tn+1 then we compute link predictors for each snapshot and construct our final dataset by combining values of each predictor for different snapshots using a weighting method. This approach helps us to build link predictors which are time-dependent indeed. In this paper, we use an exponentially weighting approach to give different weights to different data points. The weighting for each older data point decreases exponentially, giving much more importance to recent observations while still not discarding older observations entirely.Fig. 1. Proposed approaches to evolution of trust network4. Data and Experimental SetupAs a case study, Epinions network is chosen, which has been used previously in trust propagation and trust-based recommendation research.
is a large product review community that supports various types of interactions as well as a web of trust that can be used for classification training and evaluation. Epinions as a multicontext social network allows users to write text reviews and to rate other users’ reviews with numerical ratings. These reviews are intended to be a help for other users in making a decision of whether to buy or not certain products. Epinions also gives a web of trust that would allow a user to express trust of other users. The dataset used in further experiments is a publicly available dataset of
network, crawled by Paolo Massa [8]. The statistics and description of the dataset used in our experiments is given in Table 2.836K. Zolfaghar, A. Aghaie / Procedia Computer Science 3 (9Kiyana Zolfaghar / Procedia Computer Science 00 (0 Table 2. Statistics of Dataset Description #users #Reviews #Ratings #Trust Statement Number of ~ 2 717667 Range of values [1,132000] [1,1560144] [1,5] 1For Epinions, we have 3 years of dataset, from 2001 to 2003. To study evolution of trust network by predicting future links, we partition the range of year into two non-overlapping sub-ranges. The first 2 years is selected as train years and the later one as the test years. Then, we prepare the classification dataset, by choosing those author pairs that appeared in the train years, but did not have trust relation in those years. Each such pair either represents a positive example or a negative example, depending on whether the trust relation will establish in the test years or not. Classification model of link prediction problem needs to predict this link by successfully distinguishing the positive classes (trust label) from the dataset. The dataset is constructed such that the model learns to map feature values from a time-interval to class labels in a future time-period. Thus, link prediction problem can be posed as a binary classification problem, which involves each candidate trustor-trustee pair to be assigned either a trust or notrust label and can be solved by employing effective features in a supervised learning framework. 4.1. Feature Set Choosing an appropriate feature set is the most critical part of any machine learning algorithm. To face this challenge, we develop o social trust-inducing factors described in section 2.1 and apply these factors to trust evolution problem by mapping each qualitative factor into some corresponding measurable features. These factors are general enough to be adopted in different applications in social web context. These features derived from both contextual information, extracted from users behaviours such as ratings information, and structural data available in the trust network topology. In this section, we provide a short description of all the features that we used as link predictors in trust network evolution. 4.1.1. Knowledge-Based Trust This factor is represented as a measure by which it combines the overall satisfaction on interactions performed between trustor and trustee. In Epinions dataset, it refers to reviews of trustee (u j) rated by trustor (ui). We expect these rates tell us how good trustor thinks of reviews written by trustee so satisfaction can be obtained by the average of all ui’s ratings on reviews written by uj. The number of interaction is also important (|Rij|). For example, if satisfaction i, j= satisfactioni,l, but |Rij| & |Ril|, then, since i and j have been participated in more interaction, so the trustor knowledge from trustee is stronger. Achieving this, we used the sigmoid function to keep the returned value in the range of [0, 1] as well as to consider the effect of the large (|Rij|). and decide the slope and controls the midpoint of the sigmoid curve respectively. (1)4.1.2. Relationship-based trust This factor is considered as the basis of trust computation in most recent models in web domain. The reason is that structure and topology of network always affects its’ function so we should measure how much each pair of users are reachable from each other in the network of trust [4]. Calculating this factor, we can use Closeness centrality measure in social network analysis. In this regard, we calculate the Katz measure to analyze the “proximity” of trustor and trustee in trust network. It computes a weighted sum over all paths between trustor and trustee [9]. (2)K. Zolfaghar, A. Aghaie / Procedia Computer Science 3 (9Kiyana Zolfaghar / Procedia Computer Science 00 (08374.1.3. Reputation- Based Trust Factor This factor can be measured based on first, trustee popularity which measures social importance of user in the network and second, acceptability of trustee behaviour in the whole system which can be obtained through contextual information such as the quality of his reviews, available in Epinions dataset. To measure structural reputation, we use PageRank algorithm which is one of the most common method for calculating popularity in a graph-based representation network such as trust network [10]. (3) Acceptability of trustee behaviour in the Epinions website can be obtained according to his reputation on reviewing products. To compute reputation of trustee as a review writer, we aggregate the quality of all reviews that the trustee has written. The quality of a review is considered as an average of received ratings ( ). Since, if a reviewer has written just one review close to the average, it is hard to conclude the writer as a reliable reviewer. Hence, we also consider the number of reviews in order to discount less experience of writing reviews. Therefore, review writers who write high quality reviews more than others have higher reputation as a review writer. (4) Where R(uwi) is the set of reviews written by trustee u and | R(uwi) | denoted the number of items in this set. is the quality of reviews Witten by trustee. 4.1.4. Personality- Based Trust Factor. This factor shows user tendency to trust, determines how easy a specific trustor trusts other users in the system. If an online user has a high tendency to trust others in general, this disposition is likely to positively affect his or her trust in a specific trust party. This factor is associated with the trustor and it does not depend on candidate trustee at all. It can be calculated based on both structural and contextual data. Structural propensity to trust, which shows the trustor gregariousness, can be computed based on the number of ties that the node directs to others. On the other hand, contextual propensity to trust refers to global leniency a trustor shows to his or her trustees according to his ratings which can be measured by the relative difference between the trustor ratings on the reviews and the average ratings of others to that reviews. (5) (6)_Where Ri is the set of items which is rated by trustor i, r ij is the rating that rater i gave to review k and r k is average of received ratings of review k from other users. 4.1.5. Similarity- Based Trust Factor. Similarity between trustor and a trustee can be calculated based on their structural and contextual similarities. Structural similarities refer to common neighbours whom both trustor and trustee relate to. Measuring structural similarity, we used SimRank which is a general similarity measure in graph-theory and it is applicable in any domain. According to SimRank, two nodes are similar to the extent that they are joined to similar neighbours [11]. (7)Contextual similarities measure whether trustor is similar to trustee in preferences and ways of judging issues which can be computed based on their similarities in ratings in Epinions. In this regard, the common set of items that have rated with both users, is denoted by RS(i,j)=Rate(i) Rate(j) .To compute the rating similarity between i838K. Zolfaghar, A. Aghaie / Procedia Computer Science 3 (9Kiyana Zolfaghar / Procedia Computer Science 00 (0and j over the common set RS(i,j) we model the reviews rated by i and j as two vectors respectively. Particularly, we use the standard deviation of the two feedback vectors to characterize the similarity. The number of items in common set is also important. The more the number of common ratings for a given pair of peers, the more similar they are. If the two users have rated just one common item, it would seem unwise to conclude they are similar. Hence, it compensates by sigmoid function. (8)4.2. Results and Discussions After preparing the dataset and construction of trust inducing factors, we enter the modelling phase. As indicated earlier, we experimented with MLP with the back-propagation learning algorithm as the prediction model. Experiments were conducted using WEKA toolkit. The experiments were carried out and validated with a 5-fold cross-validation in which the sample is divided in 5-folds.Any four of the five segments is selected to perform training. The remaining part will be executed for testing the model. As a result, each part will be trained and tested five times. Finally the average performance is calculated. Precision, recall, F-measure and area under ROC curve are the evaluation methods which are used in this paper to examine the performance of the prediction models.Table 3. Prediction performance for the static approach Class Trust label Non-Trust label Weighted Avg. TP Rate 0.657 0.815 0.739 FP Rate 0.185 0.343 0.267 Precision 0.767 0.72 0.742 Recall 0.657 0.815 0.739 F-Measure 0.708 0.765 0.737 ROC Area 0.804 0.804 0.804The experiments are conducted in two phases. In the first phase, we calculated trust link predictors for a single snapshot of whole network till time t to predict prospective trust links at time t+1. Then the prediction model based on MLP is built on this dataset. The architecture of this model is 8 neurons in input layer and 1 hidden layer consist of 5 neurons and 2 neurons in output layer for the two class labels. The result of this model is summarized in table 3.Fig. 2. Dynamic model performance for different values of weighting factorsIn the second phase, we adopted the dynamic approach in which trust network was divided into numbers of snapshots based on specific time intervals and the link predictors were then calculated for each snapshot individually. Consistently, we divided our two-year training data to four 6-month intervals and compute trust factors for each period. To construct the final dataset, we used exponential moving average to combine values of each predictor for different snapshots [12]. To determine optimized value of weighting factor, we repeated the experiment several times (Fig. 2). The best prediction model obtained for weighting factor equal to 0.7.It shows that the recent data were more important in prediction process. The architecture of the MLP model was the same as the architecture of prediction model in the first phase. The result of the model is summarized in table 4.Table 4. Prediction performance for the dynamic approachClass Trust labelTP Rate 0.786FP Rate 0.186Precision 0.796Recall 0.786F-Measure 0.791ROC Area 0.877K. Zolfaghar, A. Aghaie / Procedia Computer Science 3 (9Kiyana Zolfaghar / Procedia Computer Science 00 (0839Non-Trust label Weighted Avg.0.814 0.8010.214 0.2010.804 0.8010.814 0.8010.809 0.8010.877 0.877Comparing the results of experiments in table 3 and 4 have shown that the dynamic approach outperformed the static approach in trust prediction. According to the result, the overall performance of prediction model was increased from 73.7% for static approach to 80.1% for dynamic approach in terms of F-measure. These results are completely consistent with the dynamic characteristics of trust so time as a contextual feature can affect the process of trust formation in social interactions on the web environment. Regarding the value of 0.7 for the optimized weighting factor, we can come to this conclusion that in studying the trust evolution, recent data has more weight to predict the future structure of trust network. This fact can be helpful in trust prediction for large dataset. As trust networks evolve continuously, the size of network becomes larger and larger. This poses a number of challenges in terms of the space and time burden on the system. In this situation, we can predict prospect trust relations more easily by adopting dynamic approach for the last M interval instead of using the whole network such as what we face with in static approach. 5. Conclusion The web is increasingly becoming a social place by shifting from just existing to participating for the users. In this regard, trust is considered as a fundamental element for interactions among them. In this paper, we presented methods to incorporate temporal information available on evolving trust networks into prediction of future trust relations. We used a supervised learning method for building link predictors from both structural attributes of the trust network and contextual information, extracted from user behaviour in his online social interactions. To achieve good prediction accuracy, we employed 5 critical aspects of social trust consisting of relationship, reputation, knowledge, similarity and personality-based trust. Then we mapped each of these qualitative factors into some corresponding measurable feature sets in a systematic manner. The experiment results on Epinions dataset showed that incorporating time-based weights significantly improves the prediction performance of future trust links in trust networks. References 1.O'Donovan, J.A., Using Trust in Social Web Applications. In J. Golbeck, In Computing with Social Trust, Springer, London ,(7. 2. Matsuo, Y., Yamamoto H. Community gravity: measuring bidirectional effects by trust and rating on online social networks. Proceedings of the 18th international conference on World wide web, Madrid, Spain (0. 3. Ma, N., Lim, E., Nguyen, V., Liu, H. 2009. Trust Relationship Prediction Using Online Product Review Data. Proceeding of the 1st ACM international workshop on Complex networks meet information CNIKM’09, Hong Kong, China,(. 4.Golbeck. J. Computing and Applying Trust in Web-based Social Networks, Doctoral Dissertation, University of Maryland, College Park, (2005). 5. Zolfaghar, k. and Aghaie, A. Computational Trust in SocialWeb: Concepts, Elements, and Implications. International Journal of Virtual Communities and Social Networking, 2(. 6. Han, J., Kamber, M. Data Mining:Concepts and Techniques. Elsevier, San Mateo, (2006). 7. Getoor, L. and Diehl, C. P. Link mining: a survey. SIGKDD Explorations 7 (. 8. P. Massa and P. Avesani. Controversial users demand local trust metrics: experimental study
community. In AAAI, (2005). 9. Katz, L. A new status index derived from sociometric analysis. Psychometrika. 18(1953), 39-43. 10. Brin, S., and Page, L. The anatomy of a large-scale hypertextual web search engine. In proceedings of seventh international World Wide Web conference. Amsterdam, Netherlands,( C 117. 11. Glen Jeh and Jennifer Widom. SimRank: A measure of structural-context similarity. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2002). 12. Holt,C.C. Forecasting seasonals and trends by exponentially weighted moving averages. International Journal of Forecasting, 20(.
更多搜索：
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。}