Incentivized Campaigning in Social Networks

• Published in: IEEE/ACM transactions on networking 2017-06, Vol.25 (3), p.1621-1634
• Main Authors: Kotnis, Bhushan, Sunny, Albert, Kuri, Joy
• Format: Article
• Language: English
• Subjects: bootstrapped percolation; Computational modeling; Computer simulation; Digital media; Games; Incentives; incentivized campaigns; information control; Knowledge engineering; Optimization; Percolation theory; Pricing; Registers; reliability theory; Social network services; Social networks
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2016.2645281

Campaigners, advertisers, and activists are increasingly turning to social recommendation mechanisms, provided by social media, for promoting their products, services, brands, and even ideas. However, many a time, such social network-based campaigns perform poorly in practice, because the intensity of recommendations drastically reduces beyond a few hops from the source. A natural strategy for maintaining the intensity is to provide incentives. In this paper, we address the problem of minimizing the cost incurred by the campaigner for incentivizing a fraction of individuals in the social network, while ensuring that the campaign message reaches a given expected fraction of individuals. We also address the dual problem of maximizing the campaign penetration for a resource constrained campaigner. To help us understand and solve the above-mentioned problems, we use percolation theory to formally state them as optimization problems. These problems are not amenable to traditional approaches because of a fixed point equation that needs to be solved numerically. However, we use results from reliability theory to establish some key properties of the fixed point, which in turn enables us to solve these problems using algorithms that are linearithmic in maximum node degree. Furthermore, we evaluate the efficacy of the analytical solutions by performing simulations on real-world networks.