Social network ad allocation and optimization: a geometric mapping-based approach

With the increasing popularity of online social networks (SNS), many advertisers choose to post their advertisements (ads) within SNS. Advertising activity on SNS has grown rapidly and is now a billion-dollar business. For example, Facebook has reached more than 1 million active advertisers who contribute 90% of its revenue. In the SNS advertising model, advertisers participating in a SNS ad campaign benefit from the effects of viral marketing and network diffusion. Modern SNS serve as advertising agents and take advantage of the network diffusion to attract advertisers and charge for the cascading impressions. The optimal ad allocation task is the problem of choosing the ad allocation plan that maximizes revenue for the SNS. Considering that users have diffusion abilities and limited daily impressions, and advertisers have various bidding prices and budget concerns, a feasible plan that obeys the constraints is difficult to find. The solution to this problem lies in the space of \({\mathbb {N}}_0^{|Ads|\times |Users|}\), which makes direct optimization unattractive. In this work, we study SNS advertising business models and formulate the SNS ad allocation problem. We show the problem is NP-hard and propose two dimension reduction schemes together with novel relaxation techniques. Our dimension reduction technique is formulated based on SNS user profile-based bidding scenario as well as social influence-based billing policies. We show the core ideas for dimension reduction are applicable to generalized assignment problems in bipartite graphs. We further draw connections between geometric mapping for complex network and the SNS ad allocation problem and map the SNS onto 2-D geometric space in order to relax the problem to geometric region allocation problems. We develop an optimization framework and solve the relaxed problem as a series of linear programs. Our proposed method is able to reduce the dimensionality of the original problem significantly, run two to four orders of magnitude faster, and reach 95% of the optimal solution. In addition, we discuss several extensions of our approach, including shape design in the geometric space for incorporating domain constraints in allocation strategies, more comprehensive real-world social influence models, as well as an alternative relaxation approach and its application in generalized assignment problems.