ABSTRACT Title of dissertation: COMPUTING AND APPLYING TRUST IN WEB-BASED SOCIAL NET WORKS Jennifer Ann Golbeck, Doctor of Philosophy, 2005 Dissertation directed by Professor James hendler Department of Computer Science The proliferation of web-based social networks has lead to new innovations in social networking, particularly by allowing users to describe their relationships beyond a basic connection. In this dissertation, I look specifically at trust in web-based social networks, how it can be computed, and how it can be used in applications. I begin with a definition of trust and a description of several properties that affect how it is used in algorithms. This is complemented by a survey of web-based social networks to gain an understanding of their scope, the types of relationship information available, and the current state of trust The computational problem of trust is to determine how much one person in the network should trust another person to whom they are not connected. I present two sets of algorithms for calculating these trust inferences: one for networks with binary trust ratings, and one for continuous ratings. For each rating scheme the algorithms are built upon the defined notions of trust. Each is then analyzed theoretically and with respect to
ABSTRACT Title of dissertation: COMPUTING AND APPLYING TRUST IN WEB-BASED SOCIAL NETWORKS Jennifer Ann Golbeck, Doctor of Philosophy, 2005 Dissertation directed by: Professor James Hendler Department of Computer Science The proliferation of web-based social networks has lead to new innovations in social networking, particularly by allowing users to describe their relationships beyond a basic connection. In this dissertation, I look specifically at trust in web-based social networks, how it can be computed, and how it can be used in applications. I begin with a definition of trust and a description of several properties that affect how it is used in algorithms. This is complemented by a survey of web-based social networks to gain an understanding of their scope, the types of relationship information available, and the current state of trust. The computational problem of trust is to determine how much one person in the network should trust another person to whom they are not connected. I present two sets of algorithms for calculating these trust inferences: one for networks with binary trust ratings, and one for continuous ratings. For each rating scheme, the algorithms are built upon the defined notions of trust. Each is then analyzed theoretically and with respect to
simulated and actual trust networks to determine how accurately they calculate the opinions of people in the system. I show that in both rating schemes the algorithms presented can be expected to be quite accurate These calculations are then put to use in two applications. FilmTrust is a website that combines trust, social networks, and movie ratings and reviews. Trust is used to personalize the website for each user, displaying recommended movie ratings, and ordering reviews by relevance. I show that, in the case where the user's opinion divergent from the average. the trust-based recommended ratings are more accurate than several other common collaborative filtering techniques. The second application is TrustMail, an email client that uses the trust rating of each sender as a score for the Users can then sort me s according to their trust value I conclude with a description of other applications where trust inferences can be used, and how the lessons from this dissertation can be applied to infer information about relationships in other complex systems
simulated and actual trust networks to determine how accurately they calculate the opinions of people in the system. I show that in both rating schemes the algorithms presented can be expected to be quite accurate. These calculations are then put to use in two applications. FilmTrust is a website that combines trust, social networks, and movie ratings and reviews. Trust is used to personalize the website for each user, displaying recommended movie ratings, and ordering reviews by relevance. I show that, in the case where the user's opinion is divergent from the average, the trust-based recommended ratings are more accurate than several other common collaborative filtering techniques. The second application is TrustMail, an email client that uses the trust rating of each sender as a score for the message. Users can then sort messages according to their trust value. I conclude with a description of other applications where trust inferences can be used, and how the lessons from this dissertation can be applied to infer information about relationships in other complex systems
COMPUTING AND APPLY ING TRUST IN WEB-BASED SOCIAL NETWORKS b Jennifer Ann Golbeck Dissertation Submitted to the Faculty of the graduate School of th University of Maryland, College Park in partial fulfillment of the requirements for the degree of Doctor of Philosophy Advisory Committee Professor James Hendler, Chair/Advisor Professor ashok agrawala Professor mark austin Professor BenjamI Professor Lise getoor Professor Ben shneiderman
COMPUTING AND APPLYING TRUST IN WEB-BASED SOCIAL NETWORKS by Jennifer Ann Golbeck Dissertation Submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2005 Advisory Committee: Professor James Hendler, Chair/Advisor Professor Ashok Agrawala Professor Mark Austin Professor Benjamin Bederson Professor Lise Getoor Professor Ben Shneiderman
COpyright by Jennifer Ann golbeck 2005
©Copyright by Jennifer Ann Golbeck 2005
To my parents
ii To my parents
ACKNOWLEDGEMENTS First, I would like to thank James Hendler, my advisor. He gave me grea intellectual freedom to pursue my interests and provided encouragement and guidance hroughout this works lifetime. Thanks also to my committee for their challenges, assistance, and support: Ben Bederson, Ben Shneiderman, Ashok Agrawala, Lise Getoor, and mark austin I received what seemed like endless help from members of MINdS WAP in many capacities. Thanks to Y arden Katz, Mike Grove, Aditya Kalyanpur, Evren Sirin, Ron Alford, Amy Alford, Debbie Heisler. Aaron Mannes, Denise Cross, and others I may have forgotten. Thanks also to the FOAF community for their support and participation Many colleagues around the world have helped me develop this work into what it is now. Thanks to Cai-Nicolas Ziegler. Paolo massa. Matthew Richardson morten Frederiksen, Chris Bizer, and Sep Kamvar. Thanks also to Stuart Kurtz, my former advisor at the University of Chicago, who helped set me on my way toward this goal My family, of course, has been very supportive and encouraging. Thanks to brother Tom golbeck and his wife and my friend Michelle, Jeanne Mitchell, and the rest of my large Catholic family who would require several pages to be fully enumerated. As always, bones to t and k who were present throughout the dissertation process Of course, a very special thanks to my husband, Dan Golbeck. He has endless wells of patience and support, and always knows the right moment to tell me that I'm
iii ACKNOWLEDGEMENTS First, I would like to thank James Hendler, my advisor. He gave me great intellectual freedom to pursue my interests and provided encouragement and guidance throughout this work’s lifetime. Thanks also to my committee for their challenges, assistance, and support: Ben Bederson, Ben Shneiderman, Ashok Agrawala, Lise Getoor, and Mark Austin. I received what seemed like endless help from members of MINDSWAP in many capacities. Thanks to Yarden Katz, Mike Grove, Aditya Kalyanpur, Evren Sirin, Ron Alford, Amy Alford, Debbie Heisler. Aaron Mannes, Denise Cross, and others I may have forgotten. Thanks also to the FOAF community for their support and participation. Many colleagues around the world have helped me develop this work into what it is now. Thanks to Cai-Nicolas Ziegler, Paolo Massa, Matthew Richardson, Morten Frederiksen, Chris Bizer, and Sep Kamvar. Thanks also to Stuart Kurtz, my former advisor at the University of Chicago, who helped set me on my way toward this goal. My family, of course, has been very supportive and encouraging. Thanks to brother Tom Golbeck and his wife and my friend Michelle, Jeanne Mitchell, and the rest of my large Catholic family who would require several pages to be fully enumerated. As always, bones to π and K who were present throughout the dissertation process. Of course, a very special thanks to my husband, Dan Golbeck. He has endless wells of patience and support, and always knows the right moment to tell me that I'm
brilliant so I'll keep going. He deserves some sort of degree for putting up with me while I completed this dissertation Finally, thanks to Irene and John Golbeck, my mom and dad. They have encouraged me every step of my life to be a strong, independent thinker, to work hard, and to keep trying at difficult things. I inherited a different kind of insanity from each of them, and the combination has served me well through all my years of education. I am eternally grateful to them for all the opportunities they made available to me, and for the support they have given me along the way
iv brilliant so I'll keep going. He deserves some sort of degree for putting up with me while I completed this dissertation. Finally, thanks to Irene and John Golbeck, my mom and dad. They have encouraged me every step of my life to be a strong, independent thinker, to work hard, and to keep trying at difficult things. I inherited a different kind of insanity from each of them, and the combination has served me well through all my years of education. I am eternally grateful to them for all the opportunities they made available to me, and for the support they have given me along the way
TABLE OF CONTENTS List of Tables List of Figures 1 Introduction 1.1 Contributions 1.2 Organization 5 2 Web-Based Social Networks 2.1 Introduction 10 2.2 Previous Work 2.3 Definitions 2.4 A Survey of Web-Based Social Networks 2. 4.1 Size 2.4.2 Cate gorization 2.4.3 Relationship Data 19 2. 5 The Semantic Web and Friend of a Friend(FoaF) 2.5.1 Background 23 2.5.2 FOAF and Current WBSNs 2.5.3 Extensions to FoaF 2.6 Conclusions and Future directions
v TABLE OF CONTENTS List of Tables List of Figures 1 Introduction 1.1 Contributions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Web-Based Social Networks 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Previous Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 A Survey of Web-Based Social Networks. . . . . . . . . . . . . . . . . . . . . . 2.4.1 Size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Categorization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.3 Relationship Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 The Semantic Web and Friend of a Friend (FOAF). . . . . . . . . . . . . . . 2.5.1 Background. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 FOAF and Current WBSNs. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.3 Extensions to FOAF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Conclusions and Future Directions. . . . . . . . . . . . . . . . . . . . . . . . . . . . ix x 1 4 5 10 10 11 12 15 16 17 19 22 23 26 27 28
3 Trust: Definition and propertie 3.1 A Definition of trust 31 3.2 Properties of 3.2.1 Transitivity 3.2.2 Composability Personalization and Asymmetry 3. 3 The Values of trust 3. 4 Conclusions 42 4 Inferring Trust: Background and Related work 4. 1 From Trust Properties to Trust Algorithms 4.2 Previous Work 4.2. 1 Game Theory 4.2.2 Peer-To-Peer Systems 4.2.3 Calculating Trust on the web 4.2.4 Public Key infrastructure 4.3 Conclusions 5 Inferring Trust in Binary Networks 5.1 Generating Social Networks 5.1.1 Building Networks with Correct Topology 5.1.2 Adding trust Ratings to graphs 5.2 Making trust Inferences 5.2.1 A Rounding algorithm 5.2.2 A Non-Rounding algorithm 61
vi 3 Trust: Definition and Properties 3.1 A Definition of Trust. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Properties of Trust. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Transitivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Composability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Personalization and Asymmetry. . . . . . . . . . . . . . . . . . . . . . . . . 3.3 The Values of Trust. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Inferring Trust: Background and Related Work 4.1 From Trust Properties to Trust Algorithms . . . . . . . . . . . . . . . . . . . . . 4.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Peer-To-Peer Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Calculating Trust on the Web. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.4 Public Key Infrastructure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Inferring Trust in Binary Networks 5.1 Generating Social Networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Building Networks with Correct Topology. . . . . . . . . . . . . . . . 5.1.2 Adding Trust Ratings to Graphs. . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Making Trust Inferences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 A Rounding Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 A Non-Rounding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 31 34 34 36 38 40 42 43 43 46 47 49 51 54 55 56 57 58 58 59 60 61
5.2.3 Analysis of the algorithms 5.2 4 Simulations 65 5.3 Conclusions 6 Inferring Trust in Continuous Networks: TidalTrust 6. 1 Experimental Networks 6.2 Patterns of trust values 75 6.2.1 Distribution of trust values 6.2.2 Correlation of Trust and Accuracy 77 6.2.3 Path Length and Accuracy. 6. 3 TidalTrust: An algorithm for inferring trust 6.3.1 Incorporating Path Lengt 6.3.2 Incorporating Trust 6.3. 3 Full Algorithm for Inferring Trust 101 6. 4 Accuracy of TidalTrust 107 6. 4.1 Discussion of Trust and Accuracy 107 6. 4.2 Related algorithms l10 6.5 Conclusions l11 7 Trust Inferences in Application: Film Trust 7.1 Related Work 17 7.2 The FilmTrust Website 7. 3 Site Personalization 123 7.3.1 Recommended Movie Ratings 123 132
vii 5.2.3 Analysis of the Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Inferring Trust in Continuous Networks: TidalTrust 6.1 Experimental Networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Patterns of Trust Values. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Distribution of Trust Values. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Correlation of Trust and Accuracy. . . . . . . . . . . . . . . . . . . . . . . 6.2.3 Path Length and Accuracy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 TidalTrust: An Algorithm for Inferring Trust. . . . . . . . . . . . . . . . . . . . 6.3.1 Incorporating Path Length. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Incorporating Trust. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 Full Algorithm for Inferring Trust. . . . . . . . . . . . . . . . . . . . . . . 6.4 Accuracy of TidalTrust . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.1 Discussion of Trust and Accuracy. . . . . . . . . . . . . . . . . . . . . . . 6.4.2 Related Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Trust Inferences in Application: FilmTrust 7.1 Related Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 The FilmTrust Website. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Site Personalization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Recommended Movie Ratings. . . . . . . . . . . . . . . . . . . . . . . . . . . 61 65 70 71 72 75 76 77 86 96 96 97 101 107 107 110 111 116 117 119 123 123 132