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 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.

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 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 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 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 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.