Chapter 1 The vast public interest in social networks has opened up many new spaces of possible research in computing. This research adopts web-based social networks as the foundation for studying trust. The goal of this work is twofold First, find ways to utilize the structure of social networks and the trust relationships within them to accurately infer how much two people that are not directly connected might trust one another, and second show how those trust inferences can be integrated into applications. The ultimate goal is to create software that is intelligent with respect to the user's social preferences such that the user's experience is personalized, and the information presented to them is more use Tens of millions of users participate in web-based social networking. The web based nature of these networks means that the data is publicly available; the websites that are taking advantage of semantic Web technologies such as foaf have even taken this a step further, making the social network information easily available to any system that
1 Chapter 1 Introduction The vast public interest in social networks has opened up many new spaces of possible research in computing. This research adopts web-based social networks as the foundation for studying trust. The goal of this work is twofold: First, find ways to utilize the structure of social networks and the trust relationships within them to accurately infer how much two people that are not directly connected might trust one another, and second, show how those trust inferences can be integrated into applications. The ultimate goal is to create software that is intelligent with respect to the user's social preferences such that the user's experience is personalized, and the information presented to them is more useful. Tens of millions of users participate in web-based social networking. The webbased nature of these networks means that the data is publicly available; the websites that are taking advantage of Semantic Web technologies, such as FOAF, have even taken this a step further, making the social network information easily available to any system that
wants to incorporate it. Similarly, the role of social trust in computing is becoming a prominent topic for research on the Semantic Web, within human-computer interaction and in the larger computing community as a whole In this work. i look at instances where trust is integrated into a social network The first step to facilitate that integration is to have a definition of trust that captures the social features while being narrow enough to function in the environment of a social network. Given two people, Alice and Bob, I define trust as follows: Alice trusts Bob if she commits to an action based on a belief that Bob's future actions will lead to a good outcome. From that definition, functional properties of trust can be extracted, including transitivity, composability, asymmetry, and personalization This definition has allowed for the development of two naturally-evolved trust networks that are used in this research. The first has nearly 2, 000 members and is entirely based on the semantic web. Using an ontology I created to extend the friend of a Friend (FOAF) vocabulary, the network is created by spidering files on the semantic web and building a centralized model The second network is also available on the semantic web but has a more typical web-based social network structure, with user accounts and a central website. This trust network backs the filmTrust website. and has over 300 members Using these foundations of trust in web-based social networks and real networks as testbeds, I move toward inferring trust within the network. If two individuals are not directly connected, a trust inference uses the paths that connect them in the social network, and the trust values along those paths, to come up with a recommendation about how much one person might trust the other. I present al gorithms for inferring trust in
2 wants to incorporate it. Similarly, the role of social trust in computing is becoming a prominent topic for research on the Semantic Web, within human-computer interaction, and in the larger computing community as a whole. In this work, I look at instances where trust is integrated into a social network. The first step to facilitate that integration is to have a definition of trust that captures the social features while being narrow enough to function in the environment of a social network. Given two people, Alice and Bob, I define trust as follows: Alice trusts Bob if she commits to an action based on a belief that Bob's future actions will lead to a good outcome. From that definition, functional properties of trust can be extracted, including transitivity, composability, asymmetry, and personalization. This definition has allowed for the development of two naturally-evolved trust networks that are used in this research. The first has nearly 2,000 members and is entirely based on the semantic web. Using an ontology I created to extend the Friend of a Friend (FOAF) vocabulary, the network is created by spidering files on the semantic web and building a centralized model. The second network is also available on the semantic web, but has a more typical web-based social network structure, with user accounts and a central website. This trust network backs the FilmTrust website, and has over 300 members. Using these foundations of trust in web-based social networks, and real networks as testbeds, I move toward inferring trust within the network. If two individuals are not directly connected, a trust inference uses the paths that connect them in the social network, and the trust values along those paths, to come up with a recommendation about how much one person might trust the other. I present algorithms for inferring trust in
networks where trust is assigned on a binary scale, and when it uses a continuous range of values. In both cases, I show that trust can be inferred quite accurately The natural question that follows regards how the inferred trust values can be used. I demonstrate this, and their benefit, through two applications. The first is FilmTrust, a web-based social network that is integrated into a movie rating and reviews website. The trust values are used to personalize the user experience. Reviews are ordered according to the trustworthiness of the author as calculated from the users perspective. Trust values are also used to create personalized recommended movie ratings for the user. When the user looks at a specific movie, they are shown the overall average rating, as well as the recommended rating calculated using trust values as weights. I show that when the user's opinion is divergent from the average opinion, that the trust-based recommendations significantly outperform both the average rating and the ratings generated by traditional collaborative filtering algorithms. The second application to use trust values is TrustMail, and email client that displays the trust rating of the sender next to each message. Users can sort their inboxes according to the trustworthiness of the sender, with the goal of identifying useful and important messages that might otherwise be missed The contributions of this work are relevant within the space of trust and social networks, but also as a general technique within complex systems. The anal ysis of the type of network and functional properties of the relationship(trust in this case)is what lead to algorithms for inferring indirect relationships in the system. That same type of analysis can be used to develop algorithms for other complex systems. I envision carrying this work into other spaces to show this connection. One project where i have already
3 networks where trust is assigned on a binary scale, and when it uses a continuous range of values. In both cases, I show that trust can be inferred quite accurately. The natural question that follows regards how the inferred trust values can be used. I demonstrate this, and their benefit, through two applications. The first is FilmTrust, a web-based social network that is integrated into a movie rating and reviews website. The trust values are used to personalize the user experience. Reviews are ordered according to the trustworthiness of the author, as calculated from the users perspective. Trust values are also used to create personalized recommended movie ratings for the user. When the user looks at a specific movie, they are shown the overall average rating, as well as the recommended rating calculated using trust values as weights. I show that when the user's opinion is divergent from the average opinion, that the trust-based recommendations significantly outperform both the average rating and the ratings generated by traditional collaborative filtering algorithms. The second application to use trust values is TrustMail, and email client that displays the trust rating of the sender next to each message. Users can sort their inboxes according to the trustworthiness of the sender, with the goal of identifying useful and important messages that might otherwise be missed. The contributions of this work are relevant within the space of trust and social networks, but also as a general technique within complex systems. The analysis of the type of network and functional properties of the relationship (trust in this case) is what lead to algorithms for inferring indirect relationships in the system. That same type of analysis can be used to develop algorithms for other complex systems. I envision carrying this work into other spaces to show this connection. One project where I have already
begun this work is with food webs, an ecological network illustrating which species eat which species in an ecosystem. The same sort of analysis used for trust can be applied here, utilizing phylogenic, taxonomic, and known trophic relationships to infer possible trophic links that have not been observed. The promise of such techniques is to help the users of a system- be it web users reviewing movies, or scientists interacting with their own specific system-to better understand a layer of the complexity and thus help them make more informed and better decisions l. Contributions The main focus of this dissertation is to illustrate how an analysis of the trust relationships in web-based social networks can lead to methods for inferrin relationships, and that those inferred values, when integrated into applications, can nhance the user experience My contributions can benefit research in online communities, the semantic web recommender systems,and complex systems analysis. Through this work I have shown hat using inferred trust relationships in web-based social networks offers some real benefits to the user. In order to accomplish this: I present a formalization of trust as a computational concept within web-based social networks, by presenting a definition and describing the functional properties of trust that follow from the definition I present a set of algorithms for inferring trust relationships in social networks that are shown to be quite accurate I show that using trust inferences to make predictive recommendations can offer significant improvements when the user's opinion is divergent from the average
4 begun this work is with food webs, an ecological network illustrating which species eat which species in an ecosystem. The same sort of analysis used for trust can be applied there, utilizing phylogenic, taxonomic, and known trophic relationships to infer possible trophic links that have not been observed. The promise of such techniques is to help the users of a system – be it web users reviewing movies, or scientists interacting with their own specific system – to better understand a layer of the complexity and thus help them make more informed and better decisions. 1.1 Contributions The main focus of this dissertation is to illustrate how an analysis of the trust relationships in web-based social networks can lead to methods for inferring relationships, and that those inferred values, when integrated into applications, can enhance the user experience. My contributions can benefit research in online communities, the semantic web, recommender systems, and complex systems analysis. Through this work I have shown that using inferred trust relationships in web-based social networks offers some real benefits to the user. In order to accomplish this: • I present a formalization of trust as a computational concept within web-based social networks, by presenting a definition and describing the functional properties of trust that follow from the definition. • I present a set of algorithms for inferring trust relationships in social networks that are shown to be quite accurate. • I show that using trust inferences to make predictive recommendations can offer significant improvements when the user's opinion is divergent from the average
1.2 Organization For this dissertation, I have chosen trust in web-based social networks as a very specific area to study the larger issue of trust, reputation, and relationships in social networks. The decision to work with web-based social networks is enforced by the fact hat they form a large, publicly available dataset with tremendous interest from the general public. Chapter 2 specifically defines what qualifies as a web-based social network, and then presents the results of an exhaustive survey of websites. Over 133,000,000 user accounts spread across 127 websites were found, with subjects ranging from the deeply religious to the fringes of alternative sexual lifestyles. The description of he size and scope of websites is followed by a explanation of how users are able to add information to their social relationships. In fact, several large social networks already contain a notion of expressed trust between users, strengthening the choice to work with these datasets. Chapter 2 also introduces the Friend-Of-A-Friend(FoAF) project,a Semantic-Web based technology that allows users to combine information about hemselves from a variety of websites, and make statements about their friends even if those statements are not supported by the sites of which the user is a member Before making any computations with trust in social networks, it is vitally important to know what trust is and the properties it has. Within computer science, trust has been co-opted by many subfields to mean many different things. It is a descriptor of security and encryption(Kent, Atkinson, 1998); a name for authentication methods or gital signatures(Ansper, et al., 2001); a measure of the quality of a peer in p2P systems Lee, et al., 2003); a factor in game theory(McCabe et al., 2003); a model for agent interactions (Jonker, Treur, 1999); a gauge of attack-resistance (Wallach, et al
5 1.2 Organization For this dissertation, I have chosen trust in web-based social networks as a very specific area to study the larger issue of trust, reputation, and relationships in social networks. The decision to work with web-based social networks is enforced by the fact that they form a large, publicly available dataset with tremendous interest from the general public. Chapter 2 specifically defines what qualifies as a web-based social network, and then presents the results of an exhaustive survey of websites. Over 133,000,000 user accounts spread across 127 websites were found, with subjects ranging from the deeply religious to the fringes of alternative sexual lifestyles. The description of the size and scope of websites is followed by a explanation of how users are able to add information to their social relationships. In fact, several large social networks already contain a notion of expressed trust between users, strengthening the choice to work with these datasets. Chapter 2 also introduces the Friend-Of-A-Friend(FOAF) Project, a Semantic-Web based technology that allows users to combine information about themselves from a variety of websites, and make statements about their friends even if those statements are not supported by the sites of which the user is a member. Before making any computations with trust in social networks, it is vitally important to know what trust is and the properties it has. Within computer science, trust has been co-opted by many subfields to mean many different things. It is a descriptor of security and encryption (Kent, Atkinson, 1998); a name for authentication methods or digital signatures (Ansper, et al., 2001); a measure of the quality of a peer in P2P systems (Lee, et al., 2003); a factor in game theory (McCabe et al., 2003); a model for agent interactions (Jonker, Treur, 1999); a gauge of attack-resistance (Wallach, et al