Trust Algorithms in Social Networks Analysis
"Explore various algorithms for determining trust among friends on social networks, including direct trust, tidal trust, and mole trust algorithms. Discover the sociology, psychology, and computer science aspects of trust in social networks."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
MASTER THESIS num. 802 ANALYSIS OF ALGORITHMS FOR DETERMINING TRUST AMONG FRIENDS ON SOCIAL NETWORKS Mirjam itum Ao. Univ. Prof. Dr. Dieter Merkl Univ. Ass. Mag. Julia Neidhardt Doc. Dr. Sc. Vedran Podobnik
Content Introduction Trust Implemented algorithms Application Evaluation Results
Introduction Recommendation systems Social networks = information Relations between users
Trust Sociology Psychology Computer science Hard definition Depends on the goal Direct trust Peer-to-peer trust
Trust Trust can have these properties: Context specific Dynamic Propagative Aggregative Asymetric
Trust Implemented algorithms: Direct trust algorithm Direct normalized trust algorithm Tidal trust algorithm Mole trust algorithm Eigen trust algorithm
Direct trust algorithm Interactions(I) Weights ?1 Friend likes post made by user ?2 Friend comments on post made by user ?3 Friend is tagged in post made by user ?4 Friend commented on a photo of user ?5 Friend liked photo of user ?6 Friend is tagged in photo of user ????? ??? ????,??????? = ? ?? ? ?? ? ???
Direct trust normalization Number of one type of friend x s interaction with user Variation of direct algorithm ?(?) ??(?) = Total number of interactions i of all user s friends ? ??(?) ????? ??? ????,??????? = ? ??? ? ?? ? ???
Tidal trust algorithm Sink Uses network built by direct trust algorithm Uses shortest paths to the sink Favors higher trust values Threshold =9 6 8 9 9 8 10 9 9 10 10 9 8 8 6 7 9 8 10 6.95 Source
Mole trust algorithm Similar to tidal trust Differences: Doesn t stop when sink is found Stops at depth d Treshold = 60% of highest trust value towards the sink
Eigen trust algorithm 0.5 0.2 + 0.3 0.4 0.5 = ?.?? Uses network built by direct normalized trust algorithm Trust values [0,1] 0.2 0.5 0.6 0.5 0.4 0.3 Sink 0.2 0.5 0.2 0.8 0.3 Source
Application Web & Facebook Application Developed in PHP 3 main functionalities: Collecting & storing user data from Facebook Computing trust Survey
Application Content 1. Part 5 questions o Best friends on Facebook o Best Friends in real life o Music recommendation o Watching over pet o Travel companion 2. Part User rates algorithm results
2 Steps in the research 1. Step - Calibration of weights in direct algorithm o 100 users o 1 question 2. Step Evaluation of algorithms o 104 users o 5 questions + ratings
Measures for algorithm evaluation 1. Kendal Tau Distance user 1. list indexes 2. list indexes A 1 3 B 2 4 C 3 1 D 4 2 E 5 5 Pair (A,B) (A,C) (A,D) (A,E) (B,C) (B.D) (B,E) (C,D) (C,E) (D,E) First list 1 < 2 1 < 3 1 < 4 1 < 5 2 < 3 2 < 4 2 < 5 3 < 4 3 < 5 4 < 5 indexes Second list 3 < 4 3 > 1 3 > 2 3 < 5 4 > 1 4 > 2 4 < 5 1 < 2 1 < 5 2 < 5 indexes Count - X X - X X - - - -
Measures for algorithm evaluation 2. Rank Difference Friends User Perception Ranking Algorithm Ranking Difference A 1 53 52 B 2 8 6 C 3 1 2 D 4 15 11 E 5 3 2 Total Difference = 73
Measures for algorithm evaluation 3. Exact (Match) Count Friend User Perception Ranking Algorithm Ranking A 1 20 B 2 2 C 3 5 D 4 15 E 5 3 Match Count = 3 Exact Match Count = 1
Calibrating the weights 100 users chose top 5 friends from real life combination of weight values from 1 to 20, step 0.5 for every combination -> average rank difference per user was calculated weight combination with lowest average rank difference was chosen Weight Description Value W1 Likes on user posts 2.5 W2 Comments on user posts 5 W3 Tags on user posts 10.5 W4 Likes on user photos 1 W5 Comments on user photos 12 W6 Tags on user photos 2
Statistics 100 users 1. part for calibration 104 users filled survey 215 users in the database 108 users female 107 users male 83864 friendships (42403 have direct trust value) 34656 photos, 71806 comments, 186827 likes , 111777 tags 62747 posts, 46873 comments, 158183 likes and 3618 tags
Evaluation Algorithms: Direct Normalized Direct Tidal Mole Eigen Combinations: Direct + Mole Direct +Tidal Norm. Direct + Eigen Measures: Kendal Tau Distance Rank Difference Match Count Direct Match Count
Results First question: chose top 5 friends from real life Direct algorithms - more precise Eigen trust highest number of big mistakes Eigen trust + weighted direct combination almost precise as direct = interesting for future research 60 50 40 30 20 Rank Difference Rank Difference Filtered 10 0
Results First question: chose top 5 friends from real life 5 Peer-to-peer algorithms - better ordering of top 5 friends Less precise because of sparse network Can be used when No direct connection between nodes In combination with direct algorithms for more information Direct algorithms average top 5 guess: more than 40% 4.5 4 3.5 3 2.5 2 1.5 Kendal Tau Distance 1 0.5 0 2.5 2 1.5 1 Match Count 0.5 Exact Count 0
Results For rest of questions: 2nd question: best friends from Facebook Three context questions Similar results between algorithms Worse results than for first question, for all algorithms Weights calibrated for first question
Results Direct algorithm Questions including interaction and socialization better results Questions including recommendation, reliance and credence worse results Similar results for normalized version 2.5 35 30 2 25 1.5 Rank difference 20 Match Count 1 Exact Count 15 Rank Difference Filtered 10 0.5 5 0 0 1 2 3 4 5 1 2 3 4 5
Results Peer-to-peer algorithms Hard to say which algorithms best for which context Every algorithm has similar results for every question Eigen most precise with question about friends to go with on a trip Mole and Tidal most precise with question about music recommendation
Results 4 algorithm results shown to user Users graded algorithms Grades from 1-5 Average grade for sentence Your best friends from real life Average grade for sentence Your best friends from Facebook Algorithm 3.2885 3.3269 Direct trust algorithm Combination of Mole trust and direct trust algorithm 2.5384 2.6731 Combination of Tidal trust and direct trust algorithm 2.6154 2.5962 Combination of Eigen trust and norm. Direct trust algorithm 3.5096 3.3846
Results Last part of the survey Users feedback on algorithms Mostly friends from school/college Direct algorithm -> 35 users said: friends from school/college Trust computed from user interactions =>interactions in real life are translated to the social network setting People transfer socialization from real life to social networks
Conclusion Direct trust algorithms show better result Normalized direct algorithm was better variant Peer-to-peer algorithms: were less precise due to sparse network showed better ordering for top 5 friends Weakness: sparse network, Advantage: direct user feedback People have need to transfer real life socializing to social networks Future work: Test peer-to-peer algorithms with less sparse networks Research ways of algorithm combination
