Computing Trust in Social NetworksWeb-Based Social Networks (WBSNs)Using WBSNsApplications of TrustResearch AreasInferring TrustMethodsPowerPoint PresentationTrust AlgorithmAccuracyTrust from SimilarityExperimental OutlineGenerating ProfilesExample ProfileResultsExtreme RatingsMaximum Difference (r)Propensity to Trust ()ValidationIn FilmTrustEffect of changeSlide 22Algorithms ConsideredInitial ideas?NetworkMethodologyFraction of Nodes at a Given Distance Whose Inferred Trust Value for the Sink ChangedSlide 28Average Magnitude of Change at a Given DistanceConclusions and Future DirectionsConclusionsFuture Work - Computing with TrustFuture Work - ApplicationsSlide 34Computing Trust in Social NetworksJennifer GolbeckCollege of Information StudiesWeb-Based Social Networks (WBSNs)•Websites and interfaces that let people maintain browsable lists of friends•Last count–245 social networking websites–Over 850,000,000 accounts–Full list at http://trust.mindswap.orgUsing WBSNs•Lots of users, spending lots of time creating public information about their preferences•We should be able to use that to build better applications•When I want a recommendation, who do I ask?–The people I trustApplications of Trust•With direct knowledge or a recommendation about how much to trust people, this value can be used as a filter in many applications•Since social networks are so prominent on the web, it is a public, accessible data source for determining the quality of annotations and informationResearch Areas•Inferring Trust Relationships•Using Trust in ApplicationsInferring TrustThe 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 CtABtBCtACMethods•TidalTrust–Personalized trust inference algorithm•SUNNY–Bayes Network algorithm that computes trust inferences and a confidence interval on the inferred value. •Profile Based–Trust from similaritySourceSinkTrust Algorithm•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 sinkAccuracy•Comparison to other algorithms –Beth-Borcherding-Klein (BBK) 1994AlgorithmNetworkTidalTrustBBKTrust Project1.09 (.99)1.59 (1.42)FilmTrust1.35 (1.23)2.75 (1.80)Trust from Similarity•We know trust correlates with overall similarity (Ziegler and Golbeck, 2006)•Does trust capture more than just overall agreement? •Two Part Analysis–Controlled study to find profile similarity measures that relate to trust–Verification through application in a live systemExperimental Outline•Phase 1: Rate Movies - Subjects rate movies on the list–Ratings grouped as extreme (1,2,9,10) or far from average (≥4 different)•Create profiles of hypothetical users –Profile is a list of movies and the hypothetical user’s ratings of them•Subjects rate how much they would trust the person represented by the profile–Vary the profile’s ratings in a controlled wayGenerating Profiles•Each profile contained exactly 10 movies, 4 from an experimental category and 6 from its complement–E.g. 4 movies with extreme ratings and 6 with non-extreme ratings•Control for average difference, standard deviation, etc. so we could see how differences on specific categories of films affected trustExample Profile•Movies m1 through m10•User ratings r1…r10 for m1…m10 –r1…r4 are extreme (1,2,9, or 10)–r5…r10 are not extreme •Profile ratings pi = ri§ iResults1. Reconfirmed that trust strongly correlates with overall similarity ().2. Agreement on extremes ()3. Largest single difference (r)4. Subject’s propensity to trust ()•When high are used on movies with extreme ratings, the trust ratings are significantly lower than when low are applied to those films•Statistically significant for all iExtreme RatingsMaximum Difference (r)•Holding overall agreement and standard deviation constant, trust decreased as the single largest difference between the profile and the subject (r) increased.Propensity to Trust ()Validation•Gather all pairs of FilmTrust users who have a known trust relationship and share movies in common –322 total user pairs•Develop a formula using the experimental parameters to estimate trust•Compute accuracy by comparing computed trust value with known valueIn FilmTrustUse weights (w1,w2, w3, w4, w5) = (7,2,1,8,2)Overall Similarity OnlyOur FormulaCorrelation0.240.73Absolute Mean Error1.911.13Std. Dev of Mean Error1.950.95Effect of change•If a node changes it’s trust value for another, that will propagate through the inferred values•How far? What is the magnitude? Does the impact increase or decrease with distance?•How does this relate to the algorithm?•Joint work with Ugur KuterAlgorithms Considered•Eigentrust–Global algorithm–Like PageRank, but with weighted edges•Advogato–Finds paths through the network–Global group trust metric that uses a set of authoritative nodes to decide how trustworthy a person is•TidalTrust•TidalTrust++–No minimum distance - search the entire networkInitial ideas?•The further you get from the sink, the smaller the impact. •Changes by more central, highly connected nodes will create a bigger impact.NetworkMethodology•Pick a pair of nodes in the network–Set trust to 0–Infer trust values between all pairs–Set trust to 1–Infer trust value between all pairs–Compare inferred values from trust=0 to trust=1•Repeat for every pair•Repeat for each algorithmFraction of Nodes at a Given Distance Whose Inferred Trust Value for the Sink ChangedSourceSinkAverage Magnitude of Change at a Given DistanceConclusions andFuture DirectionsConclusions•Trust is an important relationship in social networks. •Social relationships are different than other common data used in CS research.•Trust can be computed in a variety of ways•The type of algorithm and behavior of users in the network impact the stability of trust inferencesFuture Work - Computing with Trust•Major categories of trust inference: global vs. local, same scale vs. new scale–All have algorithms•Additional features (like confidence)•Hybrid approaches –Use trust assigned by users and similarity–Use multiple relationships for better certainty in certain domains (e.g. authority)Future Work - Applications•What
View Full Document
Unlocking...