Using social Trust for Recommender Systems Jennifer golbeck Human-Computer Interaction Lab University of Maryland, College Park How many cows in Texas? W ABDUCTIONS TO DAT 0.527,226 http://www.cowabduction.com
1 Using Social Trust for Recommender Systems Jennifer Golbeck Human-Computer Interaction Lab University of Maryland, College Park 2/39 How many cows in Texas? http://www.cowabduction.com/
facebook LIVEJOURNAL ywO Linked in EzorpIa.com myspace. C 圆■■■■ Xanga mixis >1.0000gye hi5 orkus YAHoOL 360 Adult riendfinderco China8en肉 mULTiPLyOfriendster You Tube
2 3/39 4/39 >1,000,000,000
Introduction a Trust is a way of doing social personalization a Understand how to compute trust a See applications where trust is being Used for creating recommendations 5/39 Defining trust a Overall, trust is very complex Involves personal background, history of interaction, context, similarity, reputation, etc a Sociological definitions a Trust requires a belief and a commitment E.g. Bob believes Frank will provide reliable information thus Bob is willing to act on that information Similar to a bet a In the context of recommender systems, trust is generally used to describe similarity in opInion Ignores authority, correctness on facts
3 5/39 Introduction Trust is a way of doing social personalization Understand how to compute trust See applications where trust is being used for creating recommendations 6/39 Defining Trust Overall, trust is very complex Involves personal background, history of interaction, context, similarity, reputation, etc. Sociological definitions Trust requires a belief and a commitment E.g. Bob believes Frank will provide reliable information thus Bob is willing to act on that information Similar to a bet In the context of recommender systems, trust is generally used to describe similarity in opinion Ignores authority, correctness on facts
Trust inference The Goal: Select two individuals-the source(node a) and sink (node c)-and recommend to the source how much to trust the sink B
4 7/39 8/39 Trust Inference The Goal: Select two individuals - the source (node A) and sink (node C) - and recommend to the source how much to trust the sink. A B C tAB tBC tAC
Major Algorithms-Networks u Advogato(Levien Appleseed(Ziegler and Lausen a MoleTrust(Massa and Avesani TidalTrust(Golbeck) Advogato Attack resistant Maximum network flow based on Ford-Fulkerson Node capacities determined by the distance from the This is a single source, multiple sink problem with capacities on the nodes u Network flow works on a single source single sink problem with capacities on the edges 10/39
5 9/39 Major Algorithms - Networks Advogato (Levien) Appleseed (Ziegler and Lausen) MoleTrust (Massa and Avesani) TidalTrust (Golbeck) 10/39 Advogato Levien 2003 Attack resistant Maximum network flow based on Ford-Fulkerson Node capacities determined by the distance from the source This is a single source, multiple sink problem with capacities on the nodes Network flow works on a single source single sink problem with capacities on the edges The graph is transformed
Supersink Appleseed a Ziegler and Lausen, 2004 Based on spreading activation models Trust is modeled as energy Source node is activated through an injection of energy e is then propagated to other nodes along edges All energy is fully divided among successor nodes wrt their local edge weight. Supposing average out degrees >=1, the closer the sink is to the source, and the more paths leading from the source to the sink, the higher energy flowing to sink a Output: ranking of nodes
6 11/39 A B 9 3 A- A+ B- B+ A- A+ B- B+ Supersink 8 1 2 1 12/39 Appleseed Ziegler and Lausen, 2004 Based on spreading activation models Trust is modeled as energy Source node is activated through an injection of energy e e is then propagated to other nodes along edges All energy is fully divided among successor nodes wrt. their local edge weight. Supposing average out degrees >= 1, the closer the sink is to the source, and the more paths leading from the source to the sink, the higher energy flowing to sink Output: ranking of nodes
Tidaltrust and mole trust If the source does not know the sink the source asks all of its friends how much to trust the sink and computes a trust value by a weighted average Neighbors repeat the process if they do not have a direct rating for the sink tinty j∈ad()|t≥max j∈ad(j)|t≥maa so ource
7 13/39 TidalTrust and MoleTrust If the source does not know the sink, the source asks all of its friends how much to trust the sink, and computes a trust value by a weighted average Neighbors repeat the process if they do not have a direct rating for the sink 14/39 Source Sink
Exercise Simulator with the basics of mole trust and TidalTrust is available online ahttp://zaphod.mindlab.umd.edu/socialtrustc ourse/trustDemo html What about confidence a a if decisions will be based on trust we should know how confident we are in the trust estimate How do we reflect low confidence in an inferred value 2 0.6 A 0.6
8 15/39 Exercise Simulator with the basics of MoleTrust and TidalTrust is available online http://zaphod.mindlab.umd.edu/SocialTrustC ourse/trustDemo.html 16/39 What About Confidence? If decisions will be based on trust, we should know how confident we are in the trust estimate How do we reflect low confidence in an inferred value? A E C F B G 0.9 1 0.6 0.6 0.4 0.1 0.2 1 H D
SUNNY Trust inference algorithm using Bayesian Networks a Trust network is mapped into a Bayes Net a Conditional Probability values are computed through profile similarity measures ■A“ most confident" subnetwork is se| ected and trust inference is performed on that network Result is an inferred trust value and a confidence in that value 7/39 A Note about distrust a It is hard to integrate distrust into a propagation model a If Alice distrusts bob and bob distrusts chuck should alice trust chuck or not 2 a With no clear treatment distrusted individuals could be pruned away, thUs providing little benefit to including distrust
9 17/39 SUNNY Trust inference algorithm using Bayesian Networks Trust network is mapped into a Bayes Net Conditional Probability values are computed through profile similarity measures A “most confident” subnetwork is selected and trust inference is performed on that network Result is an inferred trust value and a confidence in that value 18/39 A Note About Distrust It is hard to integrate distrust into a propagation model If Alice distrusts Bob and Bob distrusts Chuck, should Alice trust Chuck or not? With no clear treatment, “distrusted” individuals could be pruned away, thus providing little benefit to including distrust
Trust from similarity If there is no social network with trust values how do we compute trust? Assuming there are underlying ratings, can we compute trust from similarity How does this differ from collaborative filtering Exercise for the audience 1. Your Favorite movie ★★★★★ 2. Your least favorite movie ★★★★★ 3. Some Mediocre Movie ★★★★★ 4 Some mediocre movie ★★★★★ Some mediocre movie ★★★★★ 6. Some mediocre movie ★★★★ 7. Some mediocre movie ★★★★★ 8. Some mediocre movie ★★★★★ 9. Some mediocre movie ★★★★★ 0. Some mediocre movie ★★★★★ 20/39
10 19/39 Trust from Similarity If there is no social network with trust values, how do we compute trust? Assuming there are underlying ratings, can we compute trust from similarity? How does this differ from collaborative filtering? 20/39 1. Your Favorite Movie ★★★★★ 2. Your Least Favorite Movie ★★★★★ 3. Some Mediocre Movie ★★★★★ 4. Some Mediocre Movie ★★★★★ 5. Some Mediocre Movie ★★★★★ 6. Some Mediocre Movie ★★★★★ 7. Some Mediocre Movie ★★★★★ 8. Some Mediocre Movie ★★★★★ 9. Some Mediocre Movie ★★★★★ 10. Some Mediocre Movie ★★★★★ Exercise for the audience