1997); a component of ubiquitous computing(Shankar, Abraugh, 2002); a foundation for interactions in agent systems(Maes, Kozierok, 1994: Barber, Kim, 2000); and a motivation for online interaction and recommender systems(Abdul-Rahman, Hailes, 1997). It is only in the last few years that the computing community has begun to look at he more social aspect of trust as a relationship between humans The difficulty of combining trust with algorithms and mathematical analyses is that trust is difficult to define, let alone to pin down in a quantifiable way. Intense theoretical anal ysis and complex models are one way to address this issue. However, the real boost to the union of these two topics has come in the form of web-based social networks that force people to quantify trust Beginning with work in the philosophical, sociological, and psychological communities,I present a definition that captures the nature of social trust relationships and also remains clear and simple enough to be used in social networks on the web. As is justified in chapter 3, the following definition of trust is used throughout this work: Alice trusts Bob if she commits to an action based on a belief that Bob's future actions will lead to a good outcome. This definition pervades this work. The first application is as a justification for the properties of trust that forms the foundation of the algorithms transitivity, composability, and asymmetry These definitions allow for the creation of algorithms that utilize the trust etworks. Chapters 5 and 6 present algorithms for working with networks where trust is expressed in binary values and over a continuous range, respectively. When a person has not expressed a trust rating for another person, the paths that connect them in a network can be used to infer how much one(the source) should trust the other(the sink ). These
6 1997);a component of ubiquitous computing (Shankar, Abraugh, 2002); a foundation for interactions in agent systems (Maes, Kozierok, 1994; Barber, Kim, 2000); and a motivation for online interaction and recommender systems (Abdul-Rahman, Hailes, 1997). It is only in the last few years that the computing community has begun to look at the more social aspect of trust as a relationship between humans. The difficulty of combining trust with algorithms and mathematical analyses is that trust is difficult to define, let alone to pin down in a quantifiable way. Intense theoretical analysis and complex models are one way to address this issue. However, the real boost to the union of these two topics has come in the form of web-based social networks that force people to quantify trust. Beginning with work in the philosophical, sociological, and psychological communities, I present a definition that captures the nature of social trust relationships and also remains clear and simple enough to be used in social networks on the web. As is justified in chapter 3, the following definition of trust is used throughout this work: Alice trusts Bob if she commits to an action based on a belief that Bob's future actions will lead to a good outcome. This definition pervades this work. The first application is as a justification for the properties of trust that forms the foundation of the algorithms: transitivity, composability, and asymmetry. These definitions allow for the creation of algorithms that utilize the trust networks. Chapters 5 and 6 present algorithms for working with networks where trust is expressed in binary values and over a continuous range, respectively. When a person has not expressed a trust rating for another person, the paths that connect them in a network can be used to infer how much one (the source) should trust the other (the sink). These
chapters introduce the al gorithms and present a theoretical and experimental analysis of their accuracy In chapter 5, I introduce two variations on an algorithm for inferring trust relationships in networks with binary trust ratings ("trusted"or "not trusted"). Using a statistical analysis and generated social networks for simulations, it is shown that these algorithms can produce highly accurate inferences about how much one person should trust another when as few as half of the trust ratings in the network agree with the source node's opinions. The relies on the binomial distribution created with the binary system Chapter 6 moves to ratings over a continuous scale. Because the properties of the binary networks are not available to help increase accuracy, chapter 6 begins with an analysis of how trust rating and path length affect the agreement between a source and ot This analysis is then used to develop an algorithm for calculating trust in networks with continuous ratings. Two naturally developed trust networks are used to show that my method is significantly better than several other algorithms taken from the literature. To demonstrate the usefulness of these calculated ratings, two applications are introduced that personalize the users' experiences based on their trust ratings and social connections. The first is FilmTrust, a website that integrates social networks, trust, and movie ratings and reviews. Users build social connections to other people in the network. For each connection, they rate how much they trust their friends opinion about movies Users also rate movies and write reviews The two are combined when a user visits a page about a movie. They are shown the average rating for the film and a personalized recommended rating"calculated from the most trusted people who have rated the movie As users' opinions deviate from the average, the personalized rating remains a relatively
7 chapters introduce the algorithms and present a theoretical and experimental analysis of their accuracy. In chapter 5, I introduce two variations on an algorithm for inferring trust relationships in networks with binary trust ratings ("trusted" or "not trusted"). Using a statistical analysis and generated social networks for simulations, it is shown that these algorithms can produce highly accurate inferences about how much one person should trust another when as few as half of the trust ratings in the network agree with the source node's opinions. The relies on the binomial distribution created with the binary system. Chapter 6 moves to ratings over a continuous scale. Because the properties of the binary networks are not available to help increase accuracy, chapter 6 begins with an analysis of how trust rating and path length affect the agreement between a source and other nodes. This analysis is then used to develop an algorithm for calculating trust in networks with continuous ratings. Two naturally developed trust networks are used to show that my method is significantly better than several other algorithms taken from the literature. To demonstrate the usefulness of these calculated ratings, two applications are introduced that personalize the users' experiences based on their trust ratings and social connections. The first is FilmTrust, a website that integrates social networks, trust, and movie ratings and reviews. Users build social connections to other people in the network. For each connection, they rate how much they trust their friend's opinion about movies. Users also rate movies and write reviews. The two are combined when a user visits a page about a movie. They are shown the average rating for the film and a personalized "recommended rating" calculated from the most trusted people who have rated the movie. As users' opinions deviate from the average, the personalized rating remains a relatively
accurate estimation of their opinions. Reviews of the movies are also sorted according to the trustworthiness of the author so users see the most relevant ones first The second application is TrustMail, an email client that uses the calculated trust rating of each email's sender as a score for the message. users are able to sort messages according to their trust value because ratings are drawn from an extended social network, they help users identify potentially important messages from oth erwise unknown senders. The ratings can also be used for sorting spam folders so that improperly classified messages could be pulled out more easily Ultimately, trust and social preferences can be integrated into any number of potential applications. However, there is a larger application of this work. Social networks are only one type of complex system, and trust is only one type of relationshi The analysis in this work shows how an understanding of the properties of relationship- types within systems can lead to effective algorithms for understanding the relationships implicit in those systems. There are many other projects where these types of analyses can lead to results. Chapter 10 approaches this broader application with brief introductions to ongoing projects extending the work in this dissertation, as well as ecoinformatics, and information filtering This work is both the beginnings for future work and a case study the applications presented here represent only a small portion of how the specific results of rust in social networks can be applied, and a still smaller fraction of how such techniques can be applied to complex systems analysis. This work should complement the growin body of work that is integrating social network analysis and trust into the user experience Furthermore, the results here seem to suggest that a deeper understanding of the
8 accurate estimation of their opinions. Reviews of the movies are also sorted according to the trustworthiness of the author so users see the most relevant ones first. The second application is TrustMail, an email client that uses the calculated trust rating of each email's sender as a score for the message. Users are able to sort messages according to their trust value. Because ratings are drawn from an extended social network, they help users identify potentially important messages from otherwise unknown senders. The ratings can also be used for sorting spam folders so that improperly classified messages could be pulled out more easily. Ultimately, trust and social preferences can be integrated into any number of potential applications. However, there is a larger application of this work. Social networks are only one type of complex system, and trust is only one type of relationship. The analysis in this work shows how an understanding of the properties of relationshiptypes within systems can lead to effective algorithms for understanding the relationships implicit in those systems. There are many other projects where these types of analyses can lead to results. Chapter 10 approaches this broader application with brief introductions to ongoing projects extending the work in this dissertation, as well as ecoinformatics, and information filtering. This work is both the beginnings for future work and a case study. The applications presented here represent only a small portion of how the specific results of trust in social networks can be applied, and a still smaller fraction of how such techniques can be applied to complex systems analysis. This work should complement the growing body of work that is integrating social network analysis and trust into the user experience. Furthermore, the results here seem to suggest that a deeper understanding of the
relationships in complex systems and methods for inferring information about them has the potential to lead to new discoveries in the social, biological, and physical sciences
9 relationships in complex systems and methods for inferring information about them has the potential to lead to new discoveries in the social, biological, and physical sciences
Chapter 2 Web-Based Social Networks 2. Introduction Web-based social networks(WBSN) have grown quickly in number and sc since the mid-1990s. They present an interesting challenge to traditional ways of thinking about social networks. First, they are large, living examples of social networks. It has rarely, if ever, been possible to look at an actual network of millions of people without using models to fill in or simulate most of the network. The problem of gathering social information about a large group of people has been a difficult one. With WBSNs, there are many networks with millions of users that need no generated data. These networks are also much more complex with respect to the types of relationships they allow Information qualifying and quantifying aspects of the social connection between peopl is common in these systems. This means there is a potential for much richer analysis of he network As interest in social networking has grown the term social network"has become looser. Many sites promote themselves as social networks when they do not maintain any
10 Chapter 2 Web-Based Social Networks 2.1 Introduction Web-based social networks (WBSN) have grown quickly in number and scope since the mid-1990s. They present an interesting challenge to traditional ways of thinking about social networks. First, they are large, living examples of social networks. It has rarely, if ever, been possible to look at an actual network of millions of people without using models to fill in or simulate most of the network. The problem of gathering social information about a large group of people has been a difficult one. With WBSNs, there are many networks with millions of users that need no generated data. These networks are also much more complex with respect to the types of relationships they allow. Information qualifying and quantifying aspects of the social connection between people is common in these systems. This means there is a potential for much richer analysis of the network. As interest in social networking has grown, the term "social network" has become looser. Many sites promote themselves as social networks when they do not maintain any