Advertising is a significant source of revenue for most online social networks. Conventional online advertising methods need to be customized for online social networks in order to address their distinct characteristics. Recent experimental studies have shown that providing social cues along with ads, e.g. information about friends liking the ad or clicking on an ad, leads to higher click rates. In other words, the probability of a user clicking an ad is a function of the set of friends that have clicked the ad. In this work, we propose formal probabilistic models to capture this phenomenon, and study the algorithmic problem that then arises. Our work is in the context of display advertising where a contract is signed to show an ad to a pre-determined number of users. The problem we study is the following: given a certain number of impressions, what is the optimal display strategy, i.e. the optimal order and the subset of users to show the ad to, so as to maximize the expected number of clicks? Unlike previous models of influence maximization, we show that this optimization problem is hard to approximate in general, and that it is related to finding dense subgraphs of a given size. In light of the hardness result, we propose several heuristic algorithms including a two-stage algorithm inspired by influence-and-exploit strategies in viral marketing. We evaluate the performance of these heuristics on real data sets, and observe that our two-stage heuristic significantly outperforms the natural baselines.

In recent years there has been an explosive growth of digital content in the form of news feeds, videos, and original content on online platforms such as blogs and social networks. Indeed, such platforms have been used as a means of sharing and republishing information, leading to a large collection of content that users must sift through. We consider the problem of curating this vast catalogue of content such that aggregators or publishers can offer readers content that is of interest to them, with minimal spam. Under a game-theoretic model we obtain several results on the optimal content selection and on the efficiency of distributed curation.

Aggregator websites typically present documents in the form of representative clusters. In order for users to get a broader perspective, it is important to deliver a diversified set of representative documents in those clusters. One approach to diversification is to maximize the average dissimilarity among documents. Another way to capture diversity is to avoid showing several documents from the same category (e.g. from the same news channel). We combine the above two diversification concepts by modeling the latter approach as a (partition) matroid constraint, and study diversity maximization problems under matroid constraints. We present the first constant-factor approximation algorithm for this problem, using a new technique. Our local search 0.5-approximation algorithm is also the first constant-factor approximation for the max-dispersion problem under matroid constraints. Our combinatorial proof technique for maximizing diversity under matroid constraints uses the existence of a family of Latin squares which may also be of independent interest.

Presently several marketplace applications over online social networks are gaining popularity. An important class of applications is online market exchange of items. Examples include peerflix.com and readitswapit.co.uk. We model this problem as a social network where each user has two associated lists. The item list consists of items the user is willing to give away to other users. The wish list consists of items the user is interested in receiving. A transaction involves a user giving an item to another user. Users are motivated to transact in expectation of realizing their wishes. Wishes may be realized by a pair of users swapping items corresponding to each other's wishes, but more generally by means of users exchanging items through a cycle, where each user gives an item to the next user in the cycle, in accordance with the receiving user's wishes. The problem we consider is how to efficiently generate recommendations for item exchange cycles, for users in a social network. Each cycle has a value which is determined by the number of items exchanged through the cycle. We focus on the problem of generating recommendations under two models. In the deterministic model, the value of a recommendation is the total number of items exchanged through cycles. In the probabilistic model, there is a probability associated with a user transacting with another user and a user being willing to trade an item for another. The value of a recommendation then is the expected number of items exchanged. We show that under both models, the problem of determining an optimal recommendation is NP-complete and develop efficient approximation algorithms for both. We show that our algorithms have guaranteed approximation factors of 2k (for greedy), 2k -1 (for local search), and(2k + 1)/3 (for combination of greedy and local search) where k is the max cycle length. We also develop a so-called maximal algorithm, which does not have an approximation guarantee but is more efficient. We conduct a comprehensive set of experiments. Our experiments show that in practice, the approximation quality achieved by maximal is competitive w.r.t. that of the other algorithms. On the other hand, maximal outperforms all other algorithms on scalability w.r.t. network size.

We examine the case of over-specialization in recommender systems, which results from returning items that are too similar to those previously rated by the user. We propose Outside-The-Box (otb) recommendation, which takes some risk to help users make fresh discoveries, while maintaining high relevance. The proposed formalization relies on item regions and attempts to identify regions that are under-exposed to the user. We develop a recommendation algorithm which achieves a compromise between relevance and risk to find otb items. We evaluate this approach on the MovieLens data set and compare our otb recommendations against conventional recommendation strategies.

Motivated by several marketplace applications on rapidly growing online social networks, we study the problem of efficient offline matching algorithms for online exchange markets. We consider two main models of one-shot markets and exchange markets over time. For one-shot markets, we study three main variants of the problem: one-to-one exchange market problem, exchange market problem with short cycles, and probabilistic exchange market problem. We show that all the above problems are NP-hard, and propose heuristics and approximation algorithms for these problems. Experiments show that the number of items exchanged will increase when exchanges through cycles are allowed. Exploring algorithms for markets over time is an interesting direction for future work.