WWW 2008 / Poster Paper

April 21-25, 2008 ˇ Beijing, China

Towards Robust Trust Establishment in Web-Based Social Networks with SocialTrust
James Caverlee
Dep't of Computer Science Texas A&M University College Station, TX 77843

Ling Liu
College of Computing Georgia Tech Atlanta, GA 30332

Steve Webb
College of Computing Georgia Tech Atlanta, GA 30332

caverlee@cs.tamu.edu ABSTRACT

lingliu@cc.gatech.edu

webb@cc.gatech.edu

We prop ose the SocialTrust framework for tamp er-resilient trust establishment in online social networks. Two of the salient features of SocialTrust are its dynamic revision of trust by (i) distinguishing relationship quality from trust; and (ii) incorp orating a p ersonalized feedback mechanism for adapting as the social network evolves. Categories and Sub ject Descriptors: H.3.5 Information Storage and Retrieval: Online Information Services General Terms: Algorithms, Exp erimentation

social network, meaning users have no assurances over the vast ma jority of all participants in the network. Malicious users can exploit the p erceived social connection b etween users for increasing the probability of disseminating misinformation, of driving participants to the seedy side of the Internet (e.g., to sites hosting malware), and of other disruptions to the quality of community-based knowledge.

2. THE SOCIALTRUST MODEL
With these problems in mind, we present the initial design of SocialTrust, a reputation-based trust aggregation framework for supp orting tamp er-resilient trust establishment in online social networks. The b enefits of reputationbased trust from a user's p ersp ective include the ability to rate neighb ors, a mechanism to reach out to the rest of the community, and some assurances on unknown users. Initially all users are treated equally. SocialTrust supp orts trust maintenance through dynamic revision of trust ratings according to three critical comp onents: the current quality comp onent of trust T rq (i, t), the history comp onent, and the adaptation to change comp onent. The SocialTrust score for user i at time t is defined as: S T (i, t) =  ˇ T rq (i, t) +  ˇ 1 t Z
0 t

1.

INTRODUCTION

Web-based social networking services like the ones offered by MySpace and Faceb ook supp ort the management of social relationships, connecting millions of users. MySpace alone has grown from 1 million user accounts in 2004 to an astonishing 250 million accounts today. This growth has not come without a price, however. The large social networking sites have b een the target of sp ecialized phishing attacks, imp ersonating profiles, spam, targeted malware dissemination, and new threats are certain to emerge as attackers grow in sophistication. While there are imp ortant problems associated with securing the social network infrastructure, we explore vulnerabilities to the quality of information available through online social networks even when the underlying social network infrastructure has b een secured. In particular, we identify three vulnerabilities: ˇ Malicious Infiltration: Most online social networks provide some limits as to who can participate, often requiring a valid email address or a registration form. As a result, many social networks give the illusion of security [1], but malicious participants can still gain access. ˇ Nearby Threats: The small world phenomenon [6] means that there is a short distance in the network b etween any two participants. Even if a user has tight control over his direct friends, malicious users can b e just a few hops away. ˇ Limited Network View: Even if a user in the social network maintains tight control over her friends and closely monitors the quality of her neighb ors' friends, she will still have access to only a limited view of the entire
Copyright is held by the author/owner(s). WWW 2008, April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04.

S T (i, x)dx +  ˇ T rq (i, t)

where T rq (i, t) is the derivative of T rq (i, x) at x = t. This approach is similar to a Prop ortional-Integral-Derivative (PID) controller used in feedback control systems [7]. By tuning ,  , and  , the SocialTrust model can b e optimized along a numb er of dimensions, e.g., (i) to emphasize the most recent b ehavior of a user in the network (via higher values of ); (ii) to de-emphasize the current user's b ehavior in the context of his entire history of b ehavior (via higher values of  ); or (iii) to amplify sudden fluctuations in b ehavior (via higher values of  ). Given the overall SocialTrust approach, what is an appropriate choice of the base trust metric T rq (i, t)? In light of the vulnerabilities previously identified, we suggest that a good base trust metric should incorp orate two key features: 1. Distinguishing Relationship Quality from Trust. Many trust models (e.g., [4, 5]) evaluate the relative trustworthiness of a node (or user, in our case) based on the trustworthiness of all nodes p ointing to it, but make no distinction ab out the relationship (or link) quality of each node. In essence, these approaches make no distinction b etween the trust placed in a user and the trust placed in a user's relationships. Intuitively, we would like to differentiate b etween

1163


WWW 2008 / Poster Paper
users who consistently engage in high-quality relationships with other users versus users who tend to engage in lower quality relationships. 2. Incorporating Personalized User Feedback. Second, trust models based solely on network top ology are divorced from the underlying b ehavior of the users in the network. Relationships in the online social network provide the basis for trust aggregation, but there is no feedback mechanism for dynamically up dating the quality of the trust assessments based on how well each user in the network b ehaves. Hence, we are interested in "closing the loop" so that the trust assessments may b e dynamically up dated as the social network evolves and as the quality of each user (with resp ect to user feedback) changes over time. Based on these observations, SocialTrust assesses user i's trust rating T rq (i) according to the user's relationship link quality L(i) and her feedback rating F (i) through a recursive formulation: T rq (i) =  X
j r el(i)

April 21-25, 2008 ˇ Beijing, China

Figure 1: Comparing trust models line social networks. We consider a PageRank-based trust model that considers only the relationship structure of the social network; a TrustRank-based model that uses feedback ratings as a priori trust (which is equivalent to EigenTrust from the P2P domain); a preliminary SocialTrust [Cred Only] model that incorp orates relationship link quality only but no feedback ratings (which is similar in spirit to credibility-based link analysis explored in the Web domain [2]); and the final SocialTrust model. When a prop ortion of highly-trusted users b ehave maliciously, PageRank and TrustRank have no mechanism for correcting this bad b ehavior. In contrast, the SocialTrust model incorp orates link quality and feedback ratings into the trust assessment so that bad b ehavior is punished, and so the resulting precision measures are resilient to the presence of a large fraction of malicious users in the network. These initial results are encouraging, and we working to further explore the key prop erties impacting SocialTrust.

L(j ) ˇ T rq (j )/|r el(j )| + (1 - )F (i)

where |r el(i)| is the total numb er of relationships i participates in and  is a tunable mixing parameter. The intuition is that a user's trustworthiness should b e determined by b oth: (i) the numb er and trustworthiness of the users who recommend her (via relationships in the social network); and (ii) the relationship link quality of each recommending user. In this way, a recommendation from a high-trust/high-linkquality user counts more than a recommendation from a high-trust/low-link-quality user. The feedback rating F (i) favors users who have b een rated highly by other users, according to the mixing factor 1 - .

3.

PRELIMINARY EVALUATION

We have evaluated SocialTrust in a simulation over a directed graph consisting of 5,199,886 nodes and 19,145,842 relationship links that we harvested from MySpace. We refer the interested reader to [3] for more discussion of the simulation setup and how link quality and feedback are computed. We consider a scenario in which an originating user has an information need (e.g., looking for a job in Texas, finding a good restaurant) for which she can use her social network. The basic scenario is this: a user browses her relationships up to some radius looking for candidate users to ask; based on an analysis of their profiles, she constructs a set of candidate users who might satisfy her information need; based on the provided trust ratings, she selects the top-k most trusted candidate users; she asks all top-k; if she is satisfied, she provides p ositive feedback to the trust manager; otherwise, she provides negative feedback. We model two typ es of users: (i) malicious users, who always provide an irrelevant resp onse when asked; and (ii) legitimate users, who sometimes accidentally provide an irrelevant resp onse when asked. For a query q , let R+ denote the set of relevant users for q throughout the entire space of users and let Rn denote the n top-ranked candidate users (by trust value). We measure a focused version of the standard precision measure that considers the quality of the resp onses in the top-n (the + | relative precision @ n): pr ecn = m|iR (|Rn n) . n Rn | , In Figure 1, we compare SocialTrust to several related trust models adapted from the Web and P2P domain to on-

4. CONTINUING WORK
In our future work, we are interested in developing contextaware extensions of SocialTrust so that the network may supp ort multiple trust views of each user dep ending on the context. We also see opp ortunities to augment the evaluation of relationship link quality, so that it considers more sophisticated features like the nature, duration, and value of each relationship. On the implementation side, we continue work on a SocialTrust-p owered community platform that can b e layered on top of existing social networks.

5. REFERENCES
[1] S. B. Barnes. A privacy paradox: So cial networking in the United States. First Monday, 11(9), Septemb er 2006. [2] J. Caverlee and L. Liu. Countering Web spam with credibility-based link analysis. In PODC, 2007. [3] J. Caverlee, L. Liu, and S. Webb. So cialTrust: Tamp er-resilient trust establishment in online communities. Technical rep ort, Texas A&M University, 2008. [4] Z. Gy¨ngyi, H. Garcia-Molina, and J. Pedersen. Combating o Web spam with TrustRank. In VLDB, 2004. [5] S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The EigenTrust algorithm for reputation management in P2P networks. In WWW, 2003. [6] S. Milgram. The small-world problem. Psychology Today, pages 60 ­ 67, May 1967. [7] M. Srivatsa, L. Xiong, and L. Liu. TrustGuard: Countering vulnerabilities in reputation management for decentralized overlay networks. In WWW, 2005.

1164