Near Optimal Social Promotion in Online Social Networks

Abstract

Due to dramatic growth of user population in the past decade, online social networks have become attractive channels for companies to launch marketing campaigns. We study a couple of closely related problems in online social networks. We first study the problem of active friending, which can be considered as a service provided by the social platforms to stimulate user engagement. The idea is that a source user can name a target user and the social platform offers a friending strategy to maximize the probability of the target accepting the invitation from the source. We prove that the problem is NP-hard and propose a discrete semi-differential based algorithm with guaranteed approximation ratio. As for the profit maximization problem, we consider the scenario when a profit is generated from group activities, captured by a hypergraph where hyperedges are introduced to represent the interactions among multiple users. We prove that the problem is NP-hard and develop an approximation algorithm along with an exchange-based technique to maximize the profit generated from group activities. In social advertising, the goal of online social platforms is to optimize the ad allocation with multiple advertisers. We access the tradeoff between maximizing the revenue earned from each advertiser and reducing free-riding to ensure the truthfulness of advertisers. We prove that both budgeted and unconstrained ad allocation problems are NP-hard and then develop constant factor approximation algorithms for both problems. We also study the adaptive version of the seed selection problem and the discount allocation problem. The goal is to find a limited set of highly influential seed users to assign proper discounts, such that the number of users who finally adopt the product is maximized. We propose a series of adaptive policies with bounded approximation ratio for both problems.