Influence And Exploit Strategies For Social Networks

Abstract

The importance of online social networks in advertising and market research is by now indubitable. Social networks provide detailed and broad information for millions of users and companies have been using this information to increasemarket penetration of their products. Social network companies use the revenue exerted by advertisements to sustain the costs involved in maintaining theirservers and quality of service, as well as to provide the basis of a sustainable business model. However, there is a large discrepancy between the perceived value of Social Networks and the actual revenue they generate.The widespread belief is that much of the potential of Social Networks remains unexploited. This premise has spurred a large amount of research in the direction of monetizing Social Networks. In this thesis, we are concerned with utilizing the information about the structure and strength of social ties in order to achieve certain objectives. We review previous approaches and focus on two important and closely related problems, that of Influence Maximization[Kempe, Kleinberg, Tardos'03] and Revenue Maximization[Hartline, Mirrokni, Sundararajan, '08]. The Influence Maximization Problem considers situations where a binary decision is made about adopting or not an innovation(product,technology,behaviour) and seeks for the best seed of initial adopters that achieve overall maximum spread by interacting with their social contacts. On the other hand, the Revenue Maximization Problem aims at exploiting positive network effects between buyers about the value of a product to devise a marketing strategy that maximizes the revenue. We focus an a class of strategies called Influence and Exploit, where a set of individuals is treated preferentially(free product, monetary incentives) in order to ``seed" the network(Influence) and then the remaining individuals are exploited(full price, no incentives) to achieve the objective(higher revenue, wider adoption). The technical contribution of this thesis concerns the Revenue Maximization Problem under the Uniform Additive Model[Hartline et al.'08]. We initially prove that the problem remains NP-Hard even for the undirected case via a reduction from Monotone One-in-Three SAT. Then, we embark a systematic study of the algorithmic properties of Influence and Exploit strategies. We prove that finding the Optimal Influence and Exploit strategy is NP-Hard and provide lower bounds on the ratio between the revenue extracted from an optimal IE strategy and the optimal revenue in general. Furthermore, we slightly extend and optimize the simple IE strategies proposed by Hartline et. al obtaining a first improvement of the approximation ratio of the problem. Our main technical contribution lies in developing powerful Semidefinite Programming Relaxations for designing IE strategies and the corresponding significant improvement on the approximation ratio for the problem. Finally, we propose a class of Local Search strategies to improve on an given solution and introduce intelligent heuristics based on Eigenvector Centrality correlating explicitly network position and the price to be offered to each buyer.