Title: Characterizing and Leveraging Social Phenomena in Online Networks
Description: Social phenomena have been studied extensively in small scales by social scientists. With the increasing popularity of Web 2.0 and online social networks/media, a large amount of data on social phenomena have become available. In this dissertation we study online social phenomena such as social influence in social networks in various contexts. This dissertation has two major components: 1. Identifying and characterizing online social phenomena 2. Leveraging online social phenomena for economic and commercial purposes. We begin the dissertation by developing multi-level revenue sharing schemes for viral marketing on social networks. Viral marketing leverages social influence among users of the social network. For our proposed models, we develop results on the computational complexity, individual rationality, and potential reach of employing the Shapley value as a revenue sharing scheme. Our results indicate that under the multi-level tree-based propagation model, the Shapley value is a promising scheme for revenue sharing, whereas under other models there are computational or incentive compatibility issues that remain open.

We continue with another application of social influence: social advertising. Social advertising is a new paradigm that is utilized by online social networks. Social advertising is based in the premise that social influence can be leveraged to place ads more efficiently. The goal of our work is to understand how social ads can affect click-through rates in social networks. We propose a formal model for social ads in the context of display advertising. In our model, ads are shown to users one after the other. The probability of a user clicking an ad depends on the users who have clicked this ad so far. This information is presented to users as a social cue, thus the click probability is a function of this cue. We introduce the social display optimization problem: suppose an advertiser has a contract with a publisher for showing some number (say B) impressions of an ad. What strategy should the publisher use to show these ads so as to maximize the expected number of clicks? We show hardness results for this problem and in light of the general hardness results, we develop heuristic algorithms and compare them to natural baseline ones.

We then study distributed content curation on the Web. In recent years readers have turned to the social web to consume content. In other words, they rely on their social network to curate content for them as opposed to the more traditional way of relying on news editors for this purpose -- this is an implicit consequence of social influence as well. We study how efficient this is for users with limited budgets of attention. We model distributed content curation as a reader-publisher game and show various results. Our results imply that in the complete information setting, when publishers maximize their utility selfishly, distributed content curation reaches an equilibrium which is efficient, that is, the social welfare is a constant factor of that under an optimal centralized curation. Next, we initiate the study of an exchange market problem without money that is a natural generalization of the well-studied kidney exchange problem. From the practical point of view, the problem is motivated by barter websites on the Internet, e.g., swap.com, and u-exchange.com.

In this problem, the users of the social network wish to exchange items with each other. A mechanism specifies for each user a set of items that she gives away, and a set of items that she receives. Consider a set of agents where each agent has some items to offer, and wishes to receive some items from other agents. Each agent would like to receive as many items as possible from the items that she wishes, that is, her utility is equal to the number of items that she receives and wishes. However, she will have a large dis-utility if she gives away more items than what she receives, because she considers such a trade to be unfair. To ensure voluntary participation (also known as individual rationality), we require the mechanism to avoid this. We consider different variants of this problem: with and without a constraint on the length of the exchange cycles and show different results including their truthfulness and individual rationality. In the other main component of this thesis, we study and characterize two other social phenomena: 1. friends vs. the crowd and 2. altruism vs. reciprocity in social networks.

More specifically, we study how a social network user's actions are influenced by her friends vs. the crowd's opinion. For example, in social rating websites where both ratings from friends and average ratings from everyone is available, we study how similar one's ratings are to each other. In the next part, we aim to analyze the motivations behind users' actions on online social media over an extended period of time. We look specifically at users' likes, comments and favorite markings on their friends' posts and photos. Most theories of why people exhibit prosocial behavior isolate two distinct motivations: Altruism and reciprocity. In our work, we focus on identifying the underlying motivations behind users' prosocial giving on social media. In particular, our goal is to identify if the motivation is altruism or reciprocity. For that purpose, we study two datasets of sequence of users' actions on social media: a dataset of wall posts by users of Facebook.com, and another dataset of favorite markings by users of Flickr.com.

We study the sequence of users' actions in these datasets and provide several observations on patterns related to their prosocial giving behavior.